concurrentskiplistmapソート：値の比較によって実行できますか？

Question

ゲームでは、ユーザーのリストを維持し、スコアでソートしようとしているため、特定の時間にリストをクエリして（たとえば）スコアごとにトップ10ユーザーを返すことができます。このリストはスレッドセーフでなければなりません。ユーザー名の文字列をキーとして使用することを想定しています。値は、等しいものを実装し、displayNameやスコアなどのプロパティを備えたユーザーオブジェクトです。したがって、ユーザーオブジェクトには、スコア属性を比較してその位置を決定する比較メソッドがあります。

私はこれに同時にKiplistMapを使用することを検討していますが、私が知ることができる限り、マップ（セットとは対照的に）はキーを使用してソートします。リストをユーザーオブジェクトのスコアプロパティでソートしたいのですが、特定のユーザーにアクセスしてスレッドからスコア属性を変更できる必要があるため、マップを使用します。

キーに自分のコンパレータを使用すると、比較のために関連する価値にアクセスできるとは思わないので、私の問題が解決するとは思われません。 concurrentskiplistsetを使用できますが、リストにアクセスして個々のユーザーのスコアを変更することは（毎回反復する必要があるため）、高価な操作です（想像します）。

誰かがこれを達成する方法を提案することができるでしょうか？

Answer 1

いいえ、できないと思います。注文に使用されるコンパレータは、インデックス作成に使用されるものと同じです。おそらく2つのコレクションを維持する必要があります。 1つは、ユーザーのスコアを維持するために、名前でユーザーを参照するためのスコアです。

Answer 2

get(key) コンパレータに依存します（キーを見つけることができるように）。あなたは依存するコンパレータを提案します get(key) （キーのマッピング値にアクセスするには、それに基づいて比較します）。それは必然的に無限の再帰につながります スタックオーバーフロー （明るい面では、適切なウェブサイトに投稿しています!!）

Answer 3

マイケルは正しいです、あなたもあなたのケーキを食べてそれを食べることはできません;）

3つの選択肢があると思います。

1. マップを使用して、ユーザーのスコアの更新が迅速になり、ソート時に最高のスコアを見つけるときに価格を支払います。
2. スコアごとにソートを使用して、最高のスコアを見つけることが速くなるように並べ替えますが、ユーザーのスコアを更新するときは価格を支払う必要があります
3. 2つのデータ構造を維持して、1と2の最高の状態を持つことができます。たとえば、スコアでソートされたセットに実際のデータがありますが、ユーザー名のマッピングを維持してセットなどにインデックスを付けます。そうすれば、常にソートされたスコアがあり、ユーザーのスコアの更新は検索ではなく、単なる検索です。これに支払う価格は、2つの場所で複製情報を維持していることであり、特に同時アクセスを考慮すると、両方の場所が常に同期して更新されるようにすることが難しい場合があります。

私は1〜2の間でより速いと仮定しません。私はあなたの予想される使用法でそれらを試して、最悪のことを確認するために測定します。

あなたが本当にトップNスコアにしか興味がない場合は、そのリストを個別に維持する可能性があります。そのため、ユーザー名のマップをすべての人に得点させるだけでなく、トップスコア（およびそのユーザー）の小さなセットも維持します。誰かのスコアを追加/更新するたびに、トップスコアリストに対してスコアをチェックしてください。そして、そこに最小のスコアリストよりも大きい場合は、それを追加して下部のスコアを追加してください。これは上記の提案3に似ていますが、オーバーヘッドが少なく、おそらく維持が容易です。