бинарный поиск по массиву в Perl

Question

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

Код на данный момент:

sub is_bad_str{
  my ($str, @keys) = @_;
  my $flag = 0;
  my ($key, $hex_num);
        if ($str =~ m/14'h([0-9a-f][0-9a-f][0-9a-f][0-9a-f])/;){ #'# fixes bad highlighting
  $hex_num = $1;
      }
  if (defined $hex_num){
    foreach $key (@keys){
        if ($hex_num =~ /\Q$key\E/i){
            $flag = 1;
            last;
        }
    }
  }
  if (($flag == 0) && (defined $hex_num)){
    return 1;#Bad str
  }else{
    return 0;#Good str
      }
}

Answer 1

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

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

---

1. Двоичный (полуинтервальный) поиск в массиве.

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

   Расходы на исполнение:

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

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

   ---

2. Деревья бинарного поиска (BST)

   Расходы на исполнение:

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

   
   

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

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

   ---

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

   Это поиск с линейным сканированием в несортированном списке, который ОСТАНОВИТСЯ при поиске элемента.

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

   Реализация : в Perl есть 3 способа сделать это:

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

   Сравнение

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

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

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

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

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

   ---

4. Хеш-поиск

   Расходы на производительность:

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

   Осуществление

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

   Сравнение

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

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

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

Answer 2

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

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