Блокировка бесплатного дважды связанного списка пропусков

Question

Существует тонна исследований по блокируемому двукратно связанному списку. Аналогично, есть тонны ресерах на незащищенных списках пропуска. Однако, насколько я могу судить, никому не удалось заблокировать двойной двунаправленный список пропусков. Кто-нибудь знает какие-либо исследования об обратном, или почему это так?

Редактировать: Конкретный сценарий предназначен для создания аккумулятора с быстрым квантилем (50%, 75% и т. Д.). Образцы вставляются в список пропуска в O (log n). Сохраняя итератор в текущем квантиле, мы можем сравнить вставленное значение с текущим квантилем в O (1) раз и легко определить, находится ли вставленное значение слева или справа от квантиля и на сколько квантиль в результате нужно двигаться. Это левый ход, для которого требуется предыдущий указатель.

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

Answer 1

Но зачем вам это делать? Я на самом деле не сел и работал точно, как работают списки пропуска, но из моего смутного понимания вы никогда не использовали бы предыдущие указатели. Итак, почему накладные расходы на их поддержание?

Но если вы хотите, я не понимаю, почему вы не можете. Просто замените односвязный список на двусвязный список. Двусвязный список логически когерентен, так что это все равно.

Answer 2

У меня есть идея для вас. Мы используем «курсор», чтобы найти элемент в skiplist. Курсор также сохраняет след, который был доставлен, чтобы добраться до элемента. Мы используем этот след для удаления и вставки - он избегает второго поиска для выполнения этих операций и включает версию версии списка, которая была замечена при обходе. Мне интересно, можно ли использовать курсор для более быстрого поиска предыдущего элемента.

Вам нужно будет подняться на уровень курсора, а затем выполнить поиск предмета, который будет чуть меньше вашего предмета. В качестве альтернативы, если поиск сделал его до самого низкого уровня связанного списка, просто сохраните prev ptr при прохождении. Самый низкий уровень, вероятно, используется в 50% случаев, чтобы найти ваш товар, поэтому производительность будет приличной.

Хм ... думая об этом сейчас, кажется, что курсор будет в 50% случаев иметь предыдущий ptr, 25% времени нужно искать снова с 1 уровня вверх, 12.% 2 уровня вверх, и т. д. Поэтому в редких случаях вы должны почти полностью выполнять поиск.

Я думаю, что преимущество этого заключается в том, что вам не нужно определять, как «блокировать бесплатно» поддерживать двойной связанный список пропуска, и в большинстве случаев вы резко уменьшаете стоимость поиска предыдущего элемента ,