Redis: лучше ли ZADD, чем O(logN), когда вставленный элемент находится в начале или в конце?

В документации Redis для ZADD указано, что операция выполняется O(log N).

Однако кто-нибудь знает, лучше ли ZADD, чем O(log N), когда вставленный элемент находится в начале или в конце порядка сортировки?

Например. для некоторых реализаций это может быть O (1).

В частности, в руководстве по redis указано, что:

Отсортированные наборы реализованы через двухпортовую структуру данных, содержащую как список пропуска, так и хэш-таблицу, поэтому каждый раз, когда мы добавляем элемент, Redis выполняет операцию O(log(N)) .

Кажется правдоподобным изменить список пропуска, чтобы он поддерживал O(k) вставки в начале и в конце, где k — максимальный уровень списка пропуска.


redis sortedset skip-lists
person Peter Skirko    schedule 21.08.2011    source источник

Ответы (2)


arrow_upward
3
arrow_downward

Я разместил этот вопрос на веб-сайте Redis, и Питер Нордхуис предоставил там ответ, который я публикую здесь:

Это правильно. Отсортированный набор опирается на ГСЧ для определения количества уровней на узел (это вероятностная структура данных). Вставка/удаление элемента в начале списка пропуска может быть O(1), в то время как теоретическая производительность в наихудшем случае равна O(N) (при этом каждый узел имеет одинаковый уровень). Однако амортизированная временная сложность составляет O (log N), если принять во внимание распределение уровней между узлами.

person Peter Skirko    schedule 22.08.2011
comment
Итак... ответ таков: если вы вставите в начало списка, вы получите O(1)? - person Daren; 16.02.2015

arrow_upward
0
arrow_downward

Есть ли связь между k и log(N)? Если они связаны постоянным коэффициентом, вы на самом деле ничего не изменили. (Я не знаю, существует ли такая связь, но она выглядит вполне правдоподобной, учитывая, что страница википедии на эту тему, по-видимому, такая связь в построении слоя. OTOH, страница не ссылается на доказательство, и мне сейчас не хочется выводить его вручную, так что это может быть только предположением.)

Кроме того, в целом тот факт, что алгоритм в целом равен O(log N), не мешает некоторым частным случаям быть лучше (например, O(1)).

person Donal Fellows    schedule 22.08.2011
comment
Мне также показалось интересным, что списки пропуска могут иметь проблемы с локализацией памяти (согласно resnet. uoregon.edu/~gurney_j/jmpc/skiplist.html). Это доказывает, что вы должны всегда измерять, а не гадать. - person Donal Fellows; 22.08.2011
comment
с тех пор прошло много времени, однако я нахожу вопрос действительно интересным, если я хочу вставить в redis существующий отсортированный набор, который построен отсортированным, может быть интересно узнать, каким образом лучше отправлять команды: реверс, прямо, как будто я строю бинарное дерево...? - person Daren; 08.07.2014