пропустить список для небольших наборов данных

Я скорее заинтересован в использовании списка пропуска для открытого списка для A *. Однако что меня беспокоит, так это вероятностный характер этого. Открытые списки могут варьироваться от очень маленьких наборов до огромного количества узлов, и для каждого из них необходимо поддерживать производительность.

Насколько я понимаю, списки пропуска имеют более высокую вероятность случайного получения плохих результатов для небольших наборов данных. Я думаю, что это может стать проблемой при создании большого количества коротких путей.

Я думал исправить это, почему бы не следить за случайными числами до определенной степени. Сохраняйте общее количество узлов на каждом уровне и, чтобы поддерживать идеальное распределение узлов между каждым уровнем, иногда вмешивайтесь и заставляйте узел быть определенным уровнем.

Я не уверен, насколько хорошо это будет работать в моем приложении, и, возможно, мне следует вместо этого сосредоточиться на другой структуре данных для моих открытых списков.

Во всех статьях, которые я читал о списках пропуска, такая оптимизация не упоминалась. Поскольку я новичок во всей игре профилирования производительности, я не решаюсь попытаться улучшить документированную структуру данных.


algorithm data-structures language-agnostic skip-lists
person user1759679    schedule 24.10.2012    source источник
comment
Прелесть в том, что не имеет значения, что списки пропуска имеют плохие свойства для небольших списков, потому что маленькие списки в любом случае будут быстрыми, даже если время поиска ухудшится до линейного. Я бы не беспокоился об этом до тех пор, пока после профилирования не обнаружил, что это проблема.   -  person Konrad Rudolph    schedule 24.10.2012

Ответы (3)


arrow_upward
1
arrow_downward

  1. Да, вы правы — у списков пропусков больше шансов испортиться, если говорить о небольших списках пропуска.
    В целом, согласно этой статье, является константой alpha такой, что вероятность того, что список пропусков превысит alpha * n пробела, меньше, чем 1/2Ω(sqrt(n)), поэтому по мере увеличения списков пропуска вероятность этого (превышения этого предела) становится все меньше и меньше.

  2. Чтобы избежать наихудших случаев со списком пропуска, можно использовать вариант исходного списка пропуска, детерминированный список пропуска. Эта тема обсуждается в этой дипломной работе.

  3. Другими альтернативами являются сбалансированные BST, такие как AVL и красно-черное-дерево или даже деревья B+ (которые обычно предпочтительнее для файловых систем).

  4. Если ваш «открытый набор» действительно такой маленький, вероятность того, что ваш фактор ветвления также очень мал (близок к 1), или, если быть точным, B^d (d = глубина решения; B = фактор ветвления) также будет мал. . Это приведет к быстрому поиску вне зависимости от реализации списка пропуска, поскольку предполагается, что потребуется небольшое количество узлов.

person amit    schedule 24.10.2012
comment
детерминированные списки пропусков звучат интересно, придется прочитать эту статью. - person user1759679; 25.10.2012

arrow_upward
2
arrow_downward

Я бы посоветовал вам создать программу, которая случайным образом генерирует списки пропусков длин, которые, как вы ожидаете, создаст ваш алгоритм A*. Просмотрите эти списки, чтобы увидеть, сколько из них меньше оптимального.

Я бы не рекомендовал пытаться создать структуру данных списка пропусков производства, в которой есть мониторинг, который вы предложили. Скорее всего, вы обнаружите, что код мониторинга и вмешательства приведет к плохой работе списка пропуска в общем случае.

person Jim Mischel    schedule 24.10.2012
comment
Мне любопытно, почему это заставит его работать плохо в общем случае. Если бы я ограничил свое вмешательство только уровнями, на которых вставляются новые узлы, сильно ли это повлияло бы на производительность? - person user1759679; 24.10.2012
comment
Код для отслеживания случайных чисел потребует, чтобы вы сохраняли эти числа для каждого списка и перебирали их при каждой вставке. Это значительно увеличит объем проделанной работы. Теперь, если вашей основной задачей является поиск в небольших списках, я бы посоветовал не слишком беспокоиться об этом, поскольку даже линейный поиск (который вырождается в список пропуска, если он крайне неоптимален) небольшого списка будет очень быстрым . - person Jim Mischel; 24.10.2012

arrow_upward
0
arrow_downward

Когда вы говорите: «Списки пропуска имеют более высокую вероятность случайного получения плохих результатов для небольших наборов данных», чего именно вы боитесь?

Чего вам не следует бояться, так это того, что для списка, скажем, из 10 элементов недостаточно узлов уровня 2 или 3 для ускорения обхода. Разница между итерацией связанного списка (к которому сводится список пропусков без узлов уровня 2+) из 2 элементов или 10 элементов в основном отсутствует, даже в узких циклах (тип администрирования ссылок на узлы, требуемый вашими данными структура, вероятно, будет иметь большее влияние).

Очевидно, что как только вы доберетесь до большего количества элементов, влияние отсутствия достаточного количества узлов более высокого уровня возрастет. Но, к счастью, шанс получить узел более высокого уровня также увеличивается. Например, если вы добавите 8 элементов, вероятность того, что все они будут узлами уровня 1, составляет 0,5^8 = 0,39%, то есть крайне маловероятно.

person Leon Bouquiet    schedule 24.10.2012