notebook.community

Edit and run



In [1]:

    
using Matching



In [2]:

    
urls = [
    "https://raw.githubusercontent.com/EikiTakigawa/Deferred-Acceptance/a74feec27a0720a4821cfd3827701201d73072b9/DA_Many_to_1.jl",
    "https://raw.githubusercontent.com/IoriS/Ex03/b2623c18aa4c24571cb2028339283450721c8ff2/deferred_acceptance.jl",
    "https://raw.githubusercontent.com/keiikegami/DA_Julia/435e4fb243faf371dc9d3db2c4006e4b0ff64730/ikegamida_mm.jl",
    "https://raw.githubusercontent.com/M-okb/DA-Matching/793c2eceb3a4b9b88c074a98da715a344bb9cf13/many_to_one.jl",
    "https://raw.githubusercontent.com/myuuuuun/oyama_seminar2016/31cc89df572213ac1d7dc4da320b8d2697932fb1/exercise/ex03/matching.jl",
    "https://raw.githubusercontent.com/NlGG/Economics/c9ac87dc1ce2acdbf08a30be89986e2124685e86/deferred_acceptance.jl",
    "https://raw.githubusercontent.com/nswa17/DA_alg.jl/522791c03866a812a610de68618ff105b33bd55c/da.jl",
    "https://raw.githubusercontent.com/oyataku1/Matching/4298b98e530e326aba05fbae6c9fdba39a058a8a/deferred_acceptance.jl",
    "https://raw.githubusercontent.com/SUZUKITAISHI/matching/701096f5bc327a4f619e4f9985cc4674afb6869c/my_Gale_Shap.jl",
    "https://raw.githubusercontent.com/13tsuyoshi/matching/79049ddc672d9795bec6bceab8209cf40a974d30/Many_to_one.jl",
]
function_names = [
    "deferred_acceptance",
    "deferred_acceptance",
    "ikegamida_mm",
    "okb_DA_algo",
    "Matching.gale_shapley_T",
    "deferred_acceptance",
    "DA.call_match",
    "deferred_acceptance",
    "my_Gale_Shap",
    "deferred_acceptance",
];



In [3]:

    
file_names = [split(url, "/")[end] for url in urls]
dir_names = [split(url, "/")[4] for url in urls]
paths = [join((dir_name, file_name), "/")
    for (dir_name, file_name) in zip(dir_names, file_names)];



In [4]:

    
module_names = [
    replace(
        replace(dir_name, "-", "_"),
        r"^[1-9]+", ""
    )
    for dir_name in dir_names
];



In [5]:

    
function download_files(overwrite::Bool=false)
    for (url, dir_name, path) in zip(urls, dir_names, paths)
        if !isdir(dir_name)
            mkdir(dir_name)
        end
        
        if !isfile(path) || overwrite
            download(url, path)
        end
    end
end









    Out[5]:





download_files (generic function with 2 methods)



In [6]:

    
download_files()



In [7]:

    
function load_module(module_name, path)
    module_name = parse(module_name)
    eval(Expr(:toplevel, :(
        module ($module_name)
        include($path)
        end
    ), module_name, path))
end









    Out[7]:





load_module (generic function with 1 method)



In [8]:

    
for (module_name, path) in zip(module_names, paths)
    load_module(module_name, path)
end









    



WARNING: deprecated syntax "resp_matched [" at /Users/oyama/tmp/DA160704/EikiTakigawa/DA_Many_to_1.jl:32.
Use "resp_matched[" instead.

WARNING: deprecated syntax "resp_matched [" at /Users/oyama/tmp/DA160704/EikiTakigawa/DA_Many_to_1.jl:48.
Use "resp_matched[" instead.



In [9]:

    
module oyamad
deferred_acceptance = Main.Matching.deferred_acceptance
end









    Out[9]:





oyamad



In [10]:

    
functions = Dict{ASCIIString, Function}()

for (module_name, function_name) in zip(module_names, function_names)
    eval(parse(
        "functions[\"" * module_name * "\"] = " * module_name * "." * function_name
    ))
end

functions["oyamad"] = oyamad.deferred_acceptance;



In [11]:

    
functions









    Out[11]:





Dict{ASCIIString,Function} with 11 entries:
  "NlGG"         => NlGG.deferred_acceptance
  "oyamad"       => Matching.deferred_acceptance
  "EikiTakigawa" => EikiTakigawa.deferred_acceptance
  "myuuuuun"     => myuuuuun.Matching.gale_shapley_T
  "IoriS"        => IoriS.deferred_acceptance
  "SUZUKITAISHI" => SUZUKITAISHI.my_Gale_Shap
  "nswa17"       => nswa17.DA.call_match
  "M_okb"        => M_okb.okb_DA_algo
  "keiikegami"   => keiikegami.ikegamida_mm
  "tsuyoshi"     => tsuyoshi.deferred_acceptance
  "oyataku1"     => oyataku1.deferred_acceptance

Testing One-to-One



In [12]:

    
m, n = 10, 5
srand(1234)
m_prefs, f_prefs = random_prefs(m, n)

prop_matches_oy, resp_matches_oy = oyamad.deferred_acceptance(m_prefs, f_prefs)

for (k, fn) in functions
    println(k)
    try
        @time fn(m_prefs, f_prefs)
    catch
        println("  NA")
        continue
    end
    @time prop_matches, resp_matches = fn(m_prefs, f_prefs)
    @time fn(m_prefs, f_prefs)
    if prop_matches == prop_matches_oy && resp_matches == resp_matches_oy
        println("  OK")
    else
        println("  returned: $prop_matches; expected: $prop_matches_oy")
        println("  returned: $resp_matches; expected: $resp_matches_oy")
    end
end









    



NlGG
  0.229103 seconds (153.23 k allocations: 7.536 MB, 2.62% gc time)
  0.004232 seconds (326 allocations: 25.250 KB)
  0.000031 seconds (272 allocations: 21.906 KB)
  OK
oyamad
  0.000016 seconds (49 allocations: 7.016 KB)
  0.000010 seconds (51 allocations: 7.078 KB)
  0.000008 seconds (49 allocations: 7.016 KB)
  OK
EikiTakigawa
  0.096480 seconds (64.00 k allocations: 2.882 MB)
  0.000051 seconds (212 allocations: 29.391 KB)
  0.000037 seconds (210 allocations: 29.328 KB)
  OK
myuuuuun
  NA
IoriS
  0.099193 seconds (27.41 k allocations: 1.298 MB)
  0.000034 seconds (201 allocations: 16.734 KB)
  0.000017 seconds (199 allocations: 16.672 KB)
  OK
SUZUKITAISHI
  0.103860 seconds (35.90 k allocations: 1.662 MB)
  0.000524 seconds (230 allocations: 19.375 KB)
  0.000031 seconds (228 allocations: 19.313 KB)
  OK
nswa17
  0.149516 seconds (95.04 k allocations: 4.463 MB)
  0.000013 seconds (27 allocations: 2.344 KB)
  0.000007 seconds (25 allocations: 2.281 KB)
  OK
M_okb
  0.064192 seconds (38.24 k allocations: 1.763 MB)
  0.000007 seconds (14 allocations: 1.500 KB)
  0.000004 seconds (12 allocations: 1.438 KB)
  OK
keiikegami
  0.374485 seconds (256.04 k allocations: 11.029 MB, 1.77% gc time)
  0.000681 seconds (922 allocations: 63.469 KB)
  0.000541 seconds (920 allocations: 63.406 KB)
  OK
tsuyoshi
  0.555930 seconds (359.19 k allocations: 16.631 MB)
  0.001069 seconds (1.75 k allocations: 777.813 KB)
  0.001109 seconds (1.75 k allocations: 777.750 KB)
  OK
oyataku1
  0.240126 seconds (172.69 k allocations: 7.193 MB, 3.45% gc time)
  0.000063 seconds (468 allocations: 37.172 KB)
  0.000082 seconds (466 allocations: 37.109 KB)
  OK

Testing Many-to-One



In [13]:

    
m, n = 10, 5
c = 2  # Number of caps
srand(1234)
m_prefs, f_prefs = random_prefs(m, n)
caps = Array(Int, n)
fill!(caps, c)

prop_matches_oy, resp_matches_oy, indptr_oy =
    oyamad.deferred_acceptance(m_prefs, f_prefs, caps)
for j in 1:n
    sort!(sub(resp_matches_oy,
              indptr_oy[j]:indptr_oy[j+1]-1)
    )
end

for (k, fn) in functions
    println(k)
    try
        @time fn(m_prefs, f_prefs, caps)
    catch
        println("  NA")
        continue
    end
    @time prop_matches, resp_matches, indptr = fn(m_prefs, f_prefs, caps)
    @time fn(m_prefs, f_prefs, caps)
    
    for j in 1:n
        sort!(sub(resp_matches,
                  indptr[j]:indptr[j+1]-1)
        )
    end
    if prop_matches == prop_matches_oy && resp_matches == resp_matches_oy &&
        indptr == indptr_oy
        println("  OK")
    else
        println("  returned: $prop_matches; expected: $prop_matches_oy")
        println("  returned: $resp_matches; expected: $resp_matches_oy")
    end
end









    



NlGG
  0.000404 seconds (202 allocations: 17.078 KB)
  0.000017 seconds (205 allocations: 17.172 KB)
  0.000012 seconds (202 allocations: 17.078 KB)
  OK
oyamad
  0.000014 seconds (47 allocations: 6.906 KB)
  0.000010 seconds (50 allocations: 7.000 KB)
  0.000007 seconds (47 allocations: 6.906 KB)
  OK
EikiTakigawa
  0.000478 seconds (172 allocations: 22.375 KB)
  0.000033 seconds (175 allocations: 22.469 KB)
  0.000023 seconds (172 allocations: 22.375 KB)
  OK
myuuuuun
  NA
IoriS
  0.000289 seconds (205 allocations: 17.359 KB)
  0.000024 seconds (208 allocations: 17.453 KB)
  0.000020 seconds (205 allocations: 17.359 KB)
  OK
SUZUKITAISHI
  0.000444 seconds (280 allocations: 23.719 KB)
  0.000039 seconds (283 allocations: 23.813 KB)
  0.000073 seconds (280 allocations: 23.719 KB)
  OK
nswa17
  0.081710 seconds (82.32 k allocations: 3.563 MB)
  0.000028 seconds (45 allocations: 3.250 KB)
  0.000008 seconds (42 allocations: 3.156 KB)
  OK
M_okb
  0.000262 seconds (10 allocations: 1.328 KB)
  0.000004 seconds (13 allocations: 1.422 KB)
  0.000003 seconds (10 allocations: 1.328 KB)
  OK
keiikegami
  0.000940 seconds (862 allocations: 59.828 KB)
  0.000224 seconds (865 allocations: 59.922 KB)
  0.000214 seconds (862 allocations: 59.828 KB)
  OK
tsuyoshi
  0.002049 seconds (1.31 k allocations: 543.219 KB)
  0.000767 seconds (1.27 k allocations: 540.828 KB)
  0.000572 seconds (1.26 k allocations: 540.734 KB)
  OK
oyataku1
  0.000884 seconds (451 allocations: 36.391 KB)
  0.000044 seconds (454 allocations: 36.484 KB)
  0.000038 seconds (451 allocations: 36.391 KB)
  OK

Performance Comparison



In [14]:

    
function performance(m::Int, n::Int, caps::Vector{Int}, rng::AbstractRNG)
    m_prefs, f_prefs = random_prefs(rng, m, n)
    
    times = Array(Float64, length(functions))
    names = Array(ASCIIString, length(functions))
    #allocs = Array(Int, length(functions))
    
    for (i, (k, fn)) in enumerate(functions)
        time = 0.
        try
            fn(m_prefs, f_prefs, caps)
            fn(m_prefs, f_prefs, caps)
            _, time, _, _ = @timed fn(m_prefs, f_prefs, caps)
        catch
            time = 9999.
        end
        times[i] = time
        names[i] = k
        #allocs[i] = alloc
    end
    
    indices = sortperm(times)
    for i in indices
        println(names[i])
        @printf("  %0.9f seconds\n", times[i])
    end
end

performance(m::Int, n::Int, caps::Vector{Int}, seed::Int) =
    performance(m, n, caps, MersenneTwister(seed))
performance(m::Int, n::Int, caps::Vector{Int}) =
    performance(m, n, caps, Base.GLOBAL_RNG)









    Out[14]:





performance (generic function with 3 methods)



In [15]:

    
seed = 1234









    Out[15]:





1234



In [16]:

    
m, n = 500, 500
caps = ones(Int, n)  # one-to-one
performance(m, n, caps, seed)









    



M_okb
  0.003770121 seconds
oyamad
  0.005121670 seconds
nswa17
  0.005824514 seconds
IoriS
  0.040685155 seconds
EikiTakigawa
  0.064808207 seconds
oyataku1
  0.089338253 seconds
SUZUKITAISHI
  0.108241933 seconds
tsuyoshi
  0.542399106 seconds
NlGG
  0.586721696 seconds
keiikegami
  2.206599403 seconds
myuuuuun
  9999.000000000 seconds



In [17]:

    
m = 100
c = 10
n = div(m, c)
caps = Array(Int, n)
fill!(caps, c)
performance(m, n, caps, seed)









    



M_okb
  0.000011129 seconds
oyamad
  0.000024366 seconds
nswa17
  0.000042805 seconds
IoriS
  0.000727181 seconds
NlGG
  0.000759908 seconds
oyataku1
  0.000949126 seconds
EikiTakigawa
  0.001442077 seconds
SUZUKITAISHI
  0.002651004 seconds
tsuyoshi
  0.007402193 seconds
keiikegami
  0.007408547 seconds
myuuuuun
  9999.000000000 seconds



In [18]:

    
m = 500
c = 50
n = div(m, c)
caps = Array(Int, n)
fill!(caps, c)
performance(m, n, caps, seed)









    



oyamad
  0.000120200 seconds
M_okb
  0.000120583 seconds
nswa17
  0.000238932 seconds
NlGG
  0.010082437 seconds
keiikegami
  0.038535363 seconds
EikiTakigawa
  0.105584519 seconds
IoriS
  0.147566926 seconds
oyataku1
  0.206051797 seconds
tsuyoshi
  0.349435162 seconds
SUZUKITAISHI
  3.265877307 seconds
myuuuuun
  9999.000000000 seconds



In [19]:

    
m = 1000
c = 50
n = div(m, c)
caps = Array(Int, n)
fill!(caps, c)
performance(m, n, caps, seed)









    



oyamad
  0.000374656 seconds
M_okb
  0.000429230 seconds
nswa17
  0.000777612 seconds
NlGG
  0.092031945 seconds
keiikegami
  0.153811151 seconds
EikiTakigawa
  0.511887711 seconds
IoriS
  0.541142028 seconds
oyataku1
  0.608581231 seconds
tsuyoshi
  0.849483178 seconds
SUZUKITAISHI
  12.089946372 seconds
myuuuuun
  9999.000000000 seconds



In [20]:

    
m = 1000
c = 100
n = div(m, 2*c)
caps = Array(Int, n)
fill!(caps, c)
performance(m, n, caps, seed)









    



oyamad
  0.000207096 seconds
M_okb
  0.000330993 seconds
nswa17
  0.000345872 seconds
NlGG
  0.029665631 seconds
keiikegami
  0.051590795 seconds
EikiTakigawa
  0.647007821 seconds
IoriS
  0.826486500 seconds
oyataku1
  0.997225794 seconds
tsuyoshi
  2.316589905 seconds
SUZUKITAISHI
  33.079156536 seconds
myuuuuun
  9999.000000000 seconds



In [21]:

    
m = 1000
c = 100
n = div(m, c) * 2
caps = Array(Int, n)
fill!(caps, c)
performance(m, n, caps, seed)









    



M_okb
  0.000203420 seconds
oyamad
  0.000345198 seconds
nswa17
  0.000358421 seconds
tsuyoshi
  0.048579840 seconds
myuuuuun
  0.065706607 seconds
NlGG
  0.136128421 seconds
keiikegami
  0.154921927 seconds
IoriS
  0.589332416 seconds
oyataku1
  0.593708216 seconds
EikiTakigawa
  0.776728034 seconds
SUZUKITAISHI
  9.345274726 seconds



In [ ]: