Выполнение упорядоченного списка в Firebase

Если я хочу сохранить упорядоченный список в Firebase, кажется, что лучший способ сделать это - вручную назначить приоритет каждому элементу в моем списке. Это означает, что если я вставляю или удаляю элемент из списка, я должен обновлять приоритеты всех последующих за ним элементов. Для элемента в начале списка это означает обновление каждого элемента в списке. Существует ли более эффективная структура данных или алгоритм для использования в этом случае?

Ответы

Ответ 1

Вы можете создать упорядоченный список, установив приоритет элементов соответствующим образом. Элементы в списке упорядочиваются лексиграфически по приоритету, или если приоритет может быть проанализирован на число, по числовому значению.

Если вы хотите вставить элементы в середину существующего списка, изменение приоритетов существующих элементов будет работать, но будет ужасно неэффективным. Лучше всего выбрать приоритет между двумя элементами, в которые вы хотите вставить значение, и установить этот приоритет для нового элемента.

Например, если у вас есть элемент 1 с приоритетом "a" и элемент 2 с приоритетом "b", вы можете вставить элемент 3 между ними с приоритетом "aa" (или "aq", "az" и т.д.).

В нашем опыте, в большинстве случаев, когда вы создаете упорядоченный список, вы не обязательно знаете позицию в списке, который хотите вставить элемент заранее. Например, если вы создаете Лидерскую доску для игры, вы заранее не знаете, что хотите поместить новый счет в 3-е место в списке, скорее вы знаете, что хотите вставить его в любую позицию, которую получает 10000 очков (что может оказаться третьим). В этом случае, просто установив приоритет для оценки, это выполнится. См. Наш пример совета лидеров здесь: https://www.firebase.com/tutorial/#example-leaderboard

Ответ 2

У Ruby gem ranked_model есть интересный подход к этой проблеме. Он использует целое число позиции, как и многие другие реализации "действует как список", но не полагается на повторную запись всех целых чисел в каждой позиции. Вместо этого он просто расщепляет целые числа, и поэтому каждое обновление может влиять только на одну или две строки. Возможно, стоит просмотреть readme и код, чтобы увидеть, подходит ли этот подход здесь.