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

Question

Документация redis для ZADD гласит, что операция является O (log N ).

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

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

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

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

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

Answer 1

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

---

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

Answer 2

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

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