プログラミング(主にPython2.7)とか機械学習とか

2013-11-05

キャラソートのアルゴリズムについて調べた

﹁キャラソート﹂とは

以下のページのようにキャラ(あるいは人物などの何らかの要素)を2つずつ表示して﹁どちらか好きか？﹂という質問に連続で答えていくことで全体のランキングを作るWebサービス(﹁◯◯キャラソート﹂、﹁◯◯ソート﹂など)が様々な作品について存在している ●東方キャラソート f:id:sucrose:20131026133026p:plain

どんなアルゴリズムを使っているのかに興味がわいたので調べてみました

ソートのアルゴリズム

以下の解説記事を読むとわかるようにマージソートやヒープソートといったソートアルゴリズムを人間にそのままやらせているらしいただし単純にソートアルゴリズム使うだけではなく、計算量を減らすため引き分けなどの場合にはそのペアのデータを一つにまとめたものとして扱うように工夫している ●ハロプロ・ソートの解説 ●咲-saki-キャラソート - 勤々惰々 ●管理しないsabakan » キャラソートアルゴリズムについてソートアルゴリズムは理論上、最悪計算量が最低でも\(\mathrm{O}(n \log n)\)となっている大雑把に考えると\(n \log n\)(の定数倍)回弱ぐらいの比較がソートするのに必要とみなしてよい例えば50個の要素をソートしようとしたと仮定する単純に\(n = 50\)として計算するとおよそ\(n \log_2 n = 282.2\)となりもしかしたら300回近くの比較を求められることになってしまう冒頭で紹介した東方キャラソートは100キャラ以上が登録されていて、全部を計算するのに何回の比較が必要なのか考えたくなくなるレベルである(ただし現在では作品名で限定したサブセットで実行できるようになっている

上位\(k\)件の部分ソート

Twitterなどで実際公開されているキャラソートの結果を見ると、当然ながら上位10件などの限られた件数についてのみ結果が示されているこのことから全体のソートではなく上位\(k\)件のソートを使えばもっと比較回数を減らせるんじゃないかと思って、アルゴリズムを調べてみた ●選択アルゴリズム - Wikipedia 日本語だと上のWikipediaの記事の﹁k個の最小・最大要素の選択﹂が詳しい ●sorting - Optimal algorithm for returning top k values from an array of length N - Stack Overflow ●Selection algorithm - Wikipedia, the free encyclopedia ●Partial sorting - Wikipedia, the free encyclopedia 簡単に調べた限りでは、以下のような4つのアルゴリズムが見つけられた (一)サイズを\(k\)に制限したヒープや(平衡)2分探索木などを使えばだいたい\(\mathrm{O}(n \log k)\) (二)ヒープの構築は\(\mathrm{O}(n)\)だった気がするので、\(k\)番目までをヒープソート的に取り出せば、\(\mathrm{O}(n + k \log n)\)ぐらいでもできそう (三)分割統治を使ったアルゴリズム、たとえばクイックソート風の部分ソートで\(k\)番目より後の要素だけのパーティションを無視する方法が計算量的には小さくて\(\mathrm{O}(n + k \log k)\)になるらしい (四)ペア同士で対戦していくトーナメントを使う方法 \(\mathrm{O}(n + k \log n)\) (一)詳細をググってもあまり見つからなかったのだけど、たぶんこの記事のアルゴリズム？＞ Finding Kth Minimum (partial ordering) – Using Tournament Algorithm (Malkit's Blog) (二)トーナメントの結果から以下のような順番に取っていく(あまり詳細を理解していない (一)1位 (二)1位に負けたものの中から最大 (三)1位負けたのと2位に負けたものの和集合の中から最大 (四)1位負けたのと2位に負けたと3位に負けたものの和集合の中から最大 (五)同様の手順を\(k\)番目の要素をとるまで続ける色々調べたんですが、ソートするアイテム数は多めに見積もっても100程度だと思うので、人間の比較回数を最小にするには計算量のオーダーだけでなく定数倍の部分が重要そうですね…… クイックソートだと、ピボットとの比較が連続して起こるので、答える人間側が飽きてしまいやすそうとか他にも問題がありそうです

まとめ

キャラソートの比較回数多すぎ！上位10件だけとかを求めるようにすれば、比較回数がかなり減りそうだと思うんで誰かに試してみてほしいです実際のキャラソートがキャラ数に対してどれぐらいの比較が必要になってるか確かめてみるために、がんばってソート回数が最大や最小になるように挑戦してみたのですが、操作ミスとかして最大最小を出すのはちょっとめんどくさかったです今回の話に似た話として、ソートの入力として意地悪なものを与えると非常に遅くなる場合がある(Javaなど)ことが知られていて、これについては以下の記事が面白かったです ●クイックソート殺し ●汎用ソート殺しそういえば診断メーカーみたいに簡単にキャラソートを作れるWebサービスとかって需要ありそうなのにないんですかね？