CODEWITHSUNDEEP
pythonlinked-listskip-lists
user465983
user465983

Reputation: 135

Evenly placed Skip pointers

I was reading about skip pointers and someone suggested that it is best to put evenly spaced sqrt(len of list) skip pointers. Can someone tell me what "evenly spaced" means here? I will also like to see the code of doing such a thing in Java or Python

Upvotes: 0

Views: 1386

Answers (2)

Natalija
Natalija

Reputation: 1

def add_skips(posting_list):
post_list_with_skips = []
skip_count = math.floor(math.sqrt(len(posting_list)))
pos_index = 0
skip_period = math.floor(len(posting_list) / skip_count)
# -1 because of list indexing starts with 0
skip_index = skip_period - 1
while pos_index < len(posting_list):
    if pos_index == skip_index:
        post_list_with_skips.append([posting_list[pos_index], 1])
        skip_index += skip_period
    else:
        post_list_with_skips.append([posting_list[pos_index], 0])
    pos_index += 1
return post_list_with_skips

Upvotes: 0

recursive
recursive

Reputation: 86124

I think your friend was talking about skip lists. Usually the skip pointers are placed randomly through the list. Evenly spaced pointers refers to deterministically spacing them throughout the list instead of randomly placing them. Such a scheme would probably give faster reads, but would probably require more calculation when writing to the list.

Upvotes: 2

Related Questions