이중 자유 연결 이중화 목록 잠금

Question

이중 자유 연결 이중 목록에 대한 많은 연구가 있습니다. 마찬가지로, 잠금없는 건너 뛰기 목록에 대한 많은 연구가 있습니다. 그러나 내가 말할 수있는 최선의 방법은 아무도 잠금이없는 이중 링크 된 건너 뛰기 목록을 관리하지 않았다는 것입니다. 누구도 그 반대의 연구를 알고 있습니까? 그렇지 않은 이유는 무엇입니까?

편집 : 특정 시나리오는 빠른 분위 (50 %, 75 % 등) 누적 기 구축에 사용됩니다. 샘플은 O (log n) 시간에 스킵 목록에 삽입됩니다. 현재 quantile에 반복자를 유지함으로써 삽입 된 값을 O (1) 시간의 현재 quantile과 비교할 수 있으며 삽입 된 값이 quantile의 왼쪽 또는 오른쪽에 있는지 여부를 쉽게 판별 할 수 있고 quantile 그 결과로 이동해야합니다. 이전 포인터가 필요한 왼쪽 이동입니다.

필자가 이해 하듯이 여러 스레드가 한꺼번에 삽입하고 제거 할 때 이전 포인터를 일관되게 유지하는 데 어려움이 따릅니다. 나는 솔루션이 포인터 마킹을 영리하게 사용한다고 생각한다.

Answer 1

하지만 왜 그런 짓을했을까요? 실제로 앉아서 목록을 건너 뛰는 방법을 정확히 이해하지는 못했지만 막연한 이해로는 이전 포인터를 사용하지 않을 것입니다. 그렇다면 왜 그것들을 관리하는 오버 헤드가 있습니까?

하지만 원한다면 나는 왜 그렇게 할 수 없는지 알지 못합니다. 단독 연결 목록을 이중 연결 목록으로 바꾸십시오. 이중 연결 목록은 논리적으로 일관성이 있으므로 모두 동일합니다.

Answer 2

나는 당신을위한 아이디어가있다. 우리는 "커서"를 사용하여 skiplist에서 항목을 찾습니다. 또한 커서는 항목으로 이동하기 위해 사용 된 흔적을 유지합니다. 우리는 삭제와 삽입을 위해이 흔적을 사용합니다. 두 번째 검색이 해당 작업을 수행하는 것을 방지하고, 탐색이 수행되었을 때 보여지는 목록의 버전 번호를 포함합니다. 커서를 사용하여 이전 항목을 더 빨리 찾을 수 있는지 궁금합니다.

커서 위로 올라가서 항목보다 간신히 작은 항목을 검색해야합니다. 또는 검색 결과 링크 된 목록의 최하위 레벨로 이동 한 경우 트래버스 할 때 prev ptr을 저장하십시오. 가장 낮은 레벨은 아마도 아이템을 찾는 데 소요되는 시간의 50 %이므로 아마도 성능이 좋을 것입니다.

흠 ... 지금 생각해 보면 커서의 50 %가 이전의 PTT를 가지며 시간의 25 %는 1 단계에서 다시 검색해야합니다. 12 % 2 단계 위로, 드물기 때문에 거의 완전히 다시 검색해야합니다.

나는이 이점이 이중 링크 된 건너 뛰기 목록을 유지하는 방법을 알아낼 필요가 없다고 생각하며 대다수의 경우 이전 항목 찾기 비용을 크게 줄입니다. .