Sortierproblem
Jan Schmidt
ich habe ein groï¿œes Array mit Strings der Form
/#(\d*):(.*) \((.*)\)/
Wie sortiere ich das am geschicktesten zuerst nach $3 und dann nach $1?
Bsp:
#1: a (b)
#2: b (a)
#3: b (b)
soll werden:
#2: b (a)
#1: a (b)
#3: b (b)
Ich hab das jetzt so gemacht, dass ich einen Hash erzeugt habe, der die
Strings als values und eine fortlaufende Nummer als keys hat. Damit ist
zumindest die erste Aufgabe leicht zu lï¿œsen aber fï¿œr das sortieren nach
der Zahl mￜￜte ich dann das sortierte Array nochmal elementweise
durchgehen, Gruppen bilden (z.B. ein temporï¿œres Array) und dann das
Array sortieren.
Das muￜ doch auch einfacher gehen. Vielen Dank fￜr Anregungen.
jan
Martin Vorlaender
> ich habe ein groï¿œes Array mit Strings der Form
>
> /#(\d*):(.*) \((.*)\)/
>
> Wie sortiere ich das am geschicktesten zuerst nach $3 und dann nach $1?
>
> Bsp:
> #1: a (b)
> #2: b (a)
> #3: b (b)
>
> soll werden:
>
> #2: b (a)
> #1: a (b)
> #3: b (b)
>
>
> Das muￜ doch auch einfacher gehen. Vielen Dank fￜr Anregungen.
Stichwort "Schwartz'sche Transformation" [1]:
my @sorted =
map { $_->[0] }
sort { $a->[3] cmp $b->[3] || $a->[1] cmp $b->[1] }
map { /#(\d*):(.*) \((.*)\)/; [$_, $1, $2, $3] }
@data;
HTH,
Martin
[1] z.B. http://perl-seiten.homepage.t-online.de/html/perl_schw.html
--
One OS to rule them all | Martin Vorlaender | OpenVMS rules!
One OS to find them | work: m...@pdv-systeme.de
One OS to bring them all | http://vms.pdv-systeme.de/users/martinv/
And in the Darkness bind them.| home: martin.v...@t-online.de
Alexander Dahl
> Wie sortiere ich das am geschicktesten zuerst nach $3 und dann nach $1?
Was Du suchst ist ein sogenannter stabiler Sortieralgorithmus. Dann
sortierst Du zweimal mit dem jeweiligen Kriterium über die Liste,
fertig. Zucker wäre dann noch Anwendung der Schwartz-Transformation.
Stabile Sortierung mit Perls eingebautem sort realisierst Du über
use sort 'stable';
Schwartz-Transformation sollte über Google genug zu finden sein. O:-)
Gruß
Alex
--
***** http://blog.antiblau.de/ *****************************
GnuPG-FP: 02C8 A590 7FE5 CA5F 3601 D1D5 8FBA 7744 CC87 10D0
Peter J. Holzer
> ich habe ein gro�es Array mit Strings der Form
>
> /#(\d*):(.*) \((.*)\)/
>
> Wie sortiere ich das am geschicktesten zuerst nach $3 und dann nach $1?
>
> Bsp:
> #1: a (b)
> #2: b (a)
> #3: b (b)
>
> soll werden:
>
> #2: b (a)
> #1: a (b)
> #3: b (b)
Der naive Ansatz:
@array = sort {
my ($a1, $a2, $a3) = $a =~ /#(\d*):(.*) \((.*)\)/;
my ($b1, $b2, $b3) = $b =~ /#(\d*):(.*) \((.*)\)/;
return $a3 cmp $b3 || $a1 <=> $b1;
}
@array;
Aber das ist nicht besonders effizient, denn es splittet bei jedem
Vergleich beide Strings. Das kann man u.A. mit der Schwartzian Transform
vermeiden:
@array = map { $_->[-1] }
sort { $a->[0] cmp $b->[0] || $a->[1] <=> $b->[1] }
map {
/#(\d*):(.*) \((.*)\)/;
[ $3, $1, $_]
}
@array;
Das ist von hinten nach vorne zu lesen:
Zuerst mappt man jedes Element auf ein Tripel, das aus den zwei
Sortierschl�sseln und dem urspr�nglichen Element besteht,
dann wird nach den Sortierschl�sseln sortiert und schlie�lich wird das
urspr�ngliche Element wieder extrahiert.
Wenn Du z.B. wei�t, dass die Strings nie einen Null-Character ("\0")
enthalten und $1 immer Zahlen mit maximal 10 Stellen sind, dann kann man
statt das anonymen Arrays das ganze in einen String packen. Das spart
Platz und Rechenzeit:
@array = map { my (undef, undef, $s) = split(/\0/, $_, 3; $s }
sort
map {
/#(\d*):(.*) \((.*)\)/;
sprintf("%s\0%010d\0%s", $3, $1, $_;
}
@array;
(Das nennt sich glaube ich Guttman-Rosler Transformation.)
In diesem Fall ist aber der Aufwand die Keys zu splitten deutlich
kleiner als der Overhead der Transformationen, so dass (zumindest auf
meinem System und bei Arraygr��en bis 1 Mio. Elemente) der naive Ansatz
tats�chlich der schnellste ist.
hp
PS: Es gibt auch das Modul Sort::Maker, das Sortierfunktionen
automatisch auch einer Beschreibung der Keys generiert. M�glicherweise
produziert das etwas schnelleres als meinen handgeschriebenen Code.
Jan Schmidt
>>
>> /#(\d*):(.*) \((.*)\)/
>>
>> Wie sortiere ich das am geschicktesten zuerst nach $3 und dann nach $1?
danke an alle - das werde ich mir morgen mal zu Gemüte führen.
jan