Gale-Shapleyアルゴリズムの実装 - LIVESENSE Data Analytics Blog

　こんにちは、リブセンスでデータサイエンティストをしている北原です。今回は、マッチングアルゴリズムとして有名なGale-Shapleyアルゴリズムを扱います。今回の記事ではアルゴリズムをそのまま実装したものを紹介し、次回の記事で計算速度を考慮した実装を紹介します。なお、弊社サービスknewが始まった頃にユーザーの急増に備えて書いたコードが元ネタですが、残念ながら今回および次回紹介するコードはknewでは使われていません。コードはJuliaとRです。下記の次回記事とセットでお読みください。

analytics.livesense.co.jp

Gale-Shapleyアルゴリズム
実装
まとめ

Gale-Shapleyアルゴリズム

　Gale-Shapleyアルゴリズムは、選好順序に基づき安定マッチングとなるペアを見つけることで、安定結婚問題を解くアルゴリズムです。アルゴリズムの特徴からDA(Deferred Acceptance)アルゴリズムと呼ばれることもあります。非常に有名なアルゴリズムなので、検索すると解説や実装が多数見つかると思います。ここでは最低限の説明のみ行います。

　安定結婚問題は、複数人からなる2つのグループがあり、個々人から相手グループの個々人に対する選好順序が定まっている時、安定マッチングを見つける問題です。安定マッチングとは、ブロッキングペアが存在しないようなマッチングです。ブロッキングペアとは互いにより選好順位が高いペアのことです。安定マッチングは複数存在し得ますが、Gale-Shapleyアルゴリズムによってプロポーズする側の希望を最も反映した安定マッチングが得られます。

　Gale-Shapleyアルゴリズムは、以下のような手順を繰り返します。

プロポーズする側の人全員を未マッチングリストに入れる
未マッチングリストが空になるまで以下を繰り返す
1. 未マッチングリストから選好順位リストが空でない人を取り出す($p$とする)
2. $p$の選好順位リストの中から一番選好順位の高い相手$q$にプロポーズ($p$の選好順位リストから$q$を削除)
  1. $q$が未マッチングの場合、$p$と仮マッチング
  2. $q$が$r$と仮マッチング済みの場合、$q$からみて$p$と$r$の選好順位を比較
    1. $p$の選好順位が高い場合、$r$との仮マッチングを破棄して$p$と仮マッチング
    2. $q$の選好順位が高い場合、$r$との仮マッチングを維持し、$p$を未マッチングリストに戻す

Gale-Shapleyアルゴリズムの計算量は、グループの人数のオーダーを$N$としたとき、$N$人の人が自分の選好リストに含まれる$N$人の人にプロポーズするので$O(N^2)$となります。

実装

　今回の記事では計算速度を考慮せず、前節で紹介したアルゴリズムをそのまま実装します。データ量が増えるにつれて計算時間がどうなるかも調べたいので、データ量の異なるサンプルデータを使います。アルゴリズムの実装コードは、これらのサンプルデータを読み込んで実行できるようにします。

　Gale-Shapleyアルゴリズムの実装は、入力データにどのような制約を課すかによって少し異なります。今回の記事では次のような入力データを想定します。

プロポーズする側とされる側の人数が異なることがある
プロポーズする側とされる側ともに、マッチングされない相手が存在しうる

knewでの利用を想定すると、男女で人数が異なることがあり得るし、希望条件とかけ離れた人とはマッチングさせないこともあり得るので、このような入力データとなっています。

　まずサンプルデータを作成するRコードは以下のようになります。パラメータでデータ量を調整できるようになっています。このコードのパラメータ例では、プロポーズする側の人数が5人、される側の人数が4人、最大で1割の相手とマッチングされない人が生じるようになっており、user1_prefs_n5m4.txtとuser2_prefs_n5m4.txtの2つのファイルが出力されます。n_scale変数を変更することでデータ量を調整することを想定しています。

　データフォーマットは少し特殊で、相手のIDが選好順に1列に並び、各ユーザーの区切りが-1でなされています。各人のIDは1から始まる連番です。例えば、ID1の人の選好順が2、5、3で、ID2の人の選好順が5、2であれば、2、5、3、-1、5、2が一列に並んだファイルが出力されます。データ量を増やした時にファイルサイズが大きくならないよう、このようなフォーマットにしています。

library(tidyverse)
set.seed(1)

# 人数パラメータ
n_scale <- 1
n_ <- 5
m_ <- 4
n <- n_ * n_scale
m <- m_ * n_scale

# マッチされない人数のパラメータ
n_cut <- as.integer(min(n, m) * 0.1)

# 選好順位のIDリスト作成
pref1_list <- map(1:n, ~ sample(1:m)[1:sample((m - n_cut):m, 1)])
pref2_list <- map(1:m, ~ sample(1:n)[1:sample((n - n_cut):n, 1)])

map(1:length(pref1_list), ~ c(pref1_list[[.]], -1)) %>% 
  unlist() %>% 
  data.frame() %>% 
  write_tsv(str_c("user1_prefs_n", n, "m", m, ".txt"), col_names = NA)
map(1:length(pref2_list), ~ c(pref2_list[[.]], -1)) %>% 
  unlist() %>% 
  data.frame() %>% 
  write_tsv(str_c("user2_prefs_n", n, "m", m, ".txt"), col_names = NA)

　Gale-Shapleyアルゴリズムの実行コマンドの例とJuliaコードは以下のようになります。実行するときは1番目の引数にプロポーズする側のファイルを指定し、2番目の引数にプロポーズする側のファイルを指定します。ファイルフォーマットが特殊なので、ファイル読み込み用の関数read_pref_file()を使って、ユーザーごとに選好順にIDが並んだベクトルを生成しています。gs()がGale-Shapleyアルゴリズムを実行する関数です。

$ julia gs1.jl user1_prefs_n5m4.txt user2_prefs_n5m4.txt

# gs1.jl
user1_fname = ARGS[1]
user2_fname = ARGS[2]

# ファイル読み込み
function read_pref_file(fname)
    user_prefs = (Vector{Int32})[]
    id_vec = (Int32)[]
    f = open(fname, "r")
    for l_ in eachline(f)
        l = parse(Int32, l_)
        if l != -1
            push!(id_vec, l)
        else
            push!(user_prefs, id_vec)
            id_vec = (Int32)[]
        end
    end
    close(f)
    return user_prefs
end
@time user1_prefs = read_pref_file(user1_fname)
@time user2_prefs = read_pref_file(user2_fname)

# マッチ相手のいないuser1のスタック
@time unmatched_user1_stack = collect(1:length(user1_prefs))

function gs(user1_prefs, user2_prefs, unmatched_user1_stack)
    # user2のマッチ相手を格納する配列（未マッチは-1）
    matched_user2 = fill(-1, length(user2_prefs))

    # user1の未マッチがなくなるまで続ける
    while length(unmatched_user1_stack) > 0
        proposer = pop!(unmatched_user1_stack)
        if !isempty(user1_prefs[proposer])
            # 選好順リストが空でない
            proposed = popfirst!(user1_prefs[proposer])
            if proposer in user2_prefs[proposed]
                # proposerがuser2の選好リストに存在する場合
                if matched_user2[proposed] < 0
                    # user2が未マッチの場合
                    matched_user2[proposed] = proposer
                else
                    # user2がマッチ済みの場合
                    current_user1_rank = findfirst(isequal(proposer), user2_prefs[proposed])
                    matched_user1_rank = findfirst(isequal(matched_user2[proposed]), user2_prefs[proposed])
                    if current_user1_rank < matched_user1_rank
                        # proposerの方が優先時順位が高い場合
                        push!(unmatched_user1_stack, matched_user2[proposed])
                        matched_user2[proposed] = proposer
                    else
                        # proposerの方が優先時順位が低い場合
                        push!(unmatched_user1_stack, proposer)
                    end
                end
            else
                # proposerがuser2の選好リストに存在しない場合
                push!(unmatched_user1_stack, proposer)
            end
        end
    end
    return matched_user2
end
@time matched_user2 = gs(user1_prefs, user2_prefs, unmatched_user1_stack)
# println(matched_user2)

　筆者の環境で@timeを使ってgs()の実行時間を計測すると、次のようになりました。データ量はプロポーズする側x人される側y人のとき、nxmyと表記しています。人数を1.5倍したときに2.25倍を超える3.4倍の時間がかかり、人数を2倍したときに4倍を超える7.9倍の時間がかかっています。つまり、$O(N^2)$ではなく、$O(N^3)$に近い計算量になっていることがうかがえます。

データ量	gs()の実行時間([sec])
n2500m2000	6
n3750m3000	20.5
n5000m4000	47.6

まとめ

　今回はGale-ShapleyアルゴリズムのJulia実装を紹介しました。今回の実装コードはあまり効率的ではなく、データ量が増えると急激に実行時間が増大します。組み合わせを扱うアルゴリズムでは、データ量が少ないサンプルデータなどでは計算がすぐに終わるので問題に気づきにくいですが、規模が大きい実データで実行すると時間がかかりすぎて問題になることがあるので注意が必要です。次回は少し改良して計算量を削減した実装を紹介します。