Leistung einer geordneten Liste in Firebase

Question

Wenn ich eine geordnete Liste in Firebase verwalten möchte, scheint es die beste Möglichkeit zu sein, jedem Element in meiner Liste manuell eine Priorität zuzuweisen. Das heißt, wenn ich ein Element aus der Liste einfüge oder entferne, muss ich die Prioritäten aller folgenden Elemente aktualisieren. Für einen Eintrag am Anfang der Liste bedeutet dies, dass alle Einträge in der Liste aktualisiert werden. Gibt es in diesem Fall eine bessere Datenstruktur oder einen besseren Algorithmus?

Answer 1

Sie können eine geordnete Liste erstellen, indem Sie die Priorität der Elemente entsprechend festlegen. Elemente in einer Liste werden lexigraphisch nach Priorität sortiert, oder wenn die Priorität durch einen numerischen Wert in eine Zahl geparst werden kann.

Wenn Sie Elemente in die Mitte einer vorhandenen Liste einfügen möchten, würde das Ändern der Prioritäten der vorhandenen Elemente funktionieren, wäre aber furchtbar ineffizient. Ein besserer Ansatz besteht darin, eine Priorität zwischen den beiden Elementen auszuwählen, an denen Sie den Wert einfügen und diese Priorität für das neue Element festlegen möchten.

Wenn Sie beispielsweise Element 1 mit der Priorität "a" und Element 2 mit der Priorität "b" hätten, könnten Sie Element 3 mit der Priorität "aa" (oder "aq", "az") einfügen. etc).

Nach unseren Erfahrungen wissen Sie in den meisten Fällen, wenn Sie eine geordnete Liste erstellen, nicht unbedingt die Position in der Liste, in die Sie das Element vorher einfügen möchten. Wenn Sie zum Beispiel eine Rangliste für ein Spiel erstellen, wissen Sie nicht im Voraus, dass Sie eine neue Punktzahl als 3. in die Liste aufnehmen möchten. Sie wissen also, dass Sie sie an jeder Position einfügen möchten, die 10000 erreicht (was vielleicht der dritte sein könnte). In diesem Fall genügt es, die Priorität auf die Punktezahl zu setzen. Sehen Sie unser Leaderboard Beispiel hier: https://www.firebase.com/tutorial/#example-leaderboard

Answer 2

Das Rubin Juwel ranked_model hat einen interessanten Ansatz für dieses Problem. Es verwendet eine Positions-Ganzzahl wie viele andere "Acts als Liste" -Implementierungen, aber es ist nicht darauf angewiesen, alle Ganzzahlen bei jeder Positionsbewegung neu zu schreiben. Stattdessen werden die Ganzzahlen weit voneinander entfernt, sodass sich jede Aktualisierung nur auf eine oder zwei Zeilen auswirkt. Vielleicht lohnt es sich, in der Readme und im Code nachzusehen, ob dieser Ansatz hier passt.