In [1]:
using DA
using Plots
plotlyjs()
Out[1]:
one to oneとみなせる場合についてテストを行います.
In [2]:
Pkg.test("DA")
In [3]:
num = 10^4
prop_prefs, resp_prefs = generate_random_prefs(num, num)
caps = ones(Int, num)
deferred_acceptance(prop_prefs, resp_prefs, caps)
Profile.clear()
@profile deferred_acceptance(prop_prefs, resp_prefs, caps)
Profile.print()
時間の殆どをマッチング前のデータ整形に使っていることがわかります.(matchings.jlのline43)
ここで,one-to-oneとみなせるmany-to-many(capsがすべて1のケース)に関して, マッチングの規模を変えながらその実行時間を計測してみます.
In [4]:
Pkg.checkout("DA", "forcomparison")
In [5]:
Pkg.status("DA")
このままだとブランチの変更が反映されないのでNotebookをRestartします.
In [1]:
using DA
using Plots
plotlyjs()
Out[1]:
In [2]:
num_range = [50, 100, 200, 500, 700, 1000]
loop = 20
elapsed = Array{Float64}(loop, length(num_range), 4)
for (i, num) in enumerate(num_range)
caps = ones(Int, num)
for l in 1:loop
prop_prefs, resp_prefs = generate_random_prefs(num, num)
_, elapsed[l, i, 1], _, _ = @timed deferred_acceptance(prop_prefs, resp_prefs)
_, elapsed[l, i, 2], _, _ = @timed deferred_acceptance_rev(prop_prefs, resp_prefs, caps)
_, elapsed[l, i, 3], _, _ = @timed deferred_acceptance_rev_offheap(prop_prefs, resp_prefs, caps)
_, elapsed[l, i, 4], _, _ = @timed deferred_acceptance(prop_prefs, resp_prefs, caps)
end
end
In [3]:
plot(num_range,
log.(squeeze(mean(sort(elapsed, 1)[1:loop-10, :, :], 1), 1)),
xlabel="num",
ylabel="time (log scale)",
title="average time",
labels=reshape(["one-to-one", "v2017", "v2017+DS.heap", "v2016"], (1, 4)))
Out[3]:
In [4]:
plot(num_range,
squeeze(mean(sort(elapsed, 1)[1:loop-10, :, :], 1), 1),
xlabel="num",
ylabel="time",
title="average time",
labels=reshape(["one-to-one", "v2017", "v2017+DS.heap", "v2016"], (1, 4)))
Out[4]:
one-to-oneとして実装したものがやはり一番早いようです.
(v2017+DS.heapはDataStructuresのbinary_maxheapを使用したバージョン, v2017は自分で実装したHeapを使用したバージョンです.)
In [5]:
Pkg.checkout("DA", "master")
In [6]:
Pkg.status("DA")
preferenceからrankを作る関数(内の代入)に一番時間がかかっているので,rankの型をUInt16型にしてみました.
関数の引数に制限がかかってしまいますが(many-to-manyのケースだとnum_respsとsum(prop_caps)が共に2^16-1= 65535以下),少し早くなるはずです.
one-to-oneとみなせるmany-to-oneのケースについて,提案側・受ける側の人数numを変えて実行時間を測ってみます.
In [1]:
using DA
using Plots
plotlyjs()
Out[1]:
In [2]:
num_range = collect(100:200:1100)
loop = 20
elapsed = Array{Float64}(loop, length(num_range))
for (i, num) in enumerate(num_range)
caps = ones(Int, num)
for l in 1:loop
prop_prefs, resp_prefs = generate_random_prefs(num, num)
_, elapsed[l, i], _, _ = @timed deferred_acceptance(prop_prefs, resp_prefs, caps)
end
end
In [3]:
plot(num_range,
squeeze(mean(sort(elapsed, 1)[1:loop-15, :], 1), 1),
xlabel="scale",
ylabel="time",
title="average time")
Out[3]:
ちなみに以下の図がone-to-one用に実装したdeferred acceptance algorithmの処理時間のグラフです.
one-to-oneとして実装したものと比べ,人数が多いところでは二倍ほど早くなりました.
In [ ]: