javascript - Firebaseでの順序付きリストのパフォーマンス

Question

Firebaseで順序付きリストを維持したい場合は、リスト内の各アイテムに手動で優先度を割り当てるのが最善の方法のようです。つまり、リストにアイテムを挿入またはリストから削除した場合、それに続くすべてのアイテムの優先度を更新する必要があります。リストの先頭にあるアイテムの場合、これはリスト内のすべてのアイテムを更新することを意味します。この場合に使用する、よりパフォーマンスの高いデータ構造またはアルゴリズムはありますか？

Answer 1

要素の優先度を適切に設定することで、順序付きリストを作成できます。リスト内の項目は、優先度によって字句順に並べ替えられます。優先度を数値に解析できる場合は、数値によって並べ替えられます。

既存のリストの途中にアイテムを挿入する場合、既存のアイテムの優先順位を変更することは機能しますが、ひどく非効率的です。より良いアプローチは、値を挿入する2つのアイテムの間で優先順位を選択し、新しいアイテムにその優先順位を設定することです。

たとえば、優先度が「a」の要素1と優先度が「b」の要素2がある場合、優先度が「aa」（または「aq」、「az」など）の2つの間に要素3を挿入できます。

私たちの経験では、順序付きリストを作成する場合、ほとんどの場合、アイテムを挿入するリスト内の位置が事前にわかっているとは限りません。たとえば、ゲームのリーダーボードを作成している場合、リストの3番目に新しいスコアを配置するかどうかは事前にわかりません。むしろ、スコア10000で得られる位置に挿入する必要があります。 （これはたまたま3番目かもしれません）。この場合、スコアに優先度を設定するだけでこれを実現できます。こちらのリーダーボードの例をご覧ください： https ：//www.firebase.com/tutorial/#example-leaderboard

Answer 2

Ruby gemのranked_modelには、この問題に対する興味深いアプローチがあります。他の多くの「リストとして機能する」実装と同様に位置整数を使用しますが、各位置移動ですべての整数を書き換えることに依存しません。代わりに、整数を大きく離して配置するため、各更新は1行または2行にのみ影響する可能性があります。このアプローチがここに適合するかどうかを確認するために、readmeとコードを調べる価値があるかもしれません。