Wie kann ich überprüfen, ob ein Perl-Array einen bestimmten Wert enthält?

239

Ich versuche, eine Möglichkeit zu finden, die Existenz eines Werts in einem Array zu überprüfen, ohne das Array zu durchlaufen.

Ich lese eine Datei für einen Parameter. Ich habe eine lange Liste von Parametern, mit denen ich mich nicht befassen möchte. Ich habe diese unerwünschten Parameter in ein Array eingefügt @badparams.

Ich möchte einen neuen Parameter lesen und wenn er in nicht vorhanden ist @badparams, verarbeiten Sie ihn. Wenn es in vorhanden ist @badparams, fahren Sie mit dem nächsten Lesevorgang fort.

Mel
quelle
3
Für die Aufzeichnung hängt die Antwort von Ihrer Situation ab. Es hört sich so an, als ob Sie wiederholte Suchvorgänge durchführen möchten. Daher ist es gut, einen Hash zu verwenden, wie von jkramer vorgeschlagen. Wenn Sie nur eine Suche durchführen möchten, können Sie auch einfach iterieren. (Und in einigen Fällen möchten Sie vielleicht eine binäre Suche durchführen, anstatt einen Hash zu verwenden!)
Cascabel
5
perldoc -f grep
Ether
6
Für die Aufzeichnung (und dies kann für Ihre Situation völlig unanwendbar sein) ist es im Allgemeinen eine bessere Idee, "gute Werte" zu identifizieren und den Rest zu ignorieren, als zu versuchen, bekannte "schlechte Werte" auszusortieren. Die Frage, die Sie stellen müssen, ist, ob es möglicherweise schlechte Werte gibt, die Sie noch nicht kennen.
Grant McLean

Antworten:

187

Verwandeln Sie das Array einfach in einen Hash:

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

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

Sie können der Liste auch weitere (eindeutige) Parameter hinzufügen:

$params{$newparam} = 1;

Und später eine Liste mit (eindeutigen) Parametern zurückbekommen:

@badparams = keys %params;
jkramer
quelle
38
Für den Datensatz durchläuft dieser Code immer noch das Array. Der Aufruf von map {} macht diese Iteration einfach sehr einfach einzugeben.
Kenny Wyland
3
Ich würde dies nur tun, wenn Ihre Werte in @badparams pseudostatisch sind und Sie vorhaben, viele Überprüfungen anhand der Karte durchzuführen. Ich würde dies nicht für einen einzigen Check empfehlen.
Aaron T Harris
Wird dies nicht für ein Array mit mehreren Elementen mit demselben Wert von Vorteil sein?
Rob Wells
3
@ RobWells nein, es wird gut funktionieren. Wenn das nächste Mal derselbe Wert angezeigt wird, wird der Eintrag im Hash einfach überschrieben, wodurch er in diesem Fall 1erneut festgelegt wird.
Andrewrjones
222

Bester allgemeiner Zweck - Besonders kurze Arrays (1000 Elemente oder weniger) und Codierer, die sich nicht sicher sind, welche Optimierungen ihren Anforderungen am besten entsprechen.

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

Es wurde erwähnt, dass grep alle Werte durchläuft, auch wenn der erste Wert im Array übereinstimmt. Dies ist wahr, jedoch ist grep in den meisten Fällen immer noch extrem schnell . Wenn Sie über kurze Arrays (weniger als 1000 Elemente) sprechen, werden die meisten Algorithmen sowieso ziemlich schnell sein. Wenn Sie über sehr lange Arrays (1.000.000 Elemente) sprechen, ist grep akzeptabel schnell, unabhängig davon, ob das Element das erste oder das mittlere oder das letzte im Array ist.

Optimierungsfälle für längere Arrays:

Wenn Ihr Array sortiert ist , verwenden Sie eine "binäre Suche".

Wenn dasselbe Array mehrmals durchsucht wird, kopieren Sie es zuerst in einen Hash und überprüfen Sie dann den Hash. Wenn der Speicher ein Problem darstellt, verschieben Sie jedes Element aus dem Array in den Hash. Effizienter, zerstört jedoch das ursprüngliche Array.

Wenn dieselben Werte innerhalb des Arrays wiederholt gesucht werden , erstellen Sie träge einen Cache. (Wenn jedes Element durchsucht wird, überprüfen Sie zuerst, ob das Suchergebnis in einem persistierten Hash gespeichert wurde. Wenn das Suchergebnis nicht im Hash gefunden wird, durchsuchen Sie das Array und fügen Sie das Ergebnis in den persistierten Hash ein, damit wir es beim nächsten Mal tun finde es im Hash und überspringe die Suche).

Hinweis: Diese Optimierungen sind nur bei langen Arrays schneller. Nicht zu stark optimieren.

Aaron T. Harris
quelle
12
Double Tilde wurde in Perl 5.10 eingeführt
bis auf weiteres angehalten.
15
@ TennisWilliamson ... und in 5.18 wird es als experimentell angesehen .
Xaerxess
5
Vermeiden Sie Smartmatch im Produktionscode. Es ist instabil / experimentell bis auf weiteres.
Vector Gorgoth
1
Ich finde es auch besser lesbar, aber Do not use sagt, dass es nicht effizient ist und überprüft jedes Element, auch wenn es das erste ist.
Giordano
7
Verwenden Sie nicht if ("value" ~~ @array). ~~ ist eine experimentelle Funktion namens Smartmatch. Das Experiment scheint als fehlgeschlagen zu gelten und wird in einer zukünftigen Version von Perl entfernt oder geändert.
Yahermann
120

Sie können die Smartmatch-Funktion in Perl 5.10 wie folgt verwenden:

Für die Suche nach wörtlichen Werten reicht es aus, wenn Sie unten nachschlagen.

if ( "value" ~~ @array ) 

Für die skalare Suche funktioniert das Ausführen von unten wie oben.

if ($val ~~ @array)

Für Inline-Arrays, die unten ausgeführt werden, funktioniert dies wie oben.

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

In Perl 5.18 ist Smartmatch als experimentell gekennzeichnet. Daher müssen Sie die Warnungen deaktivieren, indem Sie das experimentelle Pragma aktivieren, indem Sie Folgendes zu Ihrem Skript / Modul hinzufügen:

use experimental 'smartmatch';

Alternativ, wenn Sie die Verwendung von Smartmatch vermeiden möchten - dann, wie Aaron sagte, verwenden Sie:

if ( grep( /^$value$/, @array ) ) {
  #TODO:
}
Bitmap
quelle
4
Das ist schön, scheint aber neu in Perl 5.10 zu sein. Es hat einige Zeit gedauert, bis ich herausgefunden habe, warum ich Syntaxfehler bekomme.
Igor Skochinsky
17
Warnung: Möglicherweise möchten Sie diese vermeiden, da der Operator in verschiedenen Versionen anscheinend ein unterschiedliches Verhalten aufweist und in der Zwischenzeit als experimentell markiert wurde . Wenn Sie also nicht die volle Kontrolle über Ihre Perl-Version haben (und wer das hat), sollten Sie dies wahrscheinlich vermeiden.
Labyrinth
1
Ich mag diese Erklärung, warum die Einstellung use experimental 'smartmatch'empfohlen wird. Da ich die Kontrolle über meine Perl-Version (internes System) habe, verwende ich die no warnings 'experimental::smartmatch';Anweisung.
Lepe
43

Dieser Blog-Beitrag beschreibt die besten Antworten auf diese Frage.

Kurz gesagt, wenn Sie CPAN-Module installieren können, sind die am besten lesbaren Lösungen:

any(@ingredients) eq 'flour';

oder

@ingredients->contains('flour');

Eine häufigere Redewendung ist jedoch:

any { $_ eq 'flour' } @ingredients

Aber bitte nutzen Sie die first()Funktion nicht! Es drückt überhaupt nicht die Absicht Ihres Codes aus. Verwenden Sie nicht den ~~Operator "Smart Match": Er ist defekt. Und verwenden Sie grep()weder die Lösung noch einen Hash: Sie durchlaufen die gesamte Liste.

any() wird aufhören, sobald es Ihren Wert findet.

Weitere Informationen finden Sie im Blog-Beitrag.

Maskip
quelle
8
irgendwelche Bedürfnisseuse List::Util qw(any);. List::Utilist in Kernmodulen .
Onlyjob
13

Methode 1: grep (kann vorsichtig sein, wenn erwartet wird, dass der Wert ein regulärer Ausdruck ist).

Vermeiden Sie die Verwendung grep, wenn Sie sich Ressourcen ansehen.

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

Methode 2: Lineare Suche

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

Methode 3: Verwenden Sie einen Hash

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

Methode 4: Smartmatch

(hinzugefügt in Perl 5.10, markiert ist experimentell in Perl 5.18).

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

Methode 5: Verwenden Sie das Modul List::MoreUtils

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

@ eakssjos Benchmark ist gebrochen - Maßnahmen zum Erstellen von Hashes in Schleifen im Vergleich zum Erstellen von regulären Ausdrücken in Schleifen. Feste Version (plus ich habe hinzugefügt List::Util::firstund 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} );
        },
    });

Und Ergebnis (es ist für 100_000 Iterationen, zehnmal mehr als in @ eakssjos Antwort):

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
quelle
6
Wenn Sie auf mehrere Elemente testen möchten, sparen Sie Zeit, indem Sie den Hash im Voraus erstellen. Wenn Sie jedoch nur wissen möchten, ob es ein einzelnes Element enthält, haben Sie den Hash noch nicht. Daher sollte das Erstellen des Hashs Teil der Rechenzeit sein. Noch mehr für den regulären Ausdruck: Sie benötigen für jedes Element, nach dem Sie suchen, einen neuen regulären Ausdruck.
fishinear
1
@fishinear Stimmt, aber wenn Sie nur an einer Prüfung interessiert sind, nicht an mehreren Prüfungen, dann ist es natürlich eine Mikrooptimierung, sich überhaupt zu fragen, welche Methode schneller ist, da diese Mikrosekunden keine Rolle spielen. Wenn Sie diese Prüfung wiederholen möchten, ist Hash der richtige Weg, da die Kosten für die Erstellung von Hash einmal so gering sind, dass sie ignoriert werden können. Die oben genannten Benchmarks messen nur verschiedene Testmethoden, ohne Setup. Ja, dies kann in Ihrem Anwendungsfall ungültig sein, aber auch hier gilt: Wenn Sie nur eine einzige Überprüfung durchführen, sollten Sie das verwenden, was für Sie und Ihre Freunde am besten lesbar ist.
Xaerxess
10

Obwohl es bequem zu bedienen ist, scheint es, dass die Konvertierung in Hash-Lösung ziemlich viel Leistung kostet, was für mich ein Problem war.

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

Ausgabe des Benchmark-Tests:

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
quelle
5
Die Verwendung List::Util::firstist schneller, da die Iteration beendet wird, wenn eine Übereinstimmung gefunden wird.
RobEarl
1
-1 Ihr Benchmark weist Fehler auf, grepist erheblich langsamer als das Erstellen von Hashs und das Durchführen von Suchvorgängen, da erstere O (n) und letztere O (1) sind. Führen Sie die Hash-Erstellung nur einmal durch (außerhalb der Schleife) und berechnen Sie den regulären Ausdruck vorab, um nur Methoden zu messen ( siehe meine Antwort ).
Xaerxess
4
@Xaerxess: In meinem Fall wollte ich eine Suche durchführen, daher denke ich, dass es fair ist, sowohl die Hash- / Regex-Erstellung als auch die Suche / Grep zu zählen. Es wäre die Aufgabe, viele Suchvorgänge durchzuführen. Ich denke, Ihre Lösung ist besser.
Aksel
3
Wenn Sie nur eine Iteration durchführen möchten, ist der Unterschied zwischen den von Ihnen ausgewählten Methoden nicht zu unterscheiden. Daher ist jeder Benchmark falsch, da es sich in diesem Fall um eine böse Mikrooptimierung handelt.
Xaerxess
2
Der Regex wird nur einmal kompiliert, da er das Flag 'o' hat.
Apoc
3

@files ist ein vorhandenes Array

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 ab 2 hier können Sie jeden regulären Ausdruck setzen

Rohan
quelle
2

Sie wollen hier sicher einen Hash. Platzieren Sie die fehlerhaften Parameter als Schlüssel im Hash und entscheiden Sie dann, ob ein bestimmter Parameter im Hash vorhanden ist.

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

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

Wenn Sie wirklich daran interessiert sind, dies mit einem Array zu tun, schauen Sie sich List::Utiloder anList::MoreUtils

David M.
quelle
0

Es gibt zwei Möglichkeiten, dies zu tun. Sie können die Werte in einen Hash für eine Nachschlagetabelle werfen, wie in den anderen Beiträgen vorgeschlagen. (Ich werde nur eine weitere Redewendung hinzufügen.)

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

Wenn es sich jedoch um Daten handelt, die hauptsächlich aus Wortzeichen und nicht zu vielen Metas bestehen, können Sie sie in eine Regex-Abwechslung kopieren:

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

Diese Lösung müsste auf die Arten von "schlechten Werten" abgestimmt werden, nach denen Sie suchen. Und wieder, es könnte für bestimmte Arten von Saiten völlig ungeeignet sein, also Vorbehalt Emptor .

Axeman
quelle
1
Sie können auch schreiben @bad_param_lookup{@bad_params} = (), aber Sie müssen verwenden exists, um die Mitgliedschaft zu testen.
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";
    }
}

Möglicherweise möchten Sie die Konsistenz numerischer führender Leerzeichen überprüfen

Serge
quelle