Как я могу проверить, содержит ли массив Perl определенное значение?

239

Я пытаюсь выяснить способ проверки существования значения в массиве без перебора массива.

Я читаю файл для параметра. У меня длинный список параметров, с которыми я не хочу иметь дело. Я поместил эти нежелательные параметры в массив @badparams.

Я хочу прочитать новый параметр и, если он не существует @badparams, обработать его. Если он существует @badparams, перейдите к следующему прочтению.

Мел
источник
3
Для протокола, ответ зависит от вашей ситуации. Звучит так, как будто вы хотите сделать повторный поиск, поэтому использование хэша, как подсказывает jkramer, хорошо. Если вы хотите сделать только один поиск, вы можете просто повторить. (И в некоторых случаях вы можете захотеть выполнить бинарный поиск вместо использования хеша!)
Каскабель
5
perldoc -f grep
Ether
6
Для записи (а это может быть совершенно неприменимо к вашей ситуации), как правило, лучше определить «хорошие ценности» и игнорировать остальные, чем пытаться отсеять известные «плохие ценности». Вопрос, который вам нужно задать, заключается в том, возможно ли, что существуют плохие ценности, о которых вы еще не знаете.
Грант Маклин

Ответы:

187

Просто превратите массив в хеш:

my %params = map { $_ => 1 } @badparams;

if(exists($params{$someparam})) { ... }

Вы также можете добавить больше (уникальных) параметров в список:

$params{$newparam} = 1;

А позже вернем список (уникальных) параметров:

@badparams = keys %params;
jkramer
источник
38
Для записи, этот код по-прежнему перебирает массив. Вызов map {} просто упрощает ввод этой итерации.
Кенни Уайлэнд,
3
Я сделал бы это только в том случае, если ваши значения в @badparams являются псевдостатическими, и вы планируете много проверять карту. Я не рекомендовал бы это для единственной проверки.
Аарон Т Харрис
Разве это не пойдет на пользу массиву с несколькими элементами с одинаковым значением?
Роб Уэллс
3
@RobWells нет, все будет работать нормально. В следующий раз, когда он увидит то же значение, он просто перезапишет запись в хэше, которая в этом случае устанавливает ее 1снова.
Andrewrjones
222

Лучшее общее назначение - особенно короткие массивы (1000 элементов или меньше) и кодеры, которые не уверены, какие оптимизации лучше всего соответствуют их потребностям.

# $value can be any regex. be safe
if ( grep( /^$value$/, @array ) ) {
  print "found it";
}

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

Случаи оптимизации для более длинных массивов:

Если ваш массив отсортирован , используйте «бинарный поиск».

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

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

Примечание: эти оптимизации будут быстрее только при работе с длинными массивами. Не переусердствуйте.

Аарон Т Харрис
источник
12
Двойная тильда была введена в Perl 5.10
приостановлена ​​до дальнейшего уведомления.
5
Избегайте smartmatch в производственном коде. Это нестабильно / экспериментально в ожидании дальнейшего уведомления.
Вектор Горгот
1
Я нахожу это также более читабельным, но « Не использовать» говорит о том, что он неэффективен, и проверяет каждый элемент, даже если он первый.
Джордано
7
Не используйте if ("value" ~~ @array). ~~ - это экспериментальная функция под названием Smartmatch. Эксперимент, по-видимому, считается неудачным и будет удален или изменен в будущей версии Perl.
yahermann
120

Вы можете использовать функцию smartmatch в Perl 5.10 следующим образом:

Для поиска литерального значения, сделанного ниже, добьется цели.

if ( "value" ~~ @array ) 

Для скалярного поиска выполнение ниже будет работать как выше.

if ($val ~~ @array)

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

if ( $var ~~ ['bar', 'value', 'foo'] ) 

В Perl 5.18 smartmatch помечен как экспериментальный, поэтому вам нужно отключить предупреждения, включив экспериментальную прагму, добавив ниже в ваш скрипт / модуль:

use experimental 'smartmatch';

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

if ( grep( /^$value$/, @array ) ) {
  #TODO:
}
Битовая карта
источник
4
Это хорошо, но, кажется, плохо знаком с Perl 5.10. Прошло некоторое время, прежде чем я понял, почему я получаю синтаксические ошибки.
Игорь Скочинский
17
Предупреждение: вы можете избежать этого, поскольку в разных версиях оператор, по-видимому, ведет себя по-разному и тем временем был помечен как экспериментальный . Поэтому, если у вас нет полного контроля над вашей версией perl (и у кого она есть), вам, вероятно, следует избегать ее.
Лабиринт
1
Мне нравится это объяснение того, почему настройка use experimental 'smartmatch'рекомендуется. Поскольку у меня есть контроль над моей версией Perl (внутренняя система), я использую no warnings 'experimental::smartmatch';оператор.
Леп
43

В этом блоге обсуждаются лучшие ответы на этот вопрос.

Вкратце, если вы можете установить модули CPAN, то наиболее читаемые решения:

any(@ingredients) eq 'flour';

или

@ingredients->contains('flour');

Тем не менее, более распространенная идиома:

any { $_ eq 'flour' } @ingredients

Но, пожалуйста, не используйте эту first()функцию! Он не выражает цели вашего кода вообще. Не используйте ~~оператор «Smart match»: он сломан. И не используйте grep()ни решение с хешем: они перебирают весь список.

any() остановится, как только найдет вашу ценность.

Проверьте сообщение в блоге для более подробной информации.

mascip
источник
8
любые потребностиuse List::Util qw(any);. List::Utilнаходится в основных модулях .
Onlyjob
13

Метод 1: grep (может быть осторожен, хотя ожидается, что значение будет регулярным).

Старайтесь избегать использования grep, если смотрите на ресурсы.

if ( grep( /^$value$/, @badparams ) ) {
  print "found";
}

Способ 2: линейный поиск

for (@badparams) {
    if ($_ eq $value) {
       print "found";
       last;
    }
}

Способ 3: использовать хеш

my %hash = map {$_ => 1} @badparams;
print "found" if (exists $hash{$value});

Способ 4: Smartmatch

(добавлено в Perl 5.10, помечено как экспериментальное в Perl 5.18).

use experimental 'smartmatch';  # for perl 5.18
print "found" if ($value ~~ @badparams);

Способ 5: использовать модуль List::MoreUtils

use List::MoreUtils qw(any);
@badparams = (1,2,3);
$value = 1;
print "found" if any {$_ == $value} @badparams;
Камаль Наян
источник
12

тест @ eakssjo нарушен - измеряет создание хэшей в цикле против создания регулярных выражений в цикле. Фиксированная версия (плюс я добавил List::Util::firstи List::MoreUtils::any):

use List::Util qw(first);
use List::MoreUtils qw(any);
use Benchmark;

my @list = ( 1..10_000 );
my $hit = 5_000;
my $hit_regex = qr/^$hit$/; # precompute regex
my %params;
$params{$_} = 1 for @list;  # precompute hash
timethese(
    100_000, {
        'any' => sub {
            die unless ( any { $hit_regex } @list );
        },
        'first' => sub {
            die unless ( first { $hit_regex } @list );
        },
        'grep' => sub {
            die unless ( grep { $hit_regex } @list );
        },
        'hash' => sub {
            die unless ( $params{$hit} );
        },
    });

И результат (это за 100_000 итераций, в десять раз больше, чем в ответе @ eakssjo):

Benchmark: timing 100000 iterations of any, first, grep, hash...
       any:  0 wallclock secs ( 0.67 usr +  0.00 sys =  0.67 CPU) @ 149253.73/s (n=100000)
     first:  1 wallclock secs ( 0.63 usr +  0.01 sys =  0.64 CPU) @ 156250.00/s (n=100000)
      grep: 42 wallclock secs (41.95 usr +  0.08 sys = 42.03 CPU) @ 2379.25/s (n=100000)
      hash:  0 wallclock secs ( 0.01 usr +  0.00 sys =  0.01 CPU) @ 10000000.00/s (n=100000)
            (warning: too few iterations for a reliable count)
Xaerxess
источник
6
Если вы хотите проверить несколько элементов, то предварительное создание хеша экономит ваше время. Но если вы просто хотите узнать, содержит ли он один элемент, то у вас уже нет хэша. Поэтому создание хэша должно быть частью вычислительного времени. Тем более для регулярного выражения: вам нужно новое регулярное выражение для каждого элемента, который вы ищете.
fishinear
1
@fishinear Верно, но если вас интересует только одна проверка, а не несколько проверок, то, очевидно, стоит микрооптимизировать даже вопрос о том, какой метод быстрее, потому что эти микросекунды не имеют значения. Если вы хотите повторить эту проверку, лучше использовать хеш, потому что стоимость создания хеша достаточно мала, чтобы ее можно было игнорировать. Вышеуказанные тесты измеряют только различные способы тестирования, не включая какие-либо настройки. Да, это может быть недействительным в вашем случае использования, но опять же - если вы делаете только одну проверку, вы должны использовать то, что наиболее читабельно для вас и ваших товарищей.
Xaerxess
10

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

#!/usr/bin/perl
use Benchmark;
my @list;
for (1..10_000) {
    push @list, $_;
}

timethese(10000, {
  'grep'    => sub {
            if ( grep(/^5000$/o, @list) ) {
                # code
            }
        },
  'hash'    => sub {
            my %params = map { $_ => 1 } @list;
            if ( exists($params{5000}) ) {
                # code
            }
        },
});

Результат бенчмарк-теста:

Benchmark: timing 10000 iterations of grep, hash...
          grep:  8 wallclock secs ( 7.95 usr +  0.00 sys =  7.95 CPU) @ 1257.86/s (n=10000)
          hash: 50 wallclock secs (49.68 usr +  0.01 sys = 49.69 CPU) @ 201.25/s (n=10000)
Аксель
источник
5
Использование List::Util::firstбыстрее, поскольку оно прекращает итерацию, когда находит совпадение.
RobEarl
1
-1 Ваш бенчмарк имеет дефекты, grepон значительно медленнее, чем создание хэша и поиск, так как первым является O (n), а последним O (1). Просто сделайте создание хеша только один раз (вне цикла) и предварительно вычислите регулярное выражение только для измерения методов ( см. Мой ответ ).
Xaerxess
4
@Xaerxess: В моем случае я хотел сделать один поиск, поэтому я считаю, что будет справедливо сосчитать как создание хеша / регулярного выражения, так и поиск / поиск. Если бы задача состояла в том, чтобы сделать много поисков, я думаю, ваше решение лучше.
Аксель
3
Если вы хотите выполнить только одну итерацию, разница будет неразличима между любыми выбранными вами методами, поэтому любой эталонный тест неверен, поскольку в данном случае это злая микрооптимизация.
Xaerxess
2
Регулярное выражение компилируется только один раз, так как оно имеет флаг 'o'.
Апок
3

@files - это существующий массив

my @new_values =  grep(/^2[\d].[\d][A-za-z]?/,@files);

print join("\n", @new_values);

print "\n";

/^2[\d].[\d][A-za-z]?/ = vaues начиная с 2, здесь вы можете поместить любое регулярное выражение

Рохан
источник
2

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

our %bad_params = map { $_ => 1 } qw(badparam1 badparam2 badparam3)

if ($bad_params{$new_param}) {
  print "That is a bad parameter\n";
}

Если вы действительно заинтересованы в этом с массивом, посмотрите на List::UtilилиList::MoreUtils

Дэвид М
источник
0

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

my %bad_param_lookup;
@bad_param_lookup{ @bad_params } = ( 1 ) x @bad_params;

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

use English qw<$LIST_SEPARATOR>;

my $regex_str = do { 
    local $LIST_SEPARATOR = '|';
    "(?:@bad_params)";
 };

 # $front_delim and $back_delim being any characters that come before and after. 
 my $regex = qr/$front_delim$regex_str$back_delim/;

Это решение должно быть настроено для типов «плохих ценностей», которые вы ищете. И опять же, это может быть совершенно неуместно для определенных типов строк, поэтому будьте осторожны с emptor .

лесоруб
источник
1
Вы также можете написать @bad_param_lookup{@bad_params} = (), но вам нужно будет использовать existsдля проверки членства.
Грег Бэкон
-1
my @badparams = (1,2,5,7,'a','zzz');

my $badparams = join('|',@badparams);   # '|' or any other character not present in params

foreach my $par (4,5,6,7,'a','z','zzz')
{
    if ($badparams =~ /\b$par\b/)
    {
        print "$par is present\n";
    }
    else
    {
        print "$par is not present\n";
    }
}

Вы можете проверить постоянство числовых ведущих пробелов

саржа
источник