Равномерно размещенные указатели Skip

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