1 to many & many to 1の 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<:Integer}(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<:Integer}(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::Matrix{T}
end
Base.getindex(a::RowMajorMatrix, i::Integer, j::Integer) = 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 [1]:
type Matched2d
matched::AbstractArray{Integer, 1}
indptr::AbstractArray{Integer, 1}
end
function Matched2d(caps)
indptr = ones(Integer, length(caps)+1)
cms = cumsum(caps)
for i in 2:length(caps)+1
indptr[i] += cms[i-1]
end
return Matched2d(zeros(Integer, sum(caps)), indptr)
end
function Base.getindex(a::Matched2d, i::Integer, j::Integer)
if i < 1 || length(a.indptr) < i || j < 1 || a.indptr[i+1] - a.indptr[i] < j
throw(BoundsError)
end
return a.matched[a.indptr[i]+j-1]
end
function Base.setindex!(a::Matched2d, m::Integer, i::Integer, j::Integer)
if i < 1 || length(a.indptr) < i || j < 1 || a.indptr[i+1] - a.indptr[i] < j
throw(BoundsError)
end
a.matched[a.indptr[i]+j-1] = m
end
Out[1]:
In [4]:
function gale_shapley_T{T<:Int64}(
prop_prefs::AbstractArray{T, 2},
resp_prefs::AbstractArray{T, 2},
caps::AbstractArray{T, 1})
prop_prefs_T = RowMajorMatrix(prop_prefs)
resp_prefs_T = RowMajorMatrix(resp_prefs)
return gale_shapley(prop_prefs_T, resp_prefs_T, caps)
end
function gale_shapley{T<:Int64}(
prop_prefs::AbstractArray{T, 2},
resp_prefs::AbstractArray{T, 2},
caps::AbstractArray{T, 1})
# 第1次元（行）のサイズ = 受験者数, 大学数 を取得
prop_size = size(prop_prefs, 1)
resp_size = size(resp_prefs, 1)
# 仮マッチング済相手を入れる（0をunmatch）
prop_matched = zeros(Int64, prop_size)
resp_matched = Matched2d(caps)
n_props = zeros(Int64, resp_size)
resp_worst_matched = ones(Int64, resp_size)
# 未処理の受験者を入れておくスタック
stack = Stack(Int)
for i in prop_size:-1:1
push!(stack, i)
end
# 大学の選好を[受験者1の順位, 受験者2の順位,...] -> [1位の受験者の番号, 2位の受験者の番号,...] に変える
prop_rankings = argsort(resp_prefs)
# それぞれの受験者が何番目の大学まで受けたかを保存するリスト
proposed = zeros(Int64, prop_size)
while length(stack) != 0
prop = pop!(stack)
for i in proposed[prop]+1:resp_size
proposed[prop] += 1
# 順位表が終わりまで来たら探索終了
if prop_prefs[prop, i] == 0
break
end
resp = prop_prefs[prop, i]
worst = resp_worst_matched[resp]
# 大学が定員に達していない場合, 大学にとって受験者がacceptableならマッチ
if n_props[resp] < caps[resp] && prop_rankings[resp, prop+1] < prop_rankings[resp, 1]
prop_matched[prop] = resp
n_props[resp] += 1
if prop_rankings[resp, worst+1] < prop_rankings[resp, prop+1]
worst = resp
end
break
# 定員が埋まっている場合, 受験者が現在のworst受験者よりもランクが高ければマッチ
else
if prop_rankings[resp, prop+1] < prop_rankings[resp, worst+1]
prop_matched[prop] = resp
prop_matched[worst] = 0
push!(stack, worst)
worst = resp
# worstを探す
for p in 1:prop_size
if prop_matched[prop] == resp && prop_rankings[resp, worst+1] < prop_rankings[resp, p+1]
worst = p
end
end
break
end
end
end
end
n_props = 0
for p in 1:prop_size
resp = prop_matched[p]
n_props[resp] += 1
resp_matched[resp, n_props[resp]] = prop
end
return prop_matched, resp_matched.matched, resp_matched.indptr
end
Out[4]:
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 [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 [ ]: