/blog/perl


substr() in Perl
[153892 mal gelesen]
foreach in Perl
[129113 mal gelesen]
Arrays in Perl - Besonderheiten
[125269 mal gelesen]
split() in Perl - Zeichenketten teilen
[113418 mal gelesen]
open() - Dateien öffnen in Perl
[108924 mal gelesen]
grep - Listen durchsuchen in Perl
[94637 mal gelesen]
chomp() in Perl
[93594 mal gelesen]
push in Perl
[90800 mal gelesen]
sleep in Perl - Das aktuelle Script warten lassen
[75927 mal gelesen]
index() in Perl - Zeichenkette in Zeichenkette suchen
[59439 mal gelesen]


Arrays
Dateien
HTPC
Hashes
Leistungsoptimiert
PHP
Perl
RegEx
Schleifen
Script
Skalare
Sonstiges
System
Webserver
Zur Startseite


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.



Kommentare zum Beitrag "Doppelte Einträge aus Array entfernen in Perl"

Kommentar von Harald Mattern

Eine schnellere Methode

sub del_double
{ my %seen;
return grep{ not $seen{$_}++ } @_;
}



Kommentar von Perl-Hasser
igitt

Kommentar von ceyhant
sub del_double{

return keys %{{ map { $_ => 1 } @_ }};

}

Kommentar von Admin

Sorry, aber ein Test mit Benchmark und folgenden Code bei 1.000.000 Array-Werten

timethis (5, sub{@b=del_double(@a)});
timethis (5, sub{@b=keys %{{ map { $_ => 1 } @a }}});


ergibt, daß Deine Methode fast halb so langsam ist wie meine Originalmethode...

Kommentar von Mr. T
die Geschichte scheint etwas schneller zu sein



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



Kommentar von Admin
Bingo!
Diese Variante ist tatsächlich schneller.

Mit meiner Variante läuft ein durchlauf mit 1 Mio zufälligen Werten laut Benchmark 1.79 mal pro Sekunde, mit der neuen Variante 2.56 mal pro Sekunde. Dies ist ein Geschwindigkeitsvorteil von fast 50%.

Bravo und dankeschön!

Kommentar von Basti
Hallo ich habe mal eine Frage zu euren Vorschlägen.

Mein Problem ist, dass ich knapp 1300 Zeilen mit je 2 Spalten Koordinatenzahlen habe und nun die doppelten aussortieren möchte. Mit den Lösungen in diesem Forum geht das auch soweit wirklich prima, jedoch darf sich die Reihenfolge nicht verändern....

Hat hierzu jemand vielleicht einen Vorschlag? Ich wäre euch sehr dankbar, habe erst vor zwei Wochen mit Perl angefangen und aus dem Studium nur geringe C++ Kenntnisse... Bin also was das Programmieren betrifft noch ungeübt. Mein Programm bis dahin steht zwar, aber das bereitet mir jetzt Probleme.

Danke Grüße

Kommentar von Admin

Das Problem ist etwas mißverständlich beschrieben...

Hast Du Daten in Form
52.22N 10.47E
34.33N 11.34E
17.24N 59.32E
52.22N 10.47E
11.45N 34.37E
?

Wenn ja, würde folgendes helfen:

my %seen;
my @unique = grep{ ! $seen{$_}++ }@array;


Alle doppelten Elemente, die in der ersten UND zweiten Spalte übereinstimmen, werden ausgefiltert.

Hast Du Daten in der obigen Form und es darf das Erste ODER das Zweite nicht doppelt sein, hilft folgendes weiter:

@daten=<DATA>;
chomp @daten;

foreach (@daten){
($dat1,$dat2)=split(" ",$_);
if ($dat1{$dat1} != 1 && $dat2{$dat2} != 1){
push @unique,$_;
}
$dat1{$dat1}=1;
$dat2{$dat2}=1;
}

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


__DATA__
52.22N 10.47E
34.33N 11.34E
17.24N 59.32E
52.22N 10.47E
11.45N 34.37E


(Etwas ausführlich gescripted, könnte man sicherlich noch zusammmenfassen...)

Kommentar von Basti
Danke für die schnelle Antwort. Ich werde es gleich mal genauer anschauen und ausprobieren.

Das Problem ist folgendes:

Ich habe Koordinaten in folgender Form

23.344562; {TAB} 45.33412
....
....
....
23.344562; 45.33412



die doppelten sind also mehr oder weniger zufällig verteilt. Jetzt soll die erste der doppelten oder gar drei bis vierfach vorhandenen Zeilen erhalten bleiben.
Wichtig ist ausserdem, dass die Reihenfolge der gesamten Liste ebenfalls identisch bleibt.

Ich hoffe, dass es nun besser verständlich ist. Danke nochmal :)

Kommentar von basti
oh jetzt hab ich verstanden was sie meinten... :)

Ja es müssen erste UND zweite Spalte einer Zeile mit der ersten UND zweiten Spalte einer anderen Zeile übereinstimmen, damit der "lösch-Befehl" erteilt werden soll.

Ich probier das erste gleich mal aus.

gruß

Kommentar von Struppi

Das ist übrigesn eine Perl FAQ (steht also in jeder Perl Doku)
http://faq.perl.org/perlfaq4.html# How_can_I_remove_dup

und die schnelste Möglichkeit heißt Hash-Slice

Man muss schon echter Perl Hasser sein um sowas nicht zu mögen ;-)

Kommentar von Basti
also vielen Dank noch einmal, hat alles prima geklappt und ich hab nun meine Koordinatenliste.

Jetzt habe ich aber ein neues kleines Problem, an dem ich irgendwie im Moment hänge:

ich habe jetzt eine .txt Datei, mit folgendem Aufbau:

Xkoordinate; Ykoordinate; Zkoordinate
Xkoordinate; Ykoordinate; Zkoordinate
....


etwa 1900mal :)


ich will nun die Reihenfolge ändern und zwar zuerst nach der Ykoordinate in aufsteigender Richtung und dann nach der Xkoordinate, ebenfalls in aufsteigender Richtung Sortiert.

dabei soll das Ergebnis der Drei Spalten wieder in die .txt Datei geschrieben werden. (am besten die .txt Datei überschreiben)

hat wer eine Lösung hierfür? Stehe da momentan aufm Schlauch... oder es ist einfach schon zu Spät heut.

Ich danke euch schon einmal und wünsche ein schönes Wochenende :)

Kommentar von Admin

Hi Basti,

Hier erstmal Deine Lösung:

@data=<DATA>;
print join("\n",sortieren(@data));

sub sortieren{

my @zeilen=@_;
my @sortiert = ( map { $_="$_->[0]\; $_->[1]\; $_->[2]" }
sort { $a->[1] cmp $b->[1] || $a->[0] cmp $b->[0] }
map { [split /\; /] }
@zeilen );

return @sortiert;

}

__DATA__
52.22; 09.44; 33.35
11.12; 13.14; 15.16
11.11; 13.14; 15.16
11.16; 13.14; 15.16
11.16; 13.15; 15.16


Wie gewünscht nach y, dann x, z wird nicht beachtet.

Wie das funktioniert kannst Du später hier im Blog Schwartzsche Transformation lesen.
Oder hier, wo die Schwartzsche Transformation schonmal angesprochen wurde

Kommentar von Basti
Oh man ihr seit echt klasse!

Danke! Das hilft mir sehr weiter. Mit dem wie und warum werd ich mich später auf jedenfall beschäftigen, jetzt gilts erstmal meine Arbeit abzugeben :)

Kommentar von Basti
Hallo nochmal.

Ich habe mein Programm entsprechend angepasst und nun kommt folgende Fehlermeldung:

Can't use an undefined value as an ARRAY reference at ...


die Zeile des Fehlers:

my @sortiert = ( map { $_="$_->[0]\; $_->[1]\; $_->[2]" }

Ich weiss jetzt nicht, ob das ganze zu "herausgerissen" aus meinem gesamten Programm ist und deshalb nicht zu beantworten ist, aber ich habe mir jetzt fast 3Stunden alles genau angeschaut und durchgelesen und komme nicht weiter.

Grüße

Kommentar von Admin

Hi Basti,

der Code den ich oven gepostet habe war wohl ein bißchen buggi, weiss auch nicht wo ich den mal verwendet habe...

Hier der neue Code, der sollte auf jeden Fall laufen

@data=<DATA>;
print join("\n",sortieren(@data));

sub sortieren{

my @zeilen=@_;
my @sortiert = map { $_->[0] }
sort { $a->[1] cmp $b->[1] || $a->[0] cmp $b->[0] }
map { [$_,(split (/\; /,$_))[1,2]] } @zeilen ;

return @sortiert;

}

__DATA__
52.22; 09.44; 33.35
11.12; 13.14; 15.16
11.11; 13.14; 15.16
11.16; 13.14; 15.16
11.16; 13.15; 15.16



Ich hoffe jetzt klappts...

Mehr zur Schwartzschen Transformation gibts hier zu lesen

Kommentar von perler
Wie kann man doppelte Einträge aus einem Array entfernen und dabei die Ordnung des Arrays beibehalten?


Kommentar von Admin
Mehr zur Beibehaltung der Reihenfolge gibt es
hier zu sehen.



Thema: Perl Arrays Leistungsoptimiert

Der Beitrag "Doppelte Einträge aus Array entfernen in Perl" wurde 26151 mal gelesen.

Es wurde 14 x über diesen Beitrag abgestimmt.
Die durchschnittliche Beurteilung liegt bei
1.5 (1 = sehr gut - 6 = grottenschlecht).

Kommentar schreiben  Druckansicht  Seitenanfang 
Beurteilen 






 Zufällige Beiträge im /blog/perl

abs() in Perl

Wiederholungen finden mit regulären Ausdrücken

Mac-Adresse beim Apple Macintosh herausfinden

chdir - Aktuelles Arbeitsverzeichnis definieren

crypt() in Perl - Zeichenketten verschlüsseln

Datei komplett einlesen - Die exotische Variante

LWP::Simple - Modulbeschreibung in Deutsch



0.0238339900970459 sec. to build



...Blogsoftware in pure Perl - Powered by a lot of Coffee...


SSD-Festplatte - Wassn das???
Die Transliteration - Nur ein Zeichen in einem Skalar ersetzen
Select - Case in Perl
Windows 7 XP Mode – Wo finde ich den XP-Modus unter Windows 7?
Mac-Adresse beim Apple Macintosh herausfinden
SGN-Funktion für Perl

Eigene IP herausfinden mit Perl
Epoche live in Datum umwandeln
Firefox 3 - Exe-Files downloaden


Gesamtverzeichnis
Februar 2010
Dezember 2009
Oktober 2009
Januar 2009
Dezember 2008
November 2008
September 2008
August 2008
Juli 2008
Juni 2008
Mai 2008
April 2008
Januar 2008
Dezember 2007
November 2007
Oktober 2007
September 2007
August 2007
Juni 2007
Mai 2007
April 2007
März 2007
Februar 2007
Januar 2007
Dezember 2006


Mister Wong

RSS-Feed

Heute ist der
11.10.2024

Es ist
22:49:03 Uhr

Ihre IP:
3.236.86.184

Blog-Einträge: 186

Die letzten 24 Stunden im Überblick


Gelesene Beiträge insgesamt:
4418485


Webseiten vergleichen
Kalender mit Feiertagen - 2028
Links finden und testen
Menschliche Datumsangaben
IP zu Domain herausfinden
Time live in Datum umwandeln
Perl für Windows



Impressum