Список пропущенных
-
Обзор списка пропусков
- Список пропусков — это структура данных, которая позволяет быстро вставлять и удалять элементы, но требует времени для поиска.
- Используется для хранения отсортированных данных и обеспечивает логарифмический поиск.
-
Реализация и эффективность
- Список пропусков состоит из узлов, каждый из которых содержит указатель на следующий узел и уровень.
- Вставки и удаления выполняются аналогично связанным спискам, но требуют дополнительных операций для поддержания баланса.
- Поиск в списке пропусков выполняется путем последовательного перехода к узлам с более низким уровнем, что обеспечивает ожидаемое время поиска O(log n).
-
Оптимизация и квазирандомизация
- Можно оптимизировать поиск, используя только четные или нечетные узлы, но это может привести к снижению производительности.
- Квазирандомизация списка пропусков позволяет скрыть структуру уровней от злоумышленников, сохраняя при этом логарифмический поиск.
-
Индексированный список пропусков
- Индексированный список пропусков позволяет выполнять быстрый поиск по индексу, сохраняя при этом логарифмический поиск для произвольного доступа.
- Для индексации используется ширина ссылок, которая позволяет быстро находить элементы в списке пропусков.
-
История и использование
- Списки пропусков были изобретены Уильямом Пью в 1989 году и с тех пор широко используются в различных приложениях и фреймворках.
- Они применяются в Apache Portable Runtime, MemSQL, MuQSS, Cyrus IMAP, Lucene, Qt, Redis, Discord, RocksDB и других проектах.
-
Рекомендации и внешние ссылки
- Статья содержит ссылки на лекции и другие ресурсы, связанные со списками пропусков.