Artikel im Internet unter http://www.hidemail.de/blog/doppelte-eintraege-array.shtml.
Freitag, 2.2.2007, 13:38:21 Uhr

Doppelte Einträge aus Array entfernen mit Perl


Ich hab mir da mal eine Funktion geschrieben, die aus einem Array schnell alle doppelten Werte herausfiltert.
Schnell bedeutet übrigens: Ich habe verschiedene Möglichkeiten auf Ihre Schnelligkeit hin getestet und diese war die Schnellste...

Code:

sub del_double{ #Parameter: @liste, die aussortiert werden soll
my %all;
grep {$all{$_}=0} @_;
return (keys %all);
}


Aufgerufen wird das Ganze mit

@array=&del_double(@array);

Und wie funktioniert das nun?
Übergeben wird das gewünschte Array. Danach wird über den grep-Befehl jeder Wert durchgegangen und einem temporären Hash als Key zugewiesen. Das Value ist übrigens in diesem Zusammenhang egal.
Wen alle Werte durch sind, werden alle Keys des Hashes als neues Array zurückgegeben. Fertig!

Vorsicht
Die Reihenfolge des Arrays wird verändert!

Für schnellere Methoden bin ich übrigens dankbar!


Aktualisierung
Ein Leser schrieb unten eine schnellere Methode, hier der Code:

sub del_double
{
my %all;
$all{$_}=0 for @_;
return (keys %all);
}



Dieser Code ist fast 50 % schneller als mein bisheriger Spitzenreiter.
Danke nochmals!

Natürlich bin ich aber immer noch dankbar für noch schnellere Methoden.


Der Code zum benchmarken ist übrigens folgender:

use Benchmark qw(:all) ;

for ($i=0;$i<1000000;$i++){push @a,int(rand(1000));}

timethis (5, sub{@b=del_double(@a)}); # original-Code
timethis (5, sub{$all{$_}=0 for @a; @b=(keys %all);}); # hier neuer Code, der verglichen werden soll




Nachtrag, die 2.
Also, da ich gerade dieses Beispiel prädestiniert dafür halte, über die Vielfältigkeit der Lösungsmöglichkeiten in Perl zu schreiben, habe ich mich nun etwas in die weiten des Webs begeben und nach den schnellsten Lösungsmöglichkeiten gesucht.

Die ultimativ schnellste Möglichkeit scheint folgende zu sein:

sub del_double{
my %all=();
@all{@_}=1;
return (keys %all);
}



Diese Methode verzichtet ganz auf irgendwelche grep's, for's oder foreach's, sondern weist dem Hash %all direkt die keys zu, die aus dem übergebenen Array stammen.

Der Geschwindigkeitsvorteil ist gravierend:
Meine Originalmethode: 4.42 x pro Sekunde
Die bessere Methode von gestern: 5.9 x pro Sekunde
Die ganz neue Methode: 8 x pro Sekunde

Also ist die neueste Methode fast doppelt so schnell als meine erste... naja, auf die Idee muß man aber auch erst mal kommen.

Und wie geht es nun?
Nunja, das ist schnell beschrieben:
Das übergebene Array in @_ füllt den Hash mit den keys aus @_ und den Values 1(die völlig egal sind, man hätte auch sonstwas nehmen können).

Das das funktioniert war mir neu, aber man sollte sich bei Perl glaube ich eh' abgewöhnen, sich zu wundern...

Gefunden hab ich die neue Methode übrigens auf Perlmonks.org, einer wahren Fundgrube über Perl.

Artikel im Internet unter http://www.hidemail.de/blog/doppelte-eintraege-array.shtml.