Двоичный поиск в массиве в Perl

Ответ 1

Существует четыре стратегии для эффективного поиска в массиве в наборе данных в Perl.

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

• Поиск двоичного (полуинтервального) массива.

  Это, очевидно, стандартный алгоритмический подход.

  Эксплуатационные затраты:

  • O(N * log N) для начальной сортировки.
  • O(N) в среднем для вставки/удаления данных в списке после сортировки. Perl-массивы не являются связанными списками, поэтому не O(log N).
  • O(log N) для каждого поиска.
    
    

  Реализация: алгоритм настолько прост, что сделать это легко. Как обычно, существуют CPAN-модули и, вероятно, должны использоваться вместо DIY: Search::Binary.

  ---

• Деревья двоичного поиска (BST)

  Эксплуатационные затраты:

  • O(N * log N) для начальной сортировки.
  • O(log N) в среднем для вставки/удаления данных в списке после сортировки
  • O(log N) для каждого поиска.

  
  

  Реализация: в CPAN существует несколько вариантов: Tree::Binary::Search, Tree::Treap, Tree::RedBlack. Последние два имеют лучшую среднюю производительность и меньшие колебания производительности, алгоритмически.

  Сравнение. Если данные WILL меняются, вы должны использовать BST, чтобы избежать повторной сортировки. Если ваши данные случайны и никогда не меняются после сортировки, вы можете использовать простой бинарный поиск по BST, но BST могут быть настроены лучше, если каждая последняя унция производительности (BST можно оптимизировать для более быстрого среднего поиска, чем бинарный поиск списка, если вы знаете свой поиск затраты, основанные на распределении данных - см. Wiki "Оптимальные деревья двоичных деревьев" раздел или если ваше распределение данных благоприятствует одному из специальных деревьев, таких как Treap или Red/черный).

  ---

• Сокращенные (короткие замыкания) поисковые запросы.

  Это поиск по линейному сканированию в неупорядоченном списке, который останавливает поиск после того, как элемент найден.

  Производительность: O(N) за поиск случайных данных, но быстрее O(N) (скажем, N/2), чем поиск по полному списку, например grep. Никаких дополнительных затрат.

  Реализация. Есть три способа сделать их в Perl:

  • оператор Smart match (~~). Проблема в том, что она ТОЛЬКО доступна в Perl 5.10 и выше.
  • Ваш собственный цикл, который делает next; один раз.
  • List::MoreUtils модуль first() подпрограмма.

  Сравнение:

  • Во-первых, между тремя реализациями выше, List::MoreUtils::first работает быстрее, чем цикл DIY, поскольку он реализован в XS; поэтому он должен использоваться в версиях Perl до 5.10. Умное совпадение, вероятно, так же быстро, хотя я бы поставил два теста перед тем, как выбрать один или другой в Perl 5.10 +.

  • Во-вторых, сравнение короткого замыкания с другими методами, есть только 3 крайних случая, когда он должен использоваться:

    а. Ограничения памяти.. И поиск в отсортированном списке, и BST, и хэш-запросы имеют размер памяти как минимум 2*N. Если вы столкнулись с ограничением памяти (учитывая размер вашего списка), достаточно серьезным, чтобы память N vs 2*N стала необоротным барьером затрат, тогда вы используете короткий замкнутый поиск и своевременно оплачиваете штраф за исполнение.   Это особенно актуально, когда вы обрабатываете большой набор данных партиями/по очереди, чтобы во избежание прежде всего хранить все в памяти.

    В. Если ваши данные распределены и предварительно отсортированы таким образом, что большинство поисковых запросов VAST найдет свою карьеру в самом начале списка. Если это так, он МОЖЕТ превзойти методы фанатизма, такие как BST бинарного поиска, несмотря на их, очевидно, быстрый поиск O (log N). Было бы еще трудно превзойти ожидания хэша, но об этом позже.

    С. Короткозамкнутый поиск превосходит BST или отсортированный список, если количество выполненных запросов довольно мало по сравнению с размером списка, и в этом случае начальная сортировка первых двух методов (O(N log N)) перевешивает экономию средств поиска. Поскольку экономия BST по сравнению с линейным поиском составляет O(M * N), где M - это количество поисковых запросов, из этого следует, что # запросов M должен быть меньше O (log N), чтобы реализовать среднюю экономию, но может быть больше во втором когда средняя стоимость сканирования меньше O(N) из-за распределения данных.

  ---

• Поиск поиска хэшей

  Эксплуатационные затраты:

  • O(N) + epsilon для создания исходного хэша (это не является строго говоря O (N) для случайного большого набора данных из-за возможного столкновения ключей. Я недостаточно знаю о реализации хеша Perl, чтобы прояснить это, кроме состояния, МОЖЕТ быть обеспокоен любыми хэш-картами.
  • O(1) в среднем для вставки/удаления данных в списке после сортировки (+ тот же самый epsilon, что и исходное хеш-создание из-за коллизий ключей).
  • O(1) для каждого поиска (плюс тот же самый эпсилон).
    
    

  Реализация:

  my %lookup = map { $_ => 1 } @list; 
  my @lookup2{ @list } = (); # Alternative method of creating a hash
  sub find { return exists $lookup{$_[0]; }
  

  Сравнение:

  • Во-первых, та же логика применяется для сравнения короткого замыкания с поиском хэшей, как с BST, так и с короткозамкнутым поиском. Например, ALMOST всегда следует использовать хешмапы над линейным поиском, за исключением тех же двух краевых случаев (набор данных таков, что среднее сканирование списка становится O(1) вместо O(N) и отношение количества запросов к набору данных размер делает совокупную стоимость поиска менее O(N), необходимой для создания хэша).

  • Во-вторых, hashmaps ON AVERAGE, очевидно, намного быстрее, чем BST или поиск в двоичном списке. Единственный возможный краевой случай - это то, что вы каким-то образом натыкаетесь на набор данных, которому удается перегрузить ведра и превратить эту дополнительную "эпсилон" в достаточно большой вес, чтобы он начал работать менее O(log N).

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

Ответ 2

Если вы собираетесь делать один поиск, сортировка займет больше времени, чем выполнение одного линейного сканирования, поэтому вы можете просто придерживаться цикла по массиву. Для небольшого массива или если у вас может быть несколько совпадений, вы также можете посмотреть на функцию grep; это немного проще в использовании, но всегда будет проверять весь список совпадений кандидатов, а не останавливаться, когда будет найдено совпадение.

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