รายการข้าม

ในวิทยาการคอมพิวเตอร์ การก้าวกระโดดเป็นโครงสร้างข้อมูลที่ช่วยให้สามารถค้นหาได้อย่างรวดเร็ว ภายในลำดับขององค์ประกอบ การค้นหาอย่างรวดเร็วทำได้โดยการรักษาลำดับชั้นที่เชื่อมโยงกันของ subsequences โดยที่ลำดับชั้นต่อเนื่องจะข้ามไปยังองค์ประกอบที่น้อยกว่าก่อนหน้านี้ การค้นหาจะเริ่มต้นในลำดับชั้นที่เล็กที่สุดจนกว่าจะพบองค์ประกอบสองอย่างต่อเนื่องหนึ่งส่วนมีขนาดเล็กและใหญ่กว่าหรือเท่ากับองค์ประกอบที่ค้นหา ผ่านลำดับชั้นที่เชื่อมโยงองค์ประกอบทั้งสองนี้เชื่อมโยงกับองค์ประกอบของลำดับชั้นที่เบาบางที่สุดถัดไปซึ่งการค้นหาจะดำเนินต่อไปจนกว่าเราจะค้นหาลำดับทั้งหมด องค์ประกอบที่ถูกข้ามไปอาจจะได้รับการคัดเลือกให้เป็นไปตามความเป็นไปได้ หรือ deterministically กับอดีตเป็นเรื่องธรรมดามากขึ้น

ลักษณะ

รายละเอียดการดำเนินการ

องค์ประกอบที่ใช้สำหรับรายการข้ามจะมีมากกว่าหนึ่งตัวชี้เนื่องจากสามารถมีส่วนร่วมในมากกว่าหนึ่งรายการ

การแทรกและการลบจะดำเนินการเหมือนกับการดำเนินการรายการที่เชื่อมโยงกันยกเว้นองค์ประกอบ "สูง" ที่ต้องแทรกหรือลบออกจากรายการที่เชื่อมโยงกันมากกว่าหนึ่งรายการ 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