Какие корректировки структуры данных связанных списков дадут мне быстрый случайный поиск?

Question

В настоящее время я использую дважды связанный список (C ++ std::list) хранить кучу записей, у каждого из которых есть уникальный целочисленный идентификатор. Связанный список создается в отсортированном порядке, так что в списке следующий элемент всегда имеет больше уникального идентификатора, чем его предшественник.

Проблема, с которой я сталкиваюсь, заключается в том, что иногда мне нужно быстро вставить элемент в его относительную отсортированную позицию, и использование простого связанного списка означает, что эта операция - $ O (n) $, что вызывает у меня проблемы с производительностью. Как правило, это означает, что я хочу использовать что -то вроде бинарного дерева (C ++ std::map), однако, я также в зависимости от следующей функции вдвойне связанного списка для хорошей производительности:

• Способность объединить смежный раздел из одного связанного списка в другой в $ O (1) $ времени. (Амортизированный $ o (1) $ или $ o ( log log n) $ будет достаточно хорошим.)

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

Я хотел бы найти структуру замены данных или увеличение в дважды связанный список, который позволит мне продолжать разбивать целые разделы от одного списка в другой в постоянное время, но позвольте мне найти отсортированную позицию, в которую можно вставить новую запись в лучшем случае $ O (n) $.

Другие операции включают вперед и обратную итерацию по всем пунктам. Индексы записей начинаются в нуле и растут вверх по направлению к 64 битам, как правило, последовательно, и код хорошо работает в таких случаях. Иногда некоторые записи не доступны до последующих, именно вставка этих пропущенных записей вызывает проблемы с производительностью сейчас.

Один из возможных подходов, который возникает для меня, - это кэшировать местоположение нескольких индексов. Кэш будет недействительным всякий раз, когда сплайс удаляет предметы, которые могут перекрывать кэшированные записи. С этим кэшем, вместо того, чтобы выполнять линейный поиск, поиск может начать с итератора точки кэша, уникальный индекс которого ближе всего к тому, чья позиция ищет. Тем не менее, я хотел бы более полно использовать функцию смежных записей. Я также думал об иерархическом связанном списке, где у меня есть связанный список высшего уровня смежных регионов, где каждый регион представляет собой связанный список записей, которые последовательны, но я не видел чистый способ адаптировать связанный список, чтобы предоставить это функциональность. Возможно, что -то подобное было сделано раньше? Я считаю, что списки Skip будут близкими, но не вижу функциональности Splice (), плюс общий список Skip не будет использовать тот факт, что вставка никогда не происходит в смежных записях.

Answer 1

Одним из простых подходов может быть использование вдвойне связанного списка экстентов, где каждая степень представляет последовательность смежных записей. Записи в каждой степени могут быть представлены с двойным связанным списком.

Это сохраняет вашу способность делать сплайсинг $ O (1) $ времени, и теперь операция вставки занимает время $ O (k) $, где $ k $ - это количество степени (а не $ O (n) $, где $ n $ - это количество записей). Если у вас есть много степени, чем записи, это может быть частичным улучшением.

Я не знаю, будет ли это лучше, чем простой список пропуска или бинарное дерево.

Обратите внимание, что если вы используете бинарное дерево, вы все равно можете выполнять эффективную сплайсинг. Операция сплайсинга больше не является времени $ O (1) $, но это может быть сделано в $ O ( log ell) $ Time, где $ ell $ - это количество записей в сегменте сплайсированного. Это не так быстро, как сплайсинг времени $ o (1) $, но в зависимости от относительной частоты ваших различных операций, это еще одна структура данных, которую вы можете рассмотреть (например, эталоны реалистичных наборов данных).

И, конечно же, вы можете объединить эти идеи, например, с бинарным деревом источников, где каждая степень, в свою очередь, является вдвойне связанным списком смежных записей. Вставки потребуют время $ O ( lg K) $, а сплайсинг может быть сделан в $ O ( lg ell) $ времени (оба из которых потенциально могут быть лучше, чем $ o ( lg n) $, достигнутое через Простое бинарное дерево).