In [1]:
using DA
昨年のnotebookはこちら
1対1マッチングについて, (male-proposingと仮定して)マッチしていない男性をスタックに載せるなどの変更を加えました. 結果的に,
while any(男性がマッチしていないかのbool配列)の部分をwhile スタックの長さの変数 > 0とすることができ,pop!(待ち男性のスタック)とすればよい)特にマッチングループ終盤で不必要なループ・条件式の評価がなくなりました.(プロファイルを確認したところこの部分に時間がかかっていたようです)
テストを行います.
In [2]:
Pkg.test("DA")
In [3]:
m, n = 10, 10
m_prefs, f_prefs = generate_random_prefs(m, n)
m_matched, f_matched = deferred_acceptance(m_prefs, f_prefs)
Out[3]:
In [4]:
@time deferred_acceptance(m_prefs, f_prefs)
Out[4]:
タイムを計測してみます.
In [5]:
for (m, n) in [(100, 100), (200, 200), (500, 500), (1000, 1000)]
m_prefs, f_prefs = generate_random_prefs(m, n)
m_matched, f_matched = @time deferred_acceptance(m_prefs, f_prefs)
end
In [6]:
Profile.clear()
m, n = 10^4, 10^4
m_prefs, f_prefs = generate_random_prefs(m, n)
deferred_acceptance(m_prefs, f_prefs)
@profile deferred_acceptance(m_prefs, f_prefs)
Profile.print()
実行時間のほとんどが前処理(選好順に並んでいる男性リストを男性の番号順に選好を並べる作業)にかかっているようです.
次に男性・女性の数numに対して, 関数の速さをプロットしてみます.
In [7]:
using Plots
In [8]:
range = 100:100:2000
loop = 10
elapsed = Array(Float64, loop, length(range))
for (i, m) in enumerate(range)
for l in 1:loop
m_prefs, f_prefs = generate_random_prefs(m, m)
_, elapsed[l, i], _, _ = @timed deferred_acceptance(m_prefs, f_prefs)
end
end
In [9]:
print(vec(mean(sort(elapsed, 1)[1:loop-3, :], 1)))
print(collect(range))
In [10]:
plot(range,
vec(mean(sort(elapsed, 1)[1:loop-3, :], 1)),
xlabel="num",
ylabel="ms",
legend=false,
title="average time")
Out[10]:
In [11]:
m, n = 10000, 10000
m_prefs, f_prefs = generate_random_prefs(m, n)
m_matched, f_matched = deferred_acceptance(m_prefs, f_prefs)
@time deferred_acceptance(m_prefs, f_prefs)
Out[11]:
全体的に以前のコードより3~10倍早くなっています.
In [ ]: