one to many

中田竜明


In [1]:
include("da.jl")


Out[1]:
DA

ソースコードはこちら ソースコード

実行例:


In [2]:
DA.call_match([1 2; 2 1; 0 0], [1 2; 2 1; 0 0], [1, 1])


Out[2]:
([1,2],[1,2],[1,2,3])

引数2つだと1 to 1バージョンが呼ばれます.


In [3]:
DA.call_match([1 2; 2 1; 0 0], [1 2; 2 1; 0 0])


Out[3]:
([1,2],[1,2])

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]:
false

In [5]:
DA.stable_matching([1, 2], [1, 2], [2 1; 1 2; 0 0], [2 1; 1 2; 0 0])


Out[5]:
false

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]:
true

In [7]:
DA.stable_matching([2, 1], [1, 2], [2 1; 1 2; 0 0], [2 1; 1 2; 0 0])


Out[7]:
true

テストを行います


In [8]:
deferred_acceptance = DA.call_match
include("test_deferred_acceptance.jl")
print()


Test Summary: | Pass  Total
Testing da.jl |   10     10
WARNING: replacing module DA

通ったようです.

またスピードを計測してみます. まずは応募が実質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]:
PyObject <matplotlib.legend.Legend object at 0x32741b940>

マッチングの人数が2000以下の時にはほぼ等しいようです. つぎは人数を固定してそれぞれのアルゴリズムを計測します. まずは300人のとき,


In [12]:
using Matching


WARNING: using Matching.deferred_acceptance in module Main conflicts with an existing identifier.

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]:
speedtest_plot (generic function with 1 method)

In [14]:
speedtest_plot(300, 300)


Out[14]:
PyObject <matplotlib.legend.Legend object at 0x323da5e48>

one2oneのアルゴリズムのほうが少しだけ早いみたいです..? 次は4000人の時,


In [15]:
speedtest_plot(4000, 4000)


Out[15]:
PyObject <matplotlib.legend.Legend object at 0x311151828>

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]:
speedtest_plot2 (generic function with 1 method)

In [19]:
speedtest_plot2(100:200:2000, 100)


生徒側の人数にほぼ比例しているようです.

今まで定員をオーバーした時に大学にとって一番望ましくない人を弾くのに, 生徒の大学にとってのランキングを格納したヒープを使っていたのですが, ヒープを使わない時にはどれくらいの速度なのかを測るために新しいバージョンを作りました.


In [1]:
include("da.jl")


Out[1]:
DA

In [2]:
deferred_acceptance = DA.call_match
include("test_deferred_acceptance.jl")
print()


Test Summary: | Pass  Total
Testing da.jl |   10     10
WARNING: replacing module DA

テストに通ったので速度を計測します. 事実上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]:
PyObject <matplotlib.legend.Legend object at 0x313ed39e8>

one2oneがヒープを使用するone2manyとほぼ等しかったことから, かなり多くなったことがわかると思います...


In [13]:
@code_warntype DA.call_match(m_prefs, f_prefs, caps)


Variables:
  m_prefs::Array{Int64,2}
  f_prefs::Array{Int64,2}
  caps::Array{Int64,1}
  m::Int64
  n::Int64
  f_ranks::Array{Int64,2}
  m_pointers::Array{Int64,1}
  f_pointers::Array{Int64,2}
  f_holding::Array{Int64,1}
  m_matched_tf::BitArray{1}
  m_offers::Array{Int64,2}
  ##dims#8343::Tuple{Int64}
  ##dims#8344::Tuple{Int64,Int64}
  ##dims#8345::Tuple{Int64}
  ##args#8346::Tuple{Int64}
  ##dims#8347::Tuple{Int64,Int64}
  ##I#8348::Tuple{}

Body:
  begin  # /Users/neon/Desktop/S/zemi/DA_alg.jl/da.jl, line 10:
      GenSym(0) = (Base.arraysize)(m_prefs::Array{Int64,2},2)::Int64
      m = GenSym(0) # /Users/neon/Desktop/S/zemi/DA_alg.jl/da.jl, line 11:
      GenSym(1) = (Base.arraysize)(f_prefs::Array{Int64,2},2)::Int64
      n = GenSym(1) # /Users/neon/Desktop/S/zemi/DA_alg.jl/da.jl, line 13:
      f_ranks = (DA.get_ranks)(f_prefs::Array{Int64,2})::Array{Int64,2} # /Users/neon/Desktop/S/zemi/DA_alg.jl/da.jl, line 14:
      m_pointers = (Base.fill!)((Base.Array)(DA.Int,m::Int64)::Array{Int64,1},0)::Array{Int64,1} # /Users/neon/Desktop/S/zemi/DA_alg.jl/da.jl, line 15:
      f_pointers = (Base.fill!)((Base.Array)(DA.Int,m::Int64,n::Int64)::Array{Int64,2},0)::Array{Int64,2} # /Users/neon/Desktop/S/zemi/DA_alg.jl/da.jl, line 16:
      f_holding = (Base.fill!)((Base.Array)(DA.Int,n::Int64)::Array{Int64,1},0)::Array{Int64,1} # /Users/neon/Desktop/S/zemi/DA_alg.jl/da.jl, line 18:
      m_matched_tf = (Base.fill!)((Base.BitArray)(m::Int64)::BitArray{1},false)::BitArray{1} # /Users/neon/Desktop/S/zemi/DA_alg.jl/da.jl, line 19:
      m_offers = (Base.fill!)((Base.Array)(DA.Int,2,(Base.box)(Base.Int,(Base.add_int)(m::Int64,1)))::Array{Int64,2},0)::Array{Int64,2} # /Users/neon/Desktop/S/zemi/DA_alg.jl/da.jl, line 20:
      (Base.arrayset)(m_offers::Array{Int64,2},1,1,1)::Array{Int64,2} # /Users/neon/Desktop/S/zemi/DA_alg.jl/da.jl, line 22:
      (DA.da_match)(m::Int64,n::Int64,f_ranks::Array{Int64,2},m_prefs::Array{Int64,2},f_prefs::Array{Int64,2},m_pointers::Array{Int64,1},f_pointers::Array{Int64,2},m_matched_tf::BitArray{1},m_offers::Array{Int64,2},caps::Array{Int64,1},f_holding::Array{Int64,1})::Void # /Users/neon/Desktop/S/zemi/DA_alg.jl/da.jl, line 23:
      return (DA.convert_pointer_to_list)(m::Int64,n::Int64,f_pointers::Array{Int64,2},f_prefs::Array{Int64,2},caps::Array{Int64,1},f_holding::Array{Int64,1})::Tuple{Array{Int64,1},Array{Int64,1},Array{Int64,1}}
  end::Tuple{Array{Int64,1},Array{Int64,1},Array{Int64,1}}

In [16]:
Profile.clear()
@profile DA.call_match(m_prefs, f_prefs, caps)
Profile.print()


338 task.jl; anonymous; line: 447
 338 .../IJulia/src/IJulia.jl; eventloop; line: 143
  338 ...rc/execute_request.jl; execute_request_0x535c5df2; line: 183
   338 loading.jl; include_string; line: 282
    337 profile.jl; anonymous; line: 16
     21  ...zemi/DA_alg.jl/da.jl; call_match; line: 13
      13 ...zemi/DA_alg.jl/da.jl; get_ranks; line: 45
       6 multidimensional.jl; _unsafe_getindex; line: 193
       2 multidimensional.jl; _unsafe_getindex; line: 194
       2 multidimensional.jl; _unsafe_getindex; line: 195
      6  ...zemi/DA_alg.jl/da.jl; get_ranks; line: 47
      2  ...zemi/DA_alg.jl/da.jl; get_ranks; line: 49
     1   ...zemi/DA_alg.jl/da.jl; call_match; line: 16
      1 ...a/lib/julia/sys.dylib; call; (unknown line)
     315 ...zemi/DA_alg.jl/da.jl; call_match; line: 22
      48  ...emi/DA_alg.jl/da.jl; da_match; line: 156
       2  ...zemi/DA_alg.jl/da.jl; proceed_pointer!; line: 87
       10 ...zemi/DA_alg.jl/da.jl; proceed_pointer!; line: 88
       2  ...zemi/DA_alg.jl/da.jl; proceed_pointer!; line: 89
       28 ...zemi/DA_alg.jl/da.jl; proceed_pointer!; line: 91
       1  ...zemi/DA_alg.jl/da.jl; proceed_pointer!; line: 93
       5  ...zemi/DA_alg.jl/da.jl; proceed_pointer!; line: 94
      32  ...emi/DA_alg.jl/da.jl; da_match; line: 157
       1  ...emi/DA_alg.jl/da.jl; create_offers!; line: 102
       26 ...emi/DA_alg.jl/da.jl; create_offers!; line: 104
       1  ...emi/DA_alg.jl/da.jl; create_offers!; line: 106
       4  ...emi/DA_alg.jl/da.jl; create_offers!; line: 107
      235 ...emi/DA_alg.jl/da.jl; da_match; line: 158
       2   ...emi/DA_alg.jl/da.jl; decide_to_accept!; line: 133
       1   ...emi/DA_alg.jl/da.jl; decide_to_accept!; line: 134
       6   ...emi/DA_alg.jl/da.jl; decide_to_accept!; line: 137
       1   ...emi/DA_alg.jl/da.jl; decide_to_accept!; line: 138
       222 ...emi/DA_alg.jl/da.jl; decide_to_accept!; line: 139
        52 array.jl; findmax; line: 837
        1  array.jl; findmax; line: 838
        6  array.jl; findmax; line: 839
        8  array.jl; findmax; line: 841
        2  array.jl; findmax; line: 844
        40 multidimensional.jl; _unsafe_getindex; line: 193
        22 multidimensional.jl; _unsafe_getindex; line: 194
        84 multidimensional.jl; _unsafe_getindex; line: 195
       1   ...emi/DA_alg.jl/da.jl; decide_to_accept!; line: 141
       2   ...emi/DA_alg.jl/da.jl; decide_to_accept!; line: 148

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)


 30.673545 seconds (3.04 M allocations: 39.778 GB, 13.88% gc time)
  3.486124 seconds (69.00 k allocations: 1.492 GB, 11.10% gc time)
 29.057338 seconds (3.04 M allocations: 39.778 GB, 14.20% gc time)
  3.467252 seconds (69.00 k allocations: 1.492 GB, 10.56% gc time)
 27.840235 seconds (3.04 M allocations: 39.778 GB, 14.06% gc time)
  3.650230 seconds (69.00 k allocations: 1.492 GB, 9.94% gc time)
Out[8]:
([1673,4791,5677,4357,7571,971,9945,1215,8145,6782  …  2094,6830,5329,8388,5873,6920,9480,889,5601,4409],[0,2802,2047,1823,9309,6860,4617,6915,4647,5482  …  1316,7622,1617,8298,2606,8863,3005,6802,3523,3544])

findmaxが遅いみたいなので, その部分を実装しなおしました.


In [1]:
include("da.jl")


Out[1]:
DA

In [2]:
deferred_acceptance = DA.call_match
include("test_deferred_acceptance.jl")
print()


Test Summary: | Pass  Total
Testing da.jl |   10     10
WARNING: replacing module DA

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]:
PyObject <matplotlib.legend.Legend object at 0x3219ad940>

ヒープを使うバージョンとそれほど変わらないようです. もう少しだけ見てみます. 生徒数に対して大学数が少ない時,ヒープを使うバージョンでは,


In [5]:
include("da.jl")


WARNING: replacing module DA
Out[5]:
DA

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


WARNING: replacing module DA
Out[8]:
DA

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


WARNING: replacing module DA
Out[18]:
DA

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


標準ライブラリのヒープと同じか少し遅いようです.