รายการข้าม
มีข้อสงสัยว่าบทความนี้อาจละเมิดลิขสิทธิ์ แต่ระบุไม่ได้ชัดเจนเพราะขาดแหล่งที่มา หรืออ้างถึงสิ่งพิมพ์ที่ยังตรวจสอบไม่ได้ หากแสดงได้ว่าบทความนี้ละเมิดลิขสิทธิ์ ให้แทนป้ายนี้ด้วย {{ละเมิดลิขสิทธิ์}} หากคุณมั่นใจว่าบทความนี้ไม่ได้ละเมิดลิขสิทธิ์ ให้แสดงหลักฐานในหน้าอภิปราย โปรดอย่านำป้ายนี้ออกก่อนมีข้อสรุป |
ในวิทยาการคอมพิวเตอร์ การก้าวกระโดดเป็นโครงสร้างข้อมูลที่ช่วยให้สามารถค้นหาได้อย่างรวดเร็ว ภายในลำดับขององค์ประกอบ การค้นหาอย่างรวดเร็วทำได้โดยการรักษาลำดับชั้นที่เชื่อมโยงกันของ subsequences โดยที่ลำดับชั้นต่อเนื่องจะข้ามไปยังองค์ประกอบที่น้อยกว่าก่อนหน้านี้ การค้นหาจะเริ่มต้นในลำดับชั้นที่เล็กที่สุดจนกว่าจะพบองค์ประกอบสองอย่างต่อเนื่องหนึ่งส่วนมีขนาดเล็กและใหญ่กว่าหรือเท่ากับองค์ประกอบที่ค้นหา ผ่านลำดับชั้นที่เชื่อมโยงองค์ประกอบทั้งสองนี้เชื่อมโยงกับองค์ประกอบของลำดับชั้นที่เบาบางที่สุดถัดไปซึ่งการค้นหาจะดำเนินต่อไปจนกว่าเราจะค้นหาลำดับทั้งหมด องค์ประกอบที่ถูกข้ามไปอาจจะได้รับการคัดเลือกให้เป็นไปตามความเป็นไปได้[1] หรือ deterministically[2] กับอดีตเป็นเรื่องธรรมดามากขึ้น
ลักษณะ
[แก้]รายละเอียดการดำเนินการ
[แก้]องค์ประกอบที่ใช้สำหรับรายการข้ามจะมีมากกว่าหนึ่งตัวชี้เนื่องจากสามารถมีส่วนร่วมในมากกว่าหนึ่งรายการ
การแทรกและการลบจะดำเนินการเหมือนกับการดำเนินการรายการที่เชื่อมโยงกันยกเว้นองค์ประกอบ "สูง" ที่ต้องแทรกหรือลบออกจากรายการที่เชื่อมโยงกันมากกว่าหนึ่งรายการ O (n) การดำเนินงานซึ่งบังคับให้เราไปเยี่ยมชมทุกโหนดตามลำดับจากน้อยไปมาก (เช่นพิมพ์รายชื่อทั้งหมด) ให้โอกาสในการแสดง derandomization เบื้องหลังฉากของโครงสร้างระดับของรายการข้ามไปในทางที่ดีที่สุดนำรายการข้ามไปที่ O (log n) เวลาค้นหา (เลือกระดับของโหนดที่ จำกัด ของ i เป็น 1 บวกจำนวนครั้งที่เราสามารถแบ่ง i ถึง 2 ซ้ำ ๆ ก่อนที่มันจะกลายเป็นคี่นอกจากนี้ i = 0 สำหรับส่วนหัวอินฟินิตี้เชิงลบเนื่องจากเรามีกรณีพิเศษในการเลือก เป็นระดับที่เป็นไปได้สูงสุดสำหรับโหนดที่เป็นลบและ / หรือบวกอนันต์) อย่างไรก็ตามวิธีนี้ยังช่วยให้ใครรู้ได้ว่ามีโหนดทั้งหมดที่อยู่ในระดับสูงกว่า 1 โหนดอยู่หรือไม่และลบออกอีกทางเลือกหนึ่งคือเราสามารถสร้างโครงสร้างระดับให้เป็นแบบสุ่มโดยใช้วิธีดังต่อไปนี้
make all nodes level 1
j ← 1
while the number of nodes at level j > 1 do
for each i'th node at level j do
if i is odd
if i is not the last node at level j
randomly choose whether to promote it to level j+1
else
do not promote
end if
else if i is even and node i-1 was not promoted
promote it to level j+1
end if
repeat
j ← j + 1
repeat
ดัชนีการก้าวกระโดด
ตามที่อธิบายไว้ข้างต้น Skiplist จะสามารถแทรกและกำจัดค่าจากลำดับที่เรียงลำดับได้อย่างรวดเร็ว O (log n) มีเพียงช้า O (n) lookups ของค่าในตำแหน่งที่กำหนดในลำดับ (เช่นคืนค่า 500th) ; อย่างไรก็ตามด้วยการปรับเปลี่ยนเล็กน้อยของการค้นหาแบบสุ่มจะสามารถปรับปรุงการค้นหาให้เป็น O (log n)
สำหรับทุกลิงก์ให้เก็บความกว้างของลิงก์ด้วย ความกว้างถูกกำหนดเป็นจำนวนลิงก์ของชั้นล่างที่กำลังสำรวจโดยลิงก์ "ช่องทางด่วน" แต่ละชั้นสูงกว่า ตัวอย่างเช่นนี่คือความกว้างของลิงก์ในตัวอย่างที่ด้านบนของหน้า:
1 10
o---> o---------------------------------------------------------> o Top level
1 3 2 5
o---> o---------------> o---------> o---------------------------> o Level 3
1 2 1 2 3 2
o---> o---------> o---> o---------> o---------------> o---------> o Level 2
1 1 1 1 1 1 1 1 1 1 1
o---> o---> o---> o---> o---> o---> o---> o---> o---> o---> o---> o Bottom level
Head 1st 2nd 3rd 4th 5th 6th 7th 8th 9th 10th NIL
Node Node Node Node Node Node Node Node Node Node
สังเกตว่าความกว้างของลิงก์ระดับที่สูงขึ้นคือผลรวมของลิงก์คอมโพเนนต์ด้านล่าง (เช่นความกว้าง 10 จะครอบคลุมลิงก์ที่มีความกว้าง 3, 2 และ 5 ด้านล่าง) ดังนั้นผลรวมของความกว้างทั้งหมดจะเหมือนกันในทุกระดับ (10 +1 = 1 + 3 + 2 + 5 = 1 + 2 + 1 + 2 + 5) เมื่อต้องการจัดทำดัชนีรายการข้ามและค้นหาค่า i'th ให้ข้ามรายการข้ามขณะที่นับความกว้างของแต่ละลิงก์ ลดระดับลงเมื่อความกว้างที่จะเกิดขึ้นจะใหญ่เกินไป ตัวอย่างเช่นหากต้องการหาโหนดในตำแหน่งที่ 5 (โหนด 5) ให้ข้ามการเชื่อมโยงของความกว้าง 1 ที่ระดับบนสุด ตอนนี้จำเป็นต้องใช้สี่ขั้นตอนเพิ่มเติม แต่ความกว้างต่อไปในระดับนี้คือสิบซึ่งใหญ่เกินไปดังนั้นจึงลดลงหนึ่งระดับ ข้ามไปหนึ่งลิงก์ของความกว้าง 3. เนื่องจากอีกก้าวหนึ่งของความกว้าง 2 จะไกลเกินไปเลื่อนลงไปที่ระดับล่าง ตอนนี้สำรวจการเชื่อมโยงขั้นสุดท้ายของความกว้าง 1 ไปถึงเป้าหมายที่เรียกใช้งานทั้งหมด 5 (1 + 3 + 1)
function lookupByPositionIndex (i)
node ← head
i ← i + 1 # don't count the head as a step
for level from top to bottom do
while i ≥ node.width[level] do # if next step is not too far
i ← i - node.width[level] # subtract the current width
node ← node.next[level] # traverse forward at the current level
repeat
repeat
return node.value
end function
อ้างอิง
[แก้]- ↑ Pugh, W. (1990). "Skip lists: A probabilistic alternative to balanced trees" (PDF). Communications of the ACM. 33 (6): 668. doi:10.1145/78973.78977. คลังข้อมูลเก่าเก็บจากแหล่งเดิม (PDF)เมื่อ 2020-06-20. สืบค้นเมื่อ 2018-05-10.
- ↑ Munro, J. Ian; Papadakis, Thomas; Sedgewick, Robert (1992). "Deterministic skip lists" (PDF). Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms (SODA '92). Orlando, Florida, USA: Society for Industrial and Applied Mathematics, Philadelphia, PA, USA. pp. 367–375. doi:10.1145/139404.139478.