Jak mogę sprawdzić, czy tablica Perla zawiera określoną wartość?

239

Próbuję wymyślić sposób sprawdzenia istnienia wartości w tablicy bez iteracji po tablicy.

Czytam plik dla parametru. Mam długą listę parametrów, z którymi nie chcę sobie poradzić. Te niechciane parametry umieściłem w tablicy @badparams.

Chcę odczytać nowy parametr, a jeśli nie istnieje @badparams, należy go przetworzyć. Jeśli istnieje @badparams, przejdź do następnego czytania.

Mel
źródło
3
Dla przypomnienia, odpowiedź zależy od twojej sytuacji. Wygląda na to, że chcesz powtarzać wyszukiwania, więc używanie skrótu, jak sugeruje jkramer, jest dobre. Jeśli chcesz tylko wykonać jedno wyszukiwanie, równie dobrze możesz po prostu powtórzyć. (W niektórych przypadkach możesz chcieć wyszukiwać binarnie zamiast używać skrótu!)
Cascabel
5
perldoc -f grep
Ether
6
Dla przypomnienia (i może to zupełnie nie mieć zastosowania w twojej sytuacji), ogólnie lepiej jest zidentyfikować „dobre wartości” i zignorować resztę, niż próbować odrzucić znane „złe wartości”. Pytanie, które musisz zadać, brzmi: czy to możliwe, że mogą istnieć złe wartości, o których jeszcze nie wiesz.
Grant McLean,

Odpowiedzi:

187

Po prostu zamień tablicę w skrót:

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

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

Możesz również dodać więcej (unikalnych) parametrów do listy:

$params{$newparam} = 1;

A później odzyskaj listę (unikalnych) parametrów:

@badparams = keys %params;
jkramer
źródło
38
Dla przypomnienia ten kod nadal wykonuje iterację w tablicy. Wywołanie map {} sprawia, że ​​iteracja jest bardzo łatwa do napisania.
Kenny Wyland
3
Zrobiłbym to tylko wtedy, gdy twoje wartości w @badparams są pseudostatyczne i planujesz przeprowadzić wiele kontroli na mapie. Nie poleciłbym tego przy pojedynczej kontroli.
Aaron T Harris,
Czy to nie zadziała dla tablicy z wieloma przedmiotami o tej samej wartości?
Rob Wells
3
@RobWells nie, będzie działać dobrze. Następnym razem, gdy zobaczy tę samą wartość, po prostu nadpisze wpis w haszu, co w tym przypadku ustawia go 1ponownie.
andrewrjones
222

Najlepszy ogólny cel - szczególnie krótkie tablice (1000 elementów lub mniej) i kodery, które nie są pewne, jakie optymalizacje najlepiej odpowiadają ich potrzebom.

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

Wspomniano, że grep przechodzi przez wszystkie wartości, nawet jeśli pierwsza wartość w tablicy jest zgodna. To prawda, jednak grep jest nadal bardzo szybki w większości przypadków . Jeśli mówisz o krótkich tablicach (mniej niż 1000 pozycji), większość algorytmów i tak będzie dość szybka. Jeśli mówisz o bardzo długich tablicach (1 000 000 przedmiotów), grep jest akceptowalnie szybki, niezależnie od tego, czy element jest pierwszym, środkowym czy ostatnim w tablicy.

Przypadki optymalizacji dla dłuższych tablic:

Jeśli tablica jest posortowana , użyj „wyszukiwania binarnego”.

Jeśli ta sama tablica jest wielokrotnie przeszukiwana , najpierw skopiuj ją do skrótu, a następnie sprawdź skrót. Jeśli problemem jest pamięć, przenieś każdy element z tablicy do skrótu. Bardziej wydajna pamięć, ale niszczy oryginalną macierz.

Jeśli te same wartości są wielokrotnie wyszukiwane w tablicy, leniwie zbuduj pamięć podręczną. (podczas wyszukiwania każdego elementu najpierw sprawdź, czy wynik wyszukiwania został zapisany w utrwalonym haszu. jeśli wynik wyszukiwania nie zostanie znaleziony w haszu, następnie przeszukaj tablicę i umieść wynik w hasze utrwalonej, aby następnym razem znajdź go w haszu i pomiń wyszukiwanie).

Uwaga: te optymalizacje będą szybsze tylko w przypadku długich tablic. Nie przesadnie optymalizuj.

Aaron T. Harris
źródło
12
Podwójna tylda została wprowadzona w Perlu 5.10
Wstrzymana do odwołania.
15
@DennisWilliamson ... a w 5.18 jest to uważane za eksperymentalne .
Xaerxess
5
Unikaj inteligentnego dopasowania w kodzie produkcyjnym. Jest niestabilny / eksperymentalny do odwołania.
Vector Gorgoth,
1
Uważam to również za bardziej czytelne, ale „ Nie używaj” mówi, że nie jest wydajne i sprawdza każdy element, nawet jeśli jest pierwszy.
giordano,
7
Nie używaj if („wartość” ~~ @ tablica). ~~ to eksperymentalna funkcja o nazwie Smartmatch. Eksperyment wydaje się uważany za porażkę i zostanie usunięty lub zmodyfikowany w przyszłej wersji Perla.
yahermann
120

Możesz użyć funkcji SmartMatch w Perlu 5.10 w następujący sposób:

W przypadku wyszukiwania wartości dosłownej zrobienie tego załatwi sprawę.

if ( "value" ~~ @array ) 

W przypadku wyszukiwania skalarnego wykonywanie poniżej będzie działać jak powyżej.

if ($val ~~ @array)

W przypadku poniższej tablicy działającej, będzie działać jak powyżej.

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

W Perlu 5.18 smartmatch jest oznaczony jako eksperymentalny, dlatego musisz wyłączyć ostrzeżenia, włączając eksperymentalną pragmę, dodając poniżej do skryptu / modułu:

use experimental 'smartmatch';

Alternatywnie, jeśli chcesz uniknąć korzystania z smartmatch - to, jak powiedział Aaron, użyj:

if ( grep( /^$value$/, @array ) ) {
  #TODO:
}
Mapa bitowa
źródło
4
To miłe, ale wydaje się być nowe w Perlu 5.10. Minęło trochę czasu, zanim zorientowałem się, dlaczego dostaję błędy składniowe.
Igor Skochinsky
17
Ostrzeżenie: możesz tego uniknąć, ponieważ operator ma różne zachowania w różnych wersjach, a tymczasem został oznaczony jako eksperymentalny . Więc jeśli nie masz pełnej kontroli nad wersją Perla (i kto ją posiada), prawdopodobnie powinieneś jej unikać.
Maze
1
Podoba mi się to wyjaśnienie, dlaczego ustawienie use experimental 'smartmatch'jest zalecane. Ponieważ mam kontrolę nad moją wersją perla (system wewnętrzny), używam no warnings 'experimental::smartmatch';instrukcji.
lepe
43

Ten post na blogu omawia najlepsze odpowiedzi na to pytanie.

Krótko mówiąc, jeśli możesz zainstalować moduły CPAN, najbardziej czytelnymi rozwiązaniami są:

any(@ingredients) eq 'flour';

lub

@ingredients->contains('flour');

Jednak bardziej powszechnym idiomem jest:

any { $_ eq 'flour' } @ingredients

Ale proszę, nie używaj tej first()funkcji! W ogóle nie wyraża intencji twojego kodu. Nie używaj ~~operatora „Smart match”: jest zepsuty. I nie używaj grep()ani rozwiązania z hashem: iterują całą listę.

any() przestanie, gdy tylko znajdzie wartość.

Sprawdź post na blogu, aby uzyskać więcej informacji.

mascip
źródło
8
wszelkie potrzebyuse List::Util qw(any);. List::Utiljest w modułach Core .
Onlyjob
13

Metoda 1: grep (może zachować ostrożność, podczas gdy oczekuje się, że wartość będzie wyrażeniem regularnym).

Staraj się unikać używania grep, jeśli patrzysz na zasoby.

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

Metoda 2: Wyszukiwanie liniowe

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

Metoda 3: Użyj skrótu

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

Metoda 4: SmartMatch

(dodano w Perlu 5.10, zaznaczono eksperymentalnie w Perlu 5.18).

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

Metoda 5: Użyj modułu List::MoreUtils

use List::MoreUtils qw(any);
@badparams = (1,2,3);
$value = 1;
print "found" if any {$_ == $value} @badparams;
Kamal Nayan
źródło
12

Benchmark @ eakssjo jest zepsuty - miary tworzące pętle w porównaniu do tworzenia wyrażeń regularnych w pętli. Naprawiona wersja (plus dodałem List::Util::firsti 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} );
        },
    });

I wynik (dotyczy iteracji 100_000, dziesięć razy więcej niż w odpowiedzi @ 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
źródło
6
Jeśli chcesz przetestować wiele elementów, wcześniejsze utworzenie skrótu pozwala zaoszczędzić czas. Ale jeśli chcesz tylko wiedzieć, czy zawiera pojedynczy element, nie masz już skrótu. Dlatego tworzenie skrótu powinno być częścią czasu obliczeniowego. Tym bardziej dla wyrażenia regularnego: potrzebujesz nowego wyrażenia regularnego dla każdego szukanego elementu.
fishinear
1
@fishinear Prawda, ale jeśli interesuje Cię tylko jeden czek, a nie wiele czeków, to oczywiście mikrooptymalizacja nawet zastanawia się, która metoda jest szybsza, ponieważ te mikrosekundy nie mają znaczenia. Jeśli chcesz powtórzyć tę kontrolę, hash jest właściwą drogą, ponieważ koszt utworzenia skrótu raz jest wystarczająco mały, aby go zignorować. Powyższe testy porównują tylko różne sposoby testowania, nie włączając żadnej konfiguracji. Tak, może to być niepoprawne w twoim przypadku użycia, ale znowu - jeśli wykonujesz tylko pojedyncze sprawdzenie, powinieneś użyć wszystkiego, co jest najbardziej czytelne dla ciebie i twoich znajomych.
Xaerxess,
10

Mimo że jest wygodny w użyciu, wygląda na to, że konwersja na hash kosztuje sporo wydajności, co było dla mnie problemem.

#!/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
            }
        },
});

Wynik testu porównawczego:

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)
aksel
źródło
5
Korzystanie List::Util::firstjest szybsze, ponieważ przestaje iterować po znalezieniu dopasowania.
RobEarl,
1
-1 Twój test porównawczy ma wady, grepjest znacznie wolniejszy niż tworzenie skrótu i ​​wyszukiwanie, ponieważ pierwszy to O (n), a drugi O (1). Po prostu wykonaj tworzenie skrótu tylko raz (poza pętlą) i oblicz wyrażenie regularne tylko w celu zmierzenia metod ( zobacz moją odpowiedź ).
Xaerxess,
4
@Xaerxess: W moim przypadku chciałem przeprowadzić jedno wyszukiwanie, więc myślę, że sprawiedliwie jest liczyć zarówno tworzenie skrótu / wyrażenia regularnego, jak i wyszukiwanie / grep. Zadaniem byłoby wykonanie wielu przeglądów, myślę, że twoje rozwiązanie jest lepsze.
aksel
3
Jeśli chcesz wykonać tylko jedną iterację, różnica jest niemożliwa do odróżnienia między dowolnymi wybranymi metodami, więc każdy test porównawczy jest błędny, ponieważ w tym przypadku jest to zła mikrooptymalizacja.
Xaerxess,
2
Wyrażenie regularne jest kompilowane tylko raz, ponieważ ma flagę „o”.
Apoc
3

@plik to istniejąca tablica

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 począwszy od 2 tutaj możesz umieścić dowolne wyrażenie regularne

Rohan
źródło
2

Na pewno chcesz tutaj hash. Umieść złe parametry jako klucze w haszu, a następnie zdecyduj, czy dany parametr istnieje w haszu.

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

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

Jeśli naprawdę chcesz to zrobić za pomocą tablicy, spójrz na List::UtillubList::MoreUtils

David M.
źródło
0

Można to zrobić na dwa sposoby. Możesz użyć wrzucania wartości do skrótu dla tabeli odnośników, jak sugerują inne posty. (Dodam tylko kolejny idiom.)

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

Ale jeśli są to dane składające się głównie z znaków słownych i niezbyt dużej liczby meta, możesz zrzucić je na zmianę wyrażenia regularnego:

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/;

To rozwiązanie musiałoby zostać dostosowane do typów „złych wartości”, których szukasz. I znowu, może to być całkowicie niewłaściwe dla niektórych rodzajów ciągów, więc zastrzegaj emptor .

Axeman
źródło
1
Możesz także pisać @bad_param_lookup{@bad_params} = (), ale musisz użyć existsdo przetestowania członkostwa.
Greg Bacon
-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";
    }
}

Możesz sprawdzić spójność liczbową spacji wiodących

Serge
źródło