28980 авторов и 62 редактора ответили на 85229 вопросов,
разместив 135207 ссылок на 43426 сайтов, присоединяйтесь!

Что такое Skip List?

РедактироватьВ избранноеПечать

Список с пропусками (Skip List) – структура данных, состоящая из нескольких связных списков (их принято называть слоями).

 

Основной список (его называют нижним слоем) – это обычный отсортированный связный список. Каждый элемент предыдущего слоя с некоторой фиксированной вероятностью присутствует в следующем слое. Таким образом, количество элементов уменьшается от слоя к слою и для перебора элементов следующего слоя требуется меньше времени по сравнению с предыдущим слоем.


Данная структура позволяет существенно ускорить поиск элемента в списке. Вместо последовательного перебора элементов основного списка (нижнего слоя) используется следующий алгоритм.

 

Поиск начинается с верхнего слоя.

 

Элементы слоя перебираются до тех пор, пока не будет найден элемент больший или равный целевому.

 

Если элемент списка равен целевому, поиск оканчивается (успех).

 

В противном случае осуществляется возврат к предыдущему элементу и переход к списку более низкого уровня, затем процедура повторяется.

 

Если текущий уровень – нижний, поиск оканчивается (неудача).

 

Списки с пропусками реализованы на многих современных языках программирования (Java, C++, C#, Python и т.д.).

 

Источники:

Последнее редактирование ответа: 05.06.2015

  • Оставить отзыв

    Оставить отзыв

     

РедактироватьВ избранноеПечать

«Что такое Skip List»

В других поисковых системах:

GoogleЯndexRamblerВикипедия

В соответствии с пользовательским соглашением администрация не несет ответственности за содержание материалов, которые размещают пользователи. Для урегулирования спорных вопросов и претензий Вы можете связаться с администрацией сайта genon.ru. Размещенные на сайте материалы могут содержать информацию, предназначенную для пользователей старше 18 лет, согласно Федерального закона №436-ФЗ от 29.12.2010 года "О защите детей от информации, причиняющей вред их здоровью и развитию". Обращение к пользователям 18+.