均匀放置的跳过指针

Question

我正在阅读有关跳过指针的内容，有人建议最好放置均匀间隔的 sqrt(len of list) 跳过指针。谁能告诉我“均匀分布”是什么意思？我还想看看用 Java 或 Python 做这样的事情的代码

Answer 1

我认为你的朋友正在谈论跳过列表。通常，跳过指针在列表中随机放置。均匀间隔的指针是指在整个列表中确定性地间隔它们而不是随机放置它们。这样的方案可能会提供更快的读取速度，但在写入列表时可能需要更多计算。

Answer 2

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