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 deferred_acceptance as keiikegami
from mhanami.gs_one import deferred_acceptance as mhanami
from NlGG.matching import deferred_acceptance as NlGG
from ogaway.matching import deferred_acceptance as ogaway
from oyamad.matching import deferred_acceptance as oyamad


    

In [3]:

    

from oyamad.matching_tools import random_prefs


    

In [4]:

    

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


    

In [5]:

    

# 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)


    

    




ogaway: OK
bocchan: OK
oyamad: OK
keiikegami: OK
NlGG: OK
受験者 0 が、大学 0 に応募します






    




---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-5-2af5e4003573> in <module>()
     15 
     16 for name, func in funcs.iteritems():
---> 17     m_matched_computed, f_matched_computed = func(m_prefs, f_prefs)
     18     msg = 'OK' if np.array_equal(m_matched_computed, m_matched) and                   np.array_equal(f_matched_computed, f_matched)           else 'Failed'
     19     print(name + ': ' + msg)

/Users/oyama/Development/zemi/2015/DA_many-to-one/mhanami/gs_one.pyc in deferred_acceptance(prop_prefs, resp_prefs, caps)
    132             # -> strは数値等を文字列に変換する関数ですが、配列を文字に変換はできないと思います……
    133             # -> capsは大学の定員の配列なので、もうすでに数値（int型）ではないでしょうか
--> 134                 if len(resp_matches[candidate]) < caps[candidate]:
    135                     pref = resps[candidate]
    136                     if pref.index(i) < pref.index(resp_unmatched_mark):

TypeError: 'NoneType' object has no attribute '__getitem__'

In [6]:

    

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

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)


    

    




ogaway: OK
oyamad: OK
NlGG: OK
keiikegami: OK
bocchan: OK

In [7]:

    

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,
         "ogaway": ogaway,
         "oyamad": oyamad}

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


    

    




ogaway
1000 loops, best of 3: 1.68 ms per loop
oyamad
The slowest run took 6956.36 times longer than the fastest. This could mean that an intermediate result is being cached 
1 loops, best of 3: 109 µs per loop
NlGG
1000 loops, best of 3: 1.56 ms per loop
keiikegami
1000 loops, best of 3: 480 µs per loop
bocchan






    




---------------------------------------------------------------------------
AttributeError                            Traceback (most recent call last)
<ipython-input-7-de4ba1a84969> in <module>()
     12 for name, func in funcs.iteritems():
     13     print(name)
---> 14     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)
   2305         magic_name, _, magic_arg_s = arg_s.partition(' ')
   2306         magic_name = magic_name.lstrip(prefilter.ESC_MAGIC)
-> 2307         return self.run_line_magic(magic_name, magic_arg_s)
   2308 
   2309     #-------------------------------------------------------------------------

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

//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_many-to-one/bocchan/matching.pyc in deferred_acceptance(prop_prefs, resp_prefs, caps)
     31         if y != prop_unmatched:
     32             if caps_cntr[y] >= 1:
---> 33                 if resp_prefs[y].index(resp_unmatched) > resp_prefs[y].index(x):
     34                     now_y = sum(caps_cp[:y]) + caps_cntr[y] - 1
     35                     resp_matched[now_y] = x

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

In [8]:

    

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,
         "ogaway": ogaway,
         "oyamad": oyamad}

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


    

    




ogaway
100 loops, best of 3: 2.14 ms per loop
100 loops, best of 3: 2.57 ms per loop
oyamad
10000 loops, best of 3: 71.4 µs per loop
1000 loops, best of 3: 319 µs per loop
NlGG
1000 loops, best of 3: 1.83 ms per loop
100 loops, best of 3: 2.03 ms per loop
keiikegami
1000 loops, best of 3: 533 µs per loop
1000 loops, best of 3: 751 µs per loop
bocchan
NA
1000 loops, best of 3: 753 µs per loop

In [9]:

    

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,
         "ogaway": ogaway,
         "oyamad": oyamad}

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


    

    




ogaway
1 loops, best of 3: 302 ms per loop
1 loops, best of 3: 501 ms per loop
oyamad
100 loops, best of 3: 9.05 ms per loop
10 loops, best of 3: 92.2 ms per loop
NlGG
1 loops, best of 3: 343 ms per loop
1 loops, best of 3: 414 ms per loop
keiikegami
10 loops, best of 3: 103 ms per loop
10 loops, best of 3: 181 ms per loop
bocchan
NA
1 loops, best of 3: 498 ms per loop

In [10]:

    

# Test case
num_s, num_c = 11, 5
s_unmatched = num_c
s_prefs = [[2, 0, 4, 3, s_unmatched, 1],
           [0, 2, 3, 1, 4, s_unmatched],
           [3, 4, 2, 0, 1, s_unmatched],
           [2, 3, 0, 4, s_unmatched, 1],
           [0, 3, 1, s_unmatched, 2, 4],
           [3, 2, 1, 0, 4, s_unmatched],
           [1, 4, 0, 2, s_unmatched, 3],
           [0, 2, 1, 4, 3, s_unmatched],
           [3, 0, 4, s_unmatched, 1, 2],
           [2, 0, 4, 1, 3, s_unmatched],
           [4, 3, 0, 2, 1, s_unmatched]]
c_unmatched = num_s
c_prefs = [[2, 6, 8, 10, 4, 3, 9, 7, 5, 0, 1, c_unmatched],
           [4, 6, 9, 5, 7, 1, 2, 10, c_unmatched, 0, 3, 8],
           [10, 5, 7, 2, 1, 3, 6, 0, 9, c_unmatched, 4, 8],
           [9, 0, 1, 10, 3, 8, 4, 2, 5, 7, c_unmatched, 6],
           [1, 3, 9, 6, 5, 0, 7, 2, 10, 8, c_unmatched, 4]]
caps = [4, 1, 3, 2, 1]
indptr = [0, 4, 5, 8, 10, 11]

# Unique stable matching
s_matched = [2, 0, 3, 2, 0, 2, 1, 0, 3, 0, 4]
c_matched = [1, 4, 7, 9, 6, 0, 3, 5, 2, 8, 10]


    

In [11]:

    

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

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)


    

    




ogaway: OK
oyamad: OK
NlGG: OK
keiikegami: OK
bocchan: OK

In [12]:

    

m, n = 50, 50
prop_prefs, resp_prefs, caps = random_prefs(m, n, return_caps=True)
prop_prefs_list, resp_prefs_list, caps_list \
    = prop_prefs.tolist(), resp_prefs.tolist(), caps.tolist()

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

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


    

    




ogaway
1000 loops, best of 3: 512 µs per loop
1000 loops, best of 3: 832 µs per loop
oyamad
The slowest run took 6953.26 times longer than the fastest. This could mean that an intermediate result is being cached 
1 loops, best of 3: 110 µs per loop
The slowest run took 2078.43 times longer than the fastest. This could mean that an intermediate result is being cached 
1 loops, best of 3: 371 µs per loop
NlGG






    




---------------------------------------------------------------------------
IndexError                                Traceback (most recent call last)
<ipython-input-12-97a6735ed2e2> in <module>()
     15         print('NA')
     16     else:
---> 17         get_ipython().magic(u'timeit func(prop_prefs, resp_prefs, caps)')
     18     get_ipython().magic(u'timeit func(prop_prefs_list, resp_prefs_list, caps_list)')

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

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

//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_many-to-one/NlGG/matching.pyc in deferred_acceptance(p_prefs, r_prefs, caps)
     61 
     62                         # 今持ってる人の中で最悪の人より、応募者iのがよい場合
---> 63                         if rank_i < ranks[ranks_sort[-1]]:
     64                             replaced_place = ranks_sort[-1]
     65                             replaced_name = resp_matched[indptr[pbest]:indptr[pbest+1]][replaced_place]

IndexError: index -1 is out of bounds for axis 0 with size 0

In [13]:

    

m, n = 50, 50
prop_prefs, resp_prefs, caps = random_prefs(m, n, return_caps=True)
prop_prefs_list, resp_prefs_list, caps_list \
    = prop_prefs.tolist(), resp_prefs.tolist(), caps.tolist()

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

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


    

    




ogaway
1000 loops, best of 3: 469 µs per loop
1000 loops, best of 3: 784 µs per loop
oyamad
10000 loops, best of 3: 73.2 µs per loop
1000 loops, best of 3: 341 µs per loop
keiikegami






    




keiikegami/deferred_acceptance.py:12: FutureWarning: comparison to `None` will result in an elementwise object comparison in the future.
  if caps == None:






    




---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
<ipython-input-13-15498db0296c> in <module>()
     15         print('NA')
     16     else:
---> 17         get_ipython().magic(u'timeit func(prop_prefs, resp_prefs, caps)')
     18     get_ipython().magic(u'timeit func(prop_prefs_list, resp_prefs_list, caps_list)')

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

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

//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_many-to-one/keiikegami/deferred_acceptance.pyc in deferred_acceptance(m_pref_input, f_pref_input, caps)
    127     #lapse = end - start
    128 
--> 129     if caps == [1] * f_popu:
    130         #print lapse
    131         return [list(m_match),f_match]

ValueError: The truth value of an array with more than one element is ambiguous. Use a.any() or a.all()

In [14]:

    

m, n = 50, 50
prop_prefs, resp_prefs, caps = random_prefs(m, n, return_caps=True)
prop_prefs_list, resp_prefs_list, caps_list \
    = prop_prefs.tolist(), resp_prefs.tolist(), caps.tolist()

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

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


    

    




ogaway
1000 loops, best of 3: 512 µs per loop
1000 loops, best of 3: 818 µs per loop
oyamad
10000 loops, best of 3: 71.6 µs per loop
1000 loops, best of 3: 341 µs per loop
bocchan
NA
1000 loops, best of 3: 267 µs per loop

In [15]:

    

m, n = 1000, 1000
prop_prefs, resp_prefs, caps = random_prefs(m, n, return_caps=True)
prop_prefs_list, resp_prefs_list, caps_list \
    = prop_prefs.tolist(), resp_prefs.tolist(), caps.tolist()

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

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


    

    




ogaway
10 loops, best of 3: 70.6 ms per loop
1 loops, best of 3: 197 ms per loop
oyamad
100 loops, best of 3: 4.29 ms per loop
10 loops, best of 3: 88.3 ms per loop
bocchan
NA
10 loops, best of 3: 62.1 ms per loop

In [16]:

    

import platform
print(platform.platform())


    

    




Darwin-13.4.0-x86_64-i386-64bit

In [17]:

    

import sys
print(sys.version)


    

    




2.7.10 |Anaconda 2.3.0 (x86_64)| (default, May 28 2015, 17:04:42) 
[GCC 4.2.1 (Apple Inc. build 5577)]

In [18]:

    

import numpy
print(numpy.__version__)


    

    




1.9.2

In [19]:

    

import numba
print(numba.__version__)


    

    




0.19.1

In [ ]: