質問: ランキングをデータ上に保持するとして、その取得系と更新系の計算量のうち、最悪の方について常に着目する場合、それはどこまで最小化できますか?
回答: 定量的な回答が出来ず申し訳ありません。 スコアを最高点(または∞)から最低点までの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)近くまで高速化しやすいと思いますが、いかがでしょうか?