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

こんにちは、リブセンスでデータサイエンティストをしている北原です。前回に続き今回もGale-Shapleyアルゴリズムを扱います。前回の記事で紹介した実装のボトルネックを把握し、少し改良することで計算量を大幅に削減します。コードはJuliaです。なお、今回の記事は下記の前回記事を読んでいることを前提として書かれています。 analytics.livesense.co.jp ボトルネック 選好順位判定行列 実装 実行時間の計測 まとめ ボトルネック まず、ボトルネックを見つけましょう。以下は前回記事で紹介した実装です。一見簡潔に書かれているものの、よく見ると計算時間がかかりそうなところが2箇所見つかります。 function gs(user1_prefs, user2_prefs, unmatched_user1_stack) matched_user2 = fill(-1, length(