Заблокировать бесплатно дважды связанный список пропуска

Question

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

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

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

Answer 1

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

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

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

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

Answer 2

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

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