бинарный поиск в массиве в 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. Binary (полуинтервалу) поиск массива.

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

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

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

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

   ---

2. Binary Search Trees (BSTs) Затраты

   Производительность:

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

   
   

   Реализация: существует несколько разновидностей на CPAN: Tree::Binary::Search, Tree::Treap, Tree::RedBlack. Последние два have better average performance and smaller performance fluctuations, algorithmically.

   Сравнение: Если данные изменятся, вы должны использовать BST, чтобы избежать затрат пересортируйте. Если ваши данные случайны и никогда не меняются после сортировки, вы можете использовать простой бинарный поиск по BST, но BST могут быть настроены лучше, если каждая последняя унция производительности (BST можно оптимизировать для более быстрого среднего поиска, чем бинарный поиск списка, если вы знаете свой поиск затраты, основанные на распределении данных - см. Wiki's "Optimal binary search trees" section, или если ваше распределение данных благоприятствует одному из специальных деревьев, таких как Treap или Red/Black).

   ---

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

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

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

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

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

   Сравнение:

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

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

     A. ограничения памяти. И поиск в отсортированном списке, BST и хэш-поиски имеют размер памяти как минимум 2*N. Если вы столкнулись с ограничением памяти (учитывая размер вашего списка), достаточно серьезным, чтобы N vs 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) для случайной большой набор данных, из-за возможного столкновения с ключом. Я не знаю eno ugh о реализации хэша 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), необходимых для создания хэша).

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

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

Answer 2

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

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