Gale-Shapley Algorithmを実装する. 詳細: https://github.com/OyamaZemi/exercises2016/tree/master/ex02
In [1]:
using DataStructures
include("matching_tools.jl")
Out[1]:
In [2]:
function argsort{T<:Int}(array::AbstractVector{T})
#=1次元配列をArgument Sortする
配列をSortした後, その要素が元あった場所のIndexを返す
例: [1, 3, 4, 2, 0] -> [5, 1, 4, 2, 3]
タイの順位には非対応
=#
array_with_index = Array{T}(length(array), 2)
for i in 1:length(array)
array_with_index[i, 1] = array[i]
array_with_index[i, 2] = i
end
sorted_array_with_index = sortrows(array_with_index, by=x->x[1])
return sorted_array_with_index[:, 2]
end
array = [1, 3, 4, 2, 0]
println(argsort(array))
次に, 2次元に対応させる
In [3]:
function argsort{T<:Int}(array::AbstractArray{T, 2})
#=2次元配列をArgument Sortする
それぞれの行毎にargsortする.
例: [1 3 4 2 0;
1 2 0 4 3]
-> [5 1 4 2 3;
3 1 2 5 4]
=#
row = size(array)[1]
col = size(array)[2]
argsorted = Array{T}(size(array))
for i in 1:row
out = argsort(squeeze(array[i, :], 1))
for j in 1:col
argsorted[i, j] = out[j]
end
end
return argsorted
end
array = [1 3 4 2 0; 1 2 0 4 3]
println(argsort(array))
In [4]:
type RowMajorMatrix{T} <: AbstractMatrix{T}
data::AbstractMatrix{T}
end
Base.getindex(a::RowMajorMatrix, i::Int, j::Int) = a.data[j, i]
function Base.size(a::RowMajorMatrix)
col_size = size(a.data)[1]
row_size = size(a.data)[2]
return (row_size, col_size)
end
Out[4]:
In [5]:
function gale_shapley_T{T<:Int64}(m_prefs::AbstractArray{T, 2}, f_prefs::AbstractArray{T, 2})
m_prefs_T = RowMajorMatrix(m_prefs)
f_prefs_T = RowMajorMatrix(f_prefs)
return gale_shapley(m_prefs_T, f_prefs_T)
end
function gale_shapley{T<:Int64}(m_prefs::AbstractArray{T, 2}, f_prefs::AbstractArray{T, 2})
# 第1次元（行）のサイズ = 男, 女の人数 を取得
m_size = size(m_prefs, 1)
f_size = size(f_prefs, 1)
# 仮マッチング済相手を入れる（0をunmatch）
m_matched = zeros(Int64, m_size)
f_matched = zeros(Int64, f_size)
# 未処理の男を入れておくスタック
stack = Stack(Int)
for i in m_size:-1:1
push!(stack, i)
end
# 女の選好を[男1の順位, 男2の順位,...] -> [1位の男の番号, 2位の男の番号,...] に変える
male_rankings = argsort(f_prefs)
# それぞれの男が何番目の女まで告白したかを保存するリスト
proposed = zeros(Int64, m_size)
while length(stack) != 0
male = pop!(stack)
for i in proposed[male]+1:f_size
proposed[male] += 1
# 順位表が終わりまで来たら探索終了
if m_prefs[male, i] == 0
break
end
female = m_prefs[male, i]
# 女性が誰ともマッチしていない場合, 女性にとって男性がacceptableならマッチ
if f_matched[female] == 0 && male_rankings[female, male+1] < male_rankings[female, 1]
m_matched[male] = female
f_matched[female] = male
break
# 誰かとマッチしている場合, 男性が現在のパートナーよりもランクが高ければマッチ
else
current_partner = f_matched[female]
if male_rankings[female, male+1] < male_rankings[female, current_partner+1]
m_matched[male] = female
f_matched[female] = male
m_matched[current_partner] = 0
push!(stack, current_partner)
break
end
end
end
end
return m_matched, f_matched
end
Out[5]:
In [6]:
m_prefs = [2 1 3 4 0; 1 3 2 4 0; 2 3 4 1 0]'
f_prefs = [2 1 3 0; 3 2 1 0; 1 3 2 0; 2 3 1 0]'
println(m_prefs)
println(f_prefs)
println(gale_shapley_T(m_prefs, f_prefs))
In [7]:
srand(613)
m_prefs2, f_prefs2 = random_prefs(4, 3, allow_unmatched=true)
m_prefs2 = m_prefs2
f_prefs2 = f_prefs2
println(m_prefs2)
println(f_prefs2)
println(gale_shapley_T(m_prefs2, f_prefs2))
In [8]:
function gale_shapley2_T{T<:Int64}(m_prefs::AbstractArray{T, 2}, f_prefs::AbstractArray{T, 2})
m_prefs_T = RowMajorMatrix(m_prefs)
f_prefs_T = RowMajorMatrix(f_prefs)
return gale_shapley2(m_prefs_T, f_prefs_T)
end
function gale_shapley2{T<:Int64}(m_prefs::AbstractArray{T, 2}, f_prefs::AbstractArray{T, 2})
# 第1次元（行）のサイズ = 男, 女の人数 を取得
m_size = size(m_prefs, 1)
f_size = size(f_prefs, 1)
# 仮マッチング済相手を入れる（0をunmatch）
m_matched = zeros(Int64, m_size)
f_matched = zeros(Int64, f_size)
# 未処理の男を入れておくスタック
unmatched = ones(Bool, m_size)
# 女の選好を[男1の順位, 男2の順位,...] -> [1位の男の番号, 2位の男の番号,...] に変える
male_rankings = argsort(f_prefs)
# それぞれの男が何番目の女まで告白したかを保存するリスト
proposed = zeros(Int64, m_size)
while sum(unmatched) != 0
for male in 1:m_size
if unmatched[male]
for i in proposed[male]+1:f_size
proposed[male] += 1
# 順位表が終わりまで来たら探索終了
if m_prefs[male, i] == 0
unmatched[male] = false
break
end
female = m_prefs[male, i]
# 女性が誰ともマッチしていない場合, 女性にとって男性がacceptableならマッチ
if f_matched[female] == 0 && male_rankings[female, male+1] < male_rankings[female, 1]
m_matched[male] = female
f_matched[female] = male
unmatched[male] = false
break
# 誰かとマッチしている場合, 男性が現在のパートナーよりもランクが高ければマッチ
else
current_partner = f_matched[female]
if male_rankings[female, male+1] < male_rankings[female, current_partner+1]
m_matched[male] = female
f_matched[female] = male
m_matched[current_partner] = 0
unmatched[male] = false
unmatched[current_partner] = true
break
end
end
end
end
end
end
return m_matched, f_matched
end
Out[8]:
In [9]:
m_prefs = [2 1 3 4 0; 1 3 2 4 0; 2 3 4 1 0]'
f_prefs = [2 1 3 0; 3 2 1 0; 1 3 2 0; 2 3 1 0]'
println(m_prefs)
println(f_prefs)
println(gale_shapley2_T(m_prefs, f_prefs))
In [10]:
function make_preferences(loop::Int=1000, m_size::Int=1000, f_size::Int=1000, seed::Int64=617)
srand(seed)
m_prefs = Array{Int64}(loop, f_size+1, m_size)
f_prefs = Array{Int64}(loop, m_size+1, f_size)
for i in 1:loop
m_pref, f_pref = random_prefs(m_size, f_size, allow_unmatched=true)
m_prefs[i, :, :] = m_pref
f_prefs[i, :, :] = f_pref
end
return m_prefs, f_prefs
end
function speedtest(func::Function, m_prefs, f_prefs, loop)
m_size = size(m_prefs, 3)
f_size = size(f_prefs, 3)
for i in 1:loop
m_pref = reshape(m_prefs[i, :, :], f_size+1, m_size)
f_pref = reshape(f_prefs[i, :, :], m_size+1, f_size)
end
end
Out[10]:
In [12]:
m_size = 1000
f_size = 1000
loop = 100
@time m_prefs, f_prefs = make_preferences(loop, m_size, f_size)
@time speedtest(gale_shapley_T, m_prefs, f_prefs, loop)
@time speedtest(gale_shapley2_T, m_prefs, f_prefs, loop)
Stackの方が遅いかと思ったが, ほとんど誤差の範囲
In [15]:
srand(613)
m_prefs2, f_prefs2 = random_prefs(1000, 1000, allow_unmatched=true)
Profile.clear()
@profile gale_shapley_T(m_prefs2, f_prefs2)
Profile.print()
In [ ]: