2012-11-20 24 views
13

Jeśli chcę zachować uporządkowaną listę w Firebase, wydaje mi się, że najlepiej jest ręcznie przypisać priorytet do każdego elementu na mojej liście. Oznacza to, że jeśli wstawię lub usuniemy przedmiot z listy, muszę zaktualizować priorytety wszystkich następujących po nim elementów. W przypadku pozycji na początku listy oznacza to aktualizację każdego elementu na liście. Czy w tym przypadku istnieje lepsza struktura danych lub algorytm?Wydajność uporządkowanej listy w Firebase

+0

Edytowałem to, aby poprosić o lepsze d.s. lub algorytm - jedyna uczciwa odpowiedź na pytanie "czy to wystarczająco szybkie?" to "czy profilowałeś to?" – djechlin

+0

Jaki jest algorytm sortowania? Alfabetyczny? Liczbowy? Według znacznika czasu? Zastanawiam się nad tymi mglistymi pytaniami na temat Firebase i zazwyczaj stwierdzam, że są one o wiele łatwiejsze do rozwiązania, gdy dokładnie zidentyfikuję pożądane zachowanie. – Kato

Odpowiedz

4

Możesz utworzyć uporządkowaną listę, odpowiednio ustawiając priorytet elementów. Pozycje na liście są sortowane leksykalnie według priorytetu lub jeśli priorytet może zostać sparsowany do wartości liczbowej.

Jeśli chcesz wstawić elementy na środek istniejącej listy, modyfikowanie priorytetów istniejących elementów działałoby, ale byłoby okropnie nieefektywne. Lepszym rozwiązaniem jest wybór priorytetu między dwoma elementami, w których chcesz wstawić wartość i ustawić priorytet dla nowego elementu.

Na przykład, jeśli masz element 1 z priorytetem "a", a element 2 z priorytetem "b", możesz wstawić element 3 między dwoma z priorytetem "aa" (lub "aq", "az", itp).

Z naszego doświadczenia wynika, że ​​najczęściej przy tworzeniu uporządkowanej listy niekoniecznie znasz pozycję na liście, którą chcesz wcześniej wstawić. Na przykład, jeśli tworzysz tablicę liderów do gry, nie wiesz z góry, że chcesz umieścić nowy wynik na 3. miejscu, raczej wiesz, że chcesz go wstawić w dowolnym miejscu, zdobywając 10000 punktów (która może być trzecia). W takim przypadku wystarczy ustawić priorytet dla wyniku. Zobacz nasz przykład tablicy liderów tutaj: https://www.firebase.com/tutorial/#example-leaderboard

+3

Dzięki za odpowiedź tak szybko. W tym przypadku chciałbym utworzyć listę "przeciągnij i upuść", aby kolejność została zdefiniowana przez użytkownika. Podoba mi się pomysł umieszczenia priorytetu między dwoma pożądanymi przedmiotami, ale utknąłem na jednej rzeczy: skąd wiesz, co to jest następny element, gdy używasz wywołania zwrotnego 'child_added'? Dostajesz tylko poprzedni element, a nie następny. –

+1

Czy kiedykolwiek znalazłeś dobre rozwiązanie dla listy zamówień arbitralnych @RadfordSmith? –

0

Klejnot Ruby ranked_model ma interesujące podejście do tego problemu. Używa liczby całkowitej pozycji, jak wiele innych implementacji "aktów jako list", ale nie polega na przepisywaniu wszystkich liczb całkowitych na każdym ruchu pozycji. Zamiast tego rozdziela szeroko liczby całkowite, dzięki czemu każda aktualizacja może dotyczyć tylko jednego lub dwóch wierszy. Może warto przejrzeć plik readme i kod, aby sprawdzić, czy to podejście może się tutaj zmieścić.

Powiązane problemy