1

ゲームのスコアランキングを考えます。各ユーザーに対して、スコアがただ一つ紐づいているとします。このとき、あるユーザーが与えられた時、全ユーザーの中で何番目のスコアを持っているかを知りたいとします。

このようなランキングのデータ構造は、取得と更新の計算量がトレードオフの関係にあると思います。

というのも、例えば各ユーザスコアデータについて、愚直にユーザーをキーにしたハッシュテーブルに入れておき、取得のタイミングで全テーブルを検索して、自分よりも大きなスコアを持つ要素をかぞえあげるとします。その場合、計算量は以下になります。

  • 更新系: O(1) ※hash index であった場合
  • 取得系: O(N)

また逆に、すべてのユーザーについてランキングをあらかじめ計算しておくとします。その場合、愚直に考えれば、全ての要素について見ていって、更新ユーザーの更新前と後の間の値のユーザースコアを持つユーザーのランクを、+/- 1 していくことで、更新できます。この場合、計算量は以下です。

  • 更新系: O(N)
  • 取得系: O(1) ※ hash index であった場合

質問

ランキングをデータ上に保持するとして、その取得系と更新系の計算量のうち、最悪の方について常に着目する場合、それはどこまで最小化できますか?

1
  • タイ(同率順位)は前の人のスコアを比較して、異なる値になってはじめて、単純に数を数えるだけになりますが、その場合はO(自分より高いスコアの人数を数えるだけ)とO'(自分と同じスコアか?を比較処理が加わる)のコスト差は考慮に入れる必要があるのでしょうか?
    – Чайка
    Commented 2018年11月17日 11:02

2 件の回答 2

1

スコアをキー、そのスコアを持つユーザーの人数を値とするマップを適当な平衡二分探索木で作り、木の各ノードに部分木のサイズを持たせれば、両方の操作をO(logN)で達成できると思います。

二分探索木では「左の子孫のキー値 < 親のキー値 < 右の子孫のキー値」のような性質が成り立ちますが、この時、右の部分木のサイズ(人数を全て足した数のことです)+1がそのまま順位となっています。

以下、上で説明したマップをm、ユーザーとスコアの対応表(配列やマップで持っておく)をscoreとすると2つの操作は次のように実現できます。

更新(ユーザーuのスコアをtに変更する)

  1. s = score[u]とする
  2. m[s]を1だけ減らす
  3. mにおいて、ルートからsまでのパス中のノード(s除く)で右の子に進むようなものが持つカウンタ(部分木のサイズ)を1だけ減らす
  4. m[t]を1だけ増やす
  5. mにおいて、ルートからtまでのパス中のノード(t除く)で右の子に進むようなものが持つカウンタを1だけ増やす
  6. score[u] = tとする

取得(ユーザーuの順位を取得)

  1. s = score[u]とする
  2. mでキーsを探索し、見つかったノードのカウンタ値+1を返す。

元々、二分探索木では取得・更新ともにO(logN)で達成できますが、それに加えて探索パス上でO(1)の操作を行っているだけなので、オーダーに影響はないです。

// これが最小の計算量かどうかは、申し訳ないですがちょっと分かりません・・・。

1
  • ポイントは、二分木の回転において回転後の部分木に紐付いているスコアの個数がその回転周辺のノードの情報だけで計算が可能であるからだと理解しました。
    – Yuki Inoue
    Commented 2018年11月20日 18:20
1

定量的な回答が出来ず申し訳ありません。

スコアを最高点(または∞)から最低点までのn個の区間に割り、その区間のいずれかにエントリーすると、計算量は充分考慮した式にできていませんが、

登録時は

  1. スコアは自分が管理するグループにエントリーして良い値か?→ O(n)
  2. 該当グループへの登録と該当グループが管理する人数の加算→P(1)

更新時は

  1. 変化後のスコアが自グループの管理内か?→O(1)
  2. スコアが自グループ管理範囲から外れたら、自分以外のグループへ移動→P(n)

取得系は

  1. グループの中にメンバーが居るか?→O(n)
  2. グループの中で何番目か?->P(Pの中のメンバー数)
  3. 自グループより上位のグループそれぞれのメンバー数の合計Q(n-1)

クラス化して、

  • 最大値
  • 最小値
  • 人数
  • エントリー用のハッシュ

をメンバー変数に

  • 引数のユーザーはエントリーされているか?
  • 引数のスコアが最大値から最小値の間か?
  • ユーザー名とスコアを引数にエントリーする
  • メンバー名とスコアの増減または新しいスコアを引数に、新しいスコアと自分の管理外のスコアに達したか?
  • ユーザー名を引数にエントリーから外し、人数を更新する

をメソッドにもつクラスの(インスタンスの)配列で管理出来る様な気がします。

人数やスコアの分布に依り、それぞれのグループが担うスコアの範囲を違えてあげれば(たとえば、正規分布に近い分布を示すなら、mean ±1σを細かくグループ化する、人数が多いならnを大きくするなどで)チューニングも容易で、比較的複雑にならずに最悪がO(N/n)近くまで高速化しやすいと思いますが、いかがでしょうか?

1
  • n = sqrt(N) でほどよくグループ化できれば、 O(sqrt(N)) までチューニング可能な手法だと理解しました。
    – Yuki Inoue
    Commented 2018年11月20日 18:22

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。