In [1]:

    

from __future__ import print_function
import numpy as np


    

In [2]:

    

from bocchan.matching import deferred_acceptance as bocchan
from keiikegami.deferred_acceptance import da3 as keiikegami
from mhanami.gs_one import deferred_acceptance as mhanami
from NlGG.matching import deferred_acceptance as NlGG
from tsuyoshi.da_algorithms import gale_shapley as tsuyoshi
from oyamad.matching import deferred_acceptance as oyamad


    

In [3]:

    

from oyamad.matching_tools import random_prefs


    

In [4]:

    

# Test case
m_unmatched = 3
m_prefs = [[0, 1, 2, m_unmatched],
           [2, 0, 1, m_unmatched],
           [1, 2, 0, m_unmatched],
           [2, 0, 1, m_unmatched]]
f_unmatched = 4
f_prefs = [[2, 0, 1, 3, f_unmatched],
           [0, 1, 2, 3, f_unmatched],
           [2, f_unmatched, 1, 0, 3]]

# Unique stable matching
m_matched = [0, 1, 2, m_unmatched]
f_matched = [0, 1, 2]


    

In [5]:

    

bocchan(m_prefs, f_prefs)


    

    




[0, 1, 2, 3]
[3, 3, 3, 3]
[4, 4, 4]






    
Out[5]:





([0, 2, 1, 3], [4, 4, 4])

In [6]:

    

bocchan(f_prefs, m_prefs)


    

    




[0, 1, 2]
[4, 4, 4]
[3, 3, 3, 3]






    




---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
<ipython-input-6-b1608f96d3fb> in <module>()
----> 1 bocchan(f_prefs, m_prefs)

/Users/oyama/Development/zemi/2015/DA/bocchan/matching.pyc in deferred_acceptance(arg1, arg2)
     23             arg1_matched[y] = x
     24         else:
---> 25             if arg2[y].index(arg2_matched[y])<arg2[y].index(x):
     26                 single.insert(0, x)
     27             else:

ValueError: 0 is not in list

In [7]:

    

funcs = {#"bocchan": bocchan,
         "keiikegami": keiikegami,
         "mhanami": mhanami,
         "NlGG": NlGG,
         "tsuyoshi": tsuyoshi,
         "oyamad": oyamad}


    

In [8]:

    

# Test case
m_unmatched = 3
m_prefs = [[0, 1, 2, m_unmatched],
           [2, 0, 1, m_unmatched],
           [1, 2, 0, m_unmatched],
           [2, 0, 1, m_unmatched]]
f_unmatched = 4
f_prefs = [[2, 0, 1, 3, f_unmatched],
           [0, 1, 2, 3, f_unmatched],
           [2, f_unmatched, 1, 0, 3]]

# Unique stable matching
m_matched = [0, 1, 2, m_unmatched]
f_matched = [0, 1, 2]

for name, func in funcs.iteritems():
    m_matched_computed, f_matched_computed = func(m_prefs, f_prefs)
    msg = 'OK' if np.array_equal(m_matched_computed, m_matched) and \
                  np.array_equal(f_matched_computed, f_matched) \
          else 'Failed'
    print(name + ': ' + msg)


    

    




tsuyoshi: OK
NlGG: OK
mhanami: OK
keiikegami: OK
oyamad: OK

In [9]:

    

m, n = 50, 50
prop_prefs, resp_prefs = random_prefs(m, n)

funcs = {#"bocchan": bocchan,
         "keiikegami": keiikegami,
         "mhanami": mhanami,
         "NlGG": NlGG,
         "tsuyoshi": tsuyoshi,
         "oyamad": oyamad}

for name, func in funcs.iteritems():
    print(name)
    %timeit func(prop_prefs, resp_prefs)


    

    




tsuyoshi
1000 loops, best of 3: 569 µs per loop
NlGG






    




---------------------------------------------------------------------------
AttributeError                            Traceback (most recent call last)
<ipython-input-9-9266a0835f64> in <module>()
     11 for name, func in funcs.iteritems():
     12     print(name)
---> 13     get_ipython().magic(u'timeit func(prop_prefs, resp_prefs)')

//anaconda/lib/python2.7/site-packages/IPython/core/interactiveshell.pyc in magic(self, arg_s)
   2302         magic_name, _, magic_arg_s = arg_s.partition(' ')
   2303         magic_name = magic_name.lstrip(prefilter.ESC_MAGIC)
-> 2304         return self.run_line_magic(magic_name, magic_arg_s)
   2305 
   2306     #-------------------------------------------------------------------------

//anaconda/lib/python2.7/site-packages/IPython/core/interactiveshell.pyc in run_line_magic(self, magic_name, line)
   2223                 kwargs['local_ns'] = sys._getframe(stack_depth).f_locals
   2224             with self.builtin_trap:
-> 2225                 result = fn(*args,**kwargs)
   2226             return result
   2227 

//anaconda/lib/python2.7/site-packages/IPython/core/magics/execution.pyc in timeit(self, line, cell)

//anaconda/lib/python2.7/site-packages/IPython/core/magic.pyc in <lambda>(f, *a, **k)
    191     # but it's overkill for just that one bit of state.
    192     def magic_deco(arg):
--> 193         call = lambda f, *a, **k: f(*a, **k)
    194 
    195         if callable(arg):

//anaconda/lib/python2.7/site-packages/IPython/core/magics/execution.pyc in timeit(self, line, cell)
   1034             number = 1
   1035             for _ in range(1, 10):
-> 1036                 time_number = timer.timeit(number)
   1037                 worst_tuning = max(worst_tuning, time_number / number)
   1038                 if time_number >= 0.2:

//anaconda/lib/python2.7/site-packages/IPython/core/magics/execution.pyc in timeit(self, number)
    130         gc.disable()
    131         try:
--> 132             timing = self.inner(it, self.timer)
    133         finally:
    134             if gcold:

<magic-timeit> in inner(_it, _timer)

/Users/oyama/Development/zemi/2015/DA/NlGG/matching.pyc in deferred_acceptance(m_prefs, f_prefs)
     26             if mbest != fnum:
     27 
---> 28                 if f_prefs[mbest].index(i) < f_prefs[mbest].index(have[mbest]):
     29                     single.remove(i)
     30                     if have[mbest] != mnum:

AttributeError: 'numpy.ndarray' object has no attribute 'index'

In [10]:

    

m, n = 50, 50
prop_prefs, resp_prefs = random_prefs(m, n)
prop_prefs_list, resp_prefs_list = prop_prefs.tolist(), resp_prefs.tolist()

funcs = {#"bocchan": bocchan,
         "keiikegami": keiikegami,
         "mhanami": mhanami,
         "NlGG": NlGG,
         "tsuyoshi": tsuyoshi,
         "oyamad": oyamad}

for name, func in funcs.iteritems():
    print(name)
    if name == 'NlGG':
        print('NA')
    else:
        %timeit func(prop_prefs, resp_prefs)
    %timeit func(prop_prefs_list, resp_prefs_list)


    

    




tsuyoshi
1000 loops, best of 3: 374 µs per loop
1000 loops, best of 3: 588 µs per loop
NlGG
NA
1000 loops, best of 3: 466 µs per loop
mhanami
100 loops, best of 3: 7.8 ms per loop
1000 loops, best of 3: 1.83 ms per loop
keiikegami
10 loops, best of 3: 20.4 ms per loop
10 loops, best of 3: 20.9 ms per loop
oyamad
The slowest run took 3315.69 times longer than the fastest. This could mean that an intermediate result is being cached 
1 loops, best of 3: 73 µs per loop
1000 loops, best of 3: 294 µs per loop

In [11]:

    

m, n = 200, 200
prop_prefs, resp_prefs = random_prefs(m, n)
prop_prefs_list, resp_prefs_list = prop_prefs.tolist(), resp_prefs.tolist()

funcs = {#"bocchan": bocchan,
         "keiikegami": keiikegami,
         "mhanami": mhanami,
         "NlGG": NlGG,
         "tsuyoshi": tsuyoshi,
         "oyamad": oyamad}

for name, func in funcs.iteritems():
    print(name)
    if name == 'NlGG':
        print('NA')
    else:
        %timeit func(prop_prefs, resp_prefs)
    %timeit func(prop_prefs_list, resp_prefs_list)


    

    




tsuyoshi
100 loops, best of 3: 4.38 ms per loop
100 loops, best of 3: 7.25 ms per loop
NlGG
NA
100 loops, best of 3: 9.05 ms per loop
mhanami
10 loops, best of 3: 174 ms per loop
10 loops, best of 3: 58.5 ms per loop
keiikegami
1 loops, best of 3: 1.09 s per loop
1 loops, best of 3: 1.08 s per loop
oyamad
1000 loops, best of 3: 231 µs per loop
100 loops, best of 3: 3.29 ms per loop

In [12]:

    

m, n = 500, 500
prop_prefs, resp_prefs = random_prefs(m, n)
prop_prefs_list, resp_prefs_list = prop_prefs.tolist(), resp_prefs.tolist()

funcs = {#"bocchan": bocchan,
         #"keiikegami": keiikegami,
         "mhanami": mhanami,
         "NlGG": NlGG,
         "tsuyoshi": tsuyoshi,
         "oyamad": oyamad}

for name, func in funcs.iteritems():
    print(name)
    if name in ['NlGG', 'keiikegami']:
        print('NA')
    else:
        %timeit func(prop_prefs, resp_prefs)
    %timeit func(prop_prefs_list, resp_prefs_list)


    

    




NlGG
NA
10 loops, best of 3: 91.8 ms per loop
tsuyoshi
10 loops, best of 3: 23.2 ms per loop
10 loops, best of 3: 43.7 ms per loop
mhanami
1 loops, best of 3: 1.71 s per loop
1 loops, best of 3: 791 ms per loop
oyamad
1000 loops, best of 3: 1.5 ms per loop
10 loops, best of 3: 21.8 ms per loop

In [13]:

    

m, n = 1000, 1000
prop_prefs, resp_prefs = random_prefs(m, n)
prop_prefs_list, resp_prefs_list = prop_prefs.tolist(), resp_prefs.tolist()

funcs = {#"bocchan": bocchan,
         #"keiikegami": keiikegami,
         #"mhanami": mhanami,
         "NlGG": NlGG,
         "tsuyoshi": tsuyoshi,
         "oyamad": oyamad}

for name, func in funcs.iteritems():
    print(name)
    if name in ['NlGG', 'keiikegami', 'mhanami']:
        print('NA')
    else:
        %timeit func(prop_prefs, resp_prefs)
    %timeit func(prop_prefs_list, resp_prefs_list)


    

    




NlGG
NA
1 loops, best of 3: 381 ms per loop
tsuyoshi
10 loops, best of 3: 74.1 ms per loop
10 loops, best of 3: 154 ms per loop
oyamad
100 loops, best of 3: 6.72 ms per loop
10 loops, best of 3: 88 ms per loop

In [15]:

    

import platform
print(platform.platform())


    

    




Darwin-13.4.0-x86_64-i386-64bit

In [16]:

    

import sys
print(sys.version)


    

    




2.7.9 |Anaconda 2.2.0 (x86_64)| (default, Dec 15 2014, 10:37:34) 
[GCC 4.2.1 (Apple Inc. build 5577)]

In [17]:

    

import numpy
print(numpy.__version__)


    

    




1.9.2

In [18]:

    

import numba
print(numba.__version__)


    

    




0.17.0

In [ ]: