Sortieren optimieren

Hallo,
man ist ja immer bemüht seinen Code zu optimieren und lesbar zu
halten ;-)
Das Muster ist immer ^[A-Z][1-9][_a-z]\d\d$ und soll in eine
bestimmte Reihenfolge (nicht das einfache 'sort') gebracht werden.
Kann mann die Arbeit 'besser machen'?

#-----8<-----8<-----
my @dream = ("K1_01", "K1_02", "K1a02", "K1b02", "K1_03", "K2_02");
my @unsort = ("K1_03", "K2_02", "K1a02", "K1_01", "K1_02", "K1b02");

print "So solls nachher aussehen:\n".join("\n", @dream)."\n\n";
print "Vorher:\n".join("\n", @unsort)."\n\n";
#-------------------
# drittes Zeichen nach hinten retten und durch 'Z' ersetzen
foreach ( @unsort )
{ substr($_, 5) = substr($_, 2, 1, "Z"); }

@unsort = sort @unsort; # jetzt sortieren

# gerettetes Zeichen wieder vor und hinten abschneiden
foreach ( @unsort )
{ substr($_, 2, 1, substr($_, -1)); chop; }
#-------------------
print "Nachher:\n".join("\n", @unsort)."\n\n";
#-----8<-----8<-----

Dank für jeden Tipp!
--
Mit freundlichen Grüßen
*WOL* fgang *S* chricker

Re: Sortieren optimieren

WOLfgang Schricker!

> Das Muster ist immer ^[A-Z][1-9][_a-z]\d\d$ und soll in eine
> bestimmte Reihenfolge (nicht das einfache 'sort') gebracht werden.
> Kann mann die Arbeit 'besser machen'?
>
> #-----8<-----8<-----
> my @dream = ("K1_01", "K1_02", "K1a02", "K1b02", "K1_03", "K2_02");
> my @unsort = ("K1_03", "K2_02", "K1a02", "K1_01", "K1_02", "K1b02");
>
> print "So solls nachher aussehen:\n".join("\n", @dream)."\n\n";
> print "Vorher:\n".join("\n", @unsort)."\n\n";
> #-------------------

@unsort = sort { (substr($a,0,2).substr($a,3).substr($a,2,1)) cmp
(substr($b,0,2).substr($b,3).substr($b,2,1)) } @unsort;

> #-------------------
> print "Nachher:\n".join("\n", @unsort)."\n\n";
> #-----8<-----8<-----
>
> Dank für jeden Tipp!


Gruss
Daniel

Re: Sortieren optimieren

Daniel Fischer schrieb:
> WOLfgang Schricker!
>
>> Das Muster ist immer ^[A-Z][1-9][_a-z]\d\d$ und soll in eine
>> bestimmte Reihenfolge (nicht das einfache 'sort') gebracht werden.
>> Kann mann die Arbeit 'besser machen'?
>>
>> #-----8<-----8<-----
>> my @dream = ("K1_01", "K1_02", "K1a02", "K1b02", "K1_03", "K2_02");
>> my @unsort = ("K1_03", "K2_02", "K1a02", "K1_01", "K1_02", "K1b02");
>>
> @unsort = sort { (substr($a,0,2).substr($a,3).substr($a,2,1)) cmp
> (substr($b,0,2).substr($b,3).substr($b,2,1)) } @unsort;

Moin!

Dein Code mag vielleicht etwas lesbarer sein, aber ob er auch
effizienter ist? Das wage ich zu bezweifeln, denn es muss bei jedem
Vergleich der neue zu vergleichende String zusammengesetzt werden.

Die Lösung von Wolfgang würde ich als "Poor Man's Map" bezeichnen, er
macht ja im Prinzip das, wozu man normalerweise die
map-sort-map-Kombination (Schwartzsche Transf.) einsetzt. Es ist daher
vermutlich besser.

Wolf

Re: Sortieren optimieren

Thus spoke WOLfgang Schricker (on 2006-06-22 20:38):

Hallo Wolfgang

> man ist ja immer bemüht seinen Code zu optimieren und lesbar zu
> halten ;-)
> Das Muster ist immer ^[A-Z][1-9][_a-z]\d\d$ und soll in eine
> bestimmte Reihenfolge (nicht das einfache 'sort') gebracht werden.
> Kann mann die Arbeit 'besser machen'?

Das ist _der_ Anwendungsfall für 'decorate/undecorate sort'
aka "Schwartzian Transform", wie Wolf schon angedeutet hat.

==>

@comestrue =

map { join '', (split //)[0,1,4,2,3] }
sort
map { join '', (split //)[0,1,3,4,2] }

@unsort;

<==
K1_01
K1_02
K1a02
K1b02
K1_03
K2_02


Die Idee dabei ist, in der Sort-routine
auf einem konstanten Feld zu sortieren
weil sort bei großen N teuer sein wird.
(Im Prinzip hattest Du es ja bereits
so ähnlich gemacht).

Viele Grüße

Mirco

Re: Sortieren optimieren

Mirco Wahab wrote:
> Thus spoke WOLfgang Schricker (on 2006-06-22 20:38):
> Hallo Wolfgang
>
>> man ist ja immer bemüht seinen Code zu optimieren und lesbar zu
>> halten ;-)
>> Das Muster ist immer ^[A-Z][1-9][_a-z]\d\d$ und soll in eine
>> bestimmte Reihenfolge (nicht das einfache 'sort') gebracht werden.
>> Kann mann die Arbeit 'besser machen'?
>
> Das ist _der_ Anwendungsfall für 'decorate/undecorate sort'
> aka "Schwartzian Transform", wie Wolf schon angedeutet hat.
>
> ==>
>
> @comestrue =
>
> map { join '', (split //)[0,1,4,2,3] }
> sort
> map { join '', (split //)[0,1,3,4,2] }
>
> @unsort;

Bei der "Schwartzian Transform" verwendet man allerdings üblicherweise
ein anonyous Array mit zwei Elementen: Dem-Schlüssel und dem
Original-Element. Das hat den Vorteil, dass das Mapping von
Original-Element auf Sortierschlüssel nicht umkehrbar sein muss:

@comestrue =

map { $_->[1] }
sort { $a->[0] cmp $b->[0] }
map { [ join '', (split //)[0,1,3,4,2], $_ ] }

@unsort;

Das funktioniert auch, wenn man z.B. die ersten 3 Zeichen beim Sortieren
vollkommen vernachlässigen will (was ich für eine mögliche
Interpretation des OP halte):

@comestrue =

map { $_->[1] }
sort { $a->[0] cmp $b->[0] }
map { [ substr($_, 3), $_ ] }

@unsort;

hp

--
_ | Peter J. Holzer | Man könnte sich [die Diskussion] auch
|_|_) | Sysadmin WSR/LUGA | sparen, wenn man sie sich einfach sparen
| | | hjp@hjp.at | würde.
__/ | http://www.hjp.at/ | -- Ralph Angenendt in dang 2006-04-15

Re: Sortieren optimieren

Wolf Behrenhoff!

> Dein Code mag vielleicht etwas lesbarer sein, aber ob er auch
> effizienter ist? Das wage ich zu bezweifeln, denn es muss bei jedem
> Vergleich der neue zu vergleichende String zusammengesetzt werden.

Da hast Du ganz bestimmt Recht, mir ging es aber auch nur um die
Lesbarkeit. Performanceoptimierung ist nur bei genauerer Kenntnis der
Ausgangslage möglich.


Gruß
Daniel

Re: Sortieren optimieren

Thus spoke Peter J. Holzer (on 2006-06-23 11:00):

> Mirco Wahab wrote:
>> Das ist _der_ Anwendungsfall für 'decorate/undecorate sort'
>> aka "Schwartzian Transform", wie Wolf schon angedeutet hat.
>
> Bei der "Schwartzian Transform" verwendet man allerdings üblicherweise
> ein anonyous Array mit zwei Elementen: Dem-Schlüssel und dem
> Original-Element. Das hat den Vorteil, dass das Mapping von
> Original-Element auf Sortierschlüssel nicht umkehrbar sein muss:

Stimmt.

OK, so habe ich das auch in Erinnerung, dies aber dann
wahrscheinlich den Begriff "unzulässig" in meine Richtung
hin generalisiert ...

> @comestrue =
>
> map { $_->[1] }
> sort { $a->[0] cmp $b->[0] }
> map { [ join '', (split //)[0,1,3,4,2], $_ ] }
>
> @unsort;

Ja, das wäre die "richtige Schwartzsche Transformation",
die vollständig mit einer zusätzlichen Indirektion
arbeitet.

Man könnte hier eigentlich auch auf externem
Hash sortieren (der Vollständigkeit halber):


my ($key, %ktb);

@comestrue =
map { $ktb{$_} }
sort
map {
$ktb{ ($key=join '',(split //)[0,1,3,4,2]) } = $_;
$key
}
@unsort;


Ist aber wahrscheilich vom konkreten
Problem abhängig, was man nehmen würde.

Danke & viele Grüße

Mirco