50411


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

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

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

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

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

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

# 質問

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


CC BY-SA 4.0
2018-11-16T10:44:13.290
50381
2018-11-18T07:55:13.820
2018-11-18T05:14:18.883
754
754
question
アルゴリズム
ランキングの取得と更新の計算量のうち、最悪の計算量を最小化するには？


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

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

登録時は

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

更新時は

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

取得系は

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

クラス化して、

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

をメンバー変数に

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

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

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


CC BY-SA 4.0
2018-11-17T14:10:38.433
50400
2018-11-17T14:10:38.433
14745
50381
answer


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

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

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

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

  1. `s = score[u]`とする
  2. `m[s]`を１だけ減らす
  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)の操作を行っているだけなので、オーダーに影響はないです。

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


CC BY-SA 4.0
2018-11-18T07:55:13.820
50411
2018-11-18T07:55:13.820
13199
50381
answer