In [1]:
include("da.jl")
Out[1]:
ソースコードはこちら ソースコード
実行例:
In [2]:
DA.call_match([1 2; 2 1; 0 0], [1 2; 2 1; 0 0], [1, 1])
Out[2]:
引数２つだと1 to 1バージョンが呼ばれます.
In [3]:
DA.call_match([1 2; 2 1; 0 0], [1 2; 2 1; 0 0])
Out[3]:
stableかどうかチェックする関数も中身を変更しました.
In [4]:
DA.stable_matching([1, 2], [1, 2], [1, 2, 3], [2 1; 1 2; 0 0], [2 1; 1 2; 0 0])
Out[4]:
In [5]:
DA.stable_matching([1, 2], [1, 2], [2 1; 1 2; 0 0], [2 1; 1 2; 0 0])
Out[5]:
In [6]:
DA.stable_matching([2, 1], [1, 2], [1, 2, 3], [2 1; 1 2; 0 0], [2 1; 1 2; 0 0])
Out[6]:
In [7]:
DA.stable_matching([2, 1], [1, 2], [2 1; 1 2; 0 0], [2 1; 1 2; 0 0])
Out[7]:
テストを行います
In [8]:
deferred_acceptance = DA.call_match
include("test_deferred_acceptance.jl")
print()
通ったようです.
またスピードを計測してみます. まずは応募が実質1 to 1となるケースにおいて, 様々な人数に対して1tomanyと1to1のスピードを計測します.
In [9]:
one2one_times = Float64[]
one2many_times = Float64[]
for i in 1:20
m = i * 100
n = i * 100
m_prefs, f_prefs = DA.generate_random_preference_data(m, n)
caps = ones(Int, n)
_, elapsedtime, _, _, _ = @timed DA.call_match(m_prefs, f_prefs, caps)
push!(one2many_times, elapsedtime)
_, elapsedtime, _, _, _ = @timed DA.call_match(m_prefs, f_prefs)
push!(one2one_times, elapsedtime)
end
In [10]:
using PyPlot
In [11]:
plot(collect(1:100:2000), one2one_times, label="1 to 1")
plot(collect(1:100:2000), one2many_times, label="one to many")
PyPlot.xlabel("students num (= colleges num)")
legend()
Out[11]:
マッチングの人数が2000以下の時にはほぼ等しいようです. つぎは人数を固定してそれぞれのアルゴリズムを計測します. まずは300人のとき,
In [12]:
using Matching
In [13]:
function speedtest_plot(m, n)
one2one_times = Float64[]
one2many_times = Float64[]
for i in 1:20
m_prefs, f_prefs = DA.generate_random_preference_data(m, n)
caps = ones(Int, n)
_, elapsedtime, _, _, _ = @timed DA.call_match(m_prefs, f_prefs, caps)
push!(one2many_times, elapsedtime)
_, elapsedtime, _, _, _ = @timed DA.call_match(m_prefs, f_prefs)
push!(one2one_times, elapsedtime)
end
plot(one2one_times, label="1 to 1")
plot(one2many_times, label="one to many")
PyPlot.xlabel("test No.")
legend()
end
Out[13]:
In [14]:
speedtest_plot(300, 300)
Out[14]:
one2oneのアルゴリズムのほうが少しだけ早いみたいです..? 次は4000人の時,
In [15]:
speedtest_plot(4000, 4000)
Out[15]:
one2oneのほうが少し早いようです.
次はone2manyの受け入れ側の数を固定して計測します.
In [16]:
function speedtest_plot2(ms, n)
timess = Float64[]
for m in ms
times = Float64[]
s_prefs, c_prefs, caps = random_prefs(m, n, ReturnCaps)
for i in 1:10
_, elapsedtime, _, _, _ = @timed DA.call_match(s_prefs, c_prefs, caps)
push!(times, elapsedtime)
end
push!(timess, mean(times))
end
plot(ms, timess)
PyPlot.xlabel("students")
legend()
end
Out[16]:
In [19]:
speedtest_plot2(100:200:2000, 100)
生徒側の人数にほぼ比例しているようです.
今まで定員をオーバーした時に大学にとって一番望ましくない人を弾くのに, 生徒の大学にとってのランキングを格納したヒープを使っていたのですが, ヒープを使わない時にはどれくらいの速度なのかを測るために新しいバージョンを作りました.
In [1]:
include("da.jl")
Out[1]:
In [2]:
deferred_acceptance = DA.call_match
include("test_deferred_acceptance.jl")
print()
テストに通ったので速度を計測します. 事実上one2one, つまりcaps=ones(Int, n)の形のマッチングに対して大学側、生徒側の数を等しく100から2000まで変えたものについて計測します.
In [11]:
one2one_times = Float64[]
one2many_times = Float64[]
for i in 1:20
m = i * 100
n = i * 100
m_prefs, f_prefs = DA.generate_random_preference_data(m, n)
caps = ones(Int, n)
_, elapsedtime, _, _, _ = @timed DA.call_match(m_prefs, f_prefs, caps)
push!(one2many_times, elapsedtime)
_, elapsedtime, _, _, _ = @timed DA.call_match(m_prefs, f_prefs)
push!(one2one_times, elapsedtime)
end
In [12]:
using PyPlot
plot(collect(1:100:2000), one2one_times, label="1 to 1")
plot(collect(1:100:2000), one2many_times, label="one to many")
PyPlot.xlabel("students num (= colleges num)")
legend()
Out[12]:
one2oneがヒープを使用するone2manyとほぼ等しかったことから, かなり多くなったことがわかると思います...
In [13]:
@code_warntype DA.call_match(m_prefs, f_prefs, caps)
In [16]:
Profile.clear()
@profile DA.call_match(m_prefs, f_prefs, caps)
Profile.print()
In [8]:
m, n = 10000, 10000
m_prefs, f_prefs = DA.generate_random_preference_data(m, n)
caps = ones(Int, n)
@time DA.call_match(m_prefs, f_prefs, caps)
@time DA.call_match(m_prefs, f_prefs)
@time DA.call_match(m_prefs, f_prefs, caps)
@time DA.call_match(m_prefs, f_prefs)
@time DA.call_match(m_prefs, f_prefs, caps)
@time DA.call_match(m_prefs, f_prefs)
Out[8]:
findmaxが遅いみたいなので, その部分を実装しなおしました.
In [1]:
include("da.jl")
Out[1]:
In [2]:
deferred_acceptance = DA.call_match
include("test_deferred_acceptance.jl")
print()
In [3]:
one2one_times = Float64[]
one2many_times = Float64[]
for i in 1:20
m = i * 100
n = i * 100
m_prefs, f_prefs = DA.generate_random_preference_data(m, n)
caps = ones(Int, n)
_, elapsedtime, _, _, _ = @timed DA.call_match(m_prefs, f_prefs, caps)
push!(one2many_times, elapsedtime)
_, elapsedtime, _, _, _ = @timed DA.call_match(m_prefs, f_prefs)
push!(one2one_times, elapsedtime)
end
In [4]:
using PyPlot
plot(collect(1:100:2000), one2one_times, label="1 to 1")
plot(collect(1:100:2000), one2many_times, label="one to many")
PyPlot.xlabel("students num (= colleges num)")
legend()
Out[4]:
ヒープを使うバージョンとそれほど変わらないようです. もう少しだけ見てみます. 生徒数に対して大学数が少ない時,ヒープを使うバージョンでは,
In [5]:
include("da.jl")
Out[5]:
In [7]:
for k in 1:5
one2many_times = Float64[]
for i in 1:30
m = i * 1000
n = 10
m_prefs, f_prefs = DA.generate_random_preference_data(m, n)
caps = fill(div(m, n), n)
_, elapsedtime, _, _, _ = @timed DA.call_match(m_prefs, f_prefs, caps)
push!(one2many_times, elapsedtime)
end
plot(collect(1000:1000:30000), one2many_times)
end
PyPlot.xlabel("students num (= colleges num)")
legend()
ヒープを使わないバージョンでは,
In [8]:
include("da.jl")
Out[8]:
In [9]:
for k in 1:5
one2many_times = Float64[]
for i in 1:30
m = i * 1000
n = 10
m_prefs, f_prefs = DA.generate_random_preference_data(m, n)
caps = fill(div(m, n), n)
_, elapsedtime, _, _, _ = @timed DA.call_match(m_prefs, f_prefs, caps)
push!(one2many_times, elapsedtime)
end
plot(collect(1000:1000:30000), one2many_times)
end
PyPlot.xlabel("students num (= colleges num)")
legend()
差が出てきました.
標準ライブラリのヒープの速度が不安だったので自分で実装してみたところ,
In [18]:
include("da.jl")
Out[18]:
In [20]:
using PyPlot
for k in 1:5
one2many_times = Float64[]
for i in 1:30
m = i * 1000
n = 10
m_prefs, f_prefs = DA.generate_random_preference_data(m, n)
caps = fill(div(m, n), n)
_, elapsedtime, _, _, _ = @timed DA.call_match(m_prefs, f_prefs, caps)
push!(one2many_times, elapsedtime)
end
plot(collect(1000:1000:30000), one2many_times)
end
PyPlot.xlabel("students num (= colleges num)")
legend()
標準ライブラリのヒープと同じか少し遅いようです.