Tabellen sortieren

Post removed (X-No-Archive: yes)

Re: Tabellen sortieren

Martin Trautmann wrote:

> Ich habe eine Tabelle mit z.B.

> ID A B
> 1 Aa E
> 2 Aa D
> 3 Ab D
> 4 Ac C

> ich wuerde die Tabelle nun gerne nach zuerst Spalte B, dann Spalte A
> sortieren

Wie liegt die Tabelle vor (Array, Datei)?

> Im Moment bin ich geneigt, das ganze erst mal in Text umzuwandeln, z.B.
> E+Aa+01
> D+Aa+02
> D+Ab+03
> C+Ac+04

Das ist gefährlich, wenn die Werte der Spalten A und B verschieden lange
Strings enthalten können.

Ich würde bei sowas vermutlich zu einem Hash-of-Hash (HoH) greifen, und
dann mittels eines verschachtelten

foreach my $key_B (sort keys ...) {
foreach my $key_A (sort keys ...) {
...
}
}

abarbeiten.

Irgendetwas anderes mit den Daten wirst ja vermutlich auch machen
wollen, und da kann ein direkter, schneller Zugriff auf einzelne Werte
eines HoH gravierende Vorteile haben. Nur sortieren geht über das
Console-Utility 'sort' schneller.

Helmut Wollmersdorfer

Re: Tabellen sortieren

Am 06.10.2006 13:46 schrieb Martin Trautmann:
> Hallo,
>
> vielleicht stehe ich einfach nur auf dem Schlauch - aber ich habe noch
> nicht raus, wie ich sinnvoll sortiere.
>
> Ich habe eine Tabelle mit z.B.
>
> ID A B
> 1 Aa E
> 2 Aa D
> 3 Ab D
> 4 Ac C
>
> ich wuerde die Tabelle nun gerne nach zuerst Spalte B, dann Spalte A
> sortieren
>
>
> Im Moment bin ich geneigt, das ganze erst mal in Text umzuwandeln, z.B.
> E+Aa+01
> D+Aa+02
> D+Ab+03
> C+Ac+04
>
> Aus den dann per sort() sortieren Daten hole ich mir wieder die
> letzten beiden Stellen der ID, um mir dann aus deren Reihenfolge wieder
>

Angenommen, diese "Tabelle" liegt als Array (@tabelle) von Arrays vor,
dann könnte

sort { $a->[1] cmp $b->[1] || $a->[0] cmp $b->[0]} @tabelle

das Nötige tun.

Falls ich Dich richtig verstanden habe.

Re: Tabellen sortieren

Post removed (X-No-Archive: yes)

Re: Tabellen sortieren

Martin Trautmann schrieb:

> Ich habe eine Tabelle mit z.B.
>
> ID A B
> 1 Aa E
> 2 Aa D
> 3 Ab D
> 4 Ac C

Was ist das? Eine menschenlesbare Perl-Datenstruktur? Eine Datei? ?

> ich wuerde die Tabelle nun gerne nach zuerst Spalte B, dann Spalte A
> sortieren

Und was soll am Ende rauskommen? Eine Perl-Datenstruktur? Eine Datei? ?

Je nach Anforderungen bist mit

- sort(1)
- split // und sort
- DBD::?
- ...

am besten bedient.

> Mit dem sort-module waere das vermutlich einfacher zu bewerkstelligen -

Mein perl hat nur ein sort-Pragma, das wird dir sicher nicht helfen. Oder
was meinst du?

> oder schafft das auch schon das normale sort?

Mit perl geht das schon, wie gesagt -- jenachdem, was du GENAU vorhast.


Frank

Re: Tabellen sortieren

Post removed (X-No-Archive: yes)

Re: Tabellen sortieren

Martin Trautmann wrote:
> On Fri, 06 Oct 2006 14:53:29 +0200, Christian Kirsch wrote:
> > Angenommen, diese "Tabelle" liegt als Array (@tabelle) von Arrays vor,
> > dann könnte
> >
> > sort { $a->[1] cmp $b->[1] || $a->[0] cmp $b->[0]} @tabelle
> >
> > das Nötige tun.
>
> uff, danke, auf sowas waere ich nach der fuer mich noch duerftigen
> Beschreibung aus dem Kamelbuch nicht gekommen. Das muss ich mal
> ausprobieren.
>
> > Falls ich Dich richtig verstanden habe.
>
> Ich glaube schon. Aber kann ich das automatisch rekursiv bekommen,

Nein. Hat damit nichts zu tun.

> je
> nachdem, ob ein, zwei, drei, ... Sortiermerkmale vorgegeben werden?
> Nebenbei ist die Sortierung je nach Feld auch mal numerisch oder text,
> wahlweise auch auf- oder abwaerts.

Die Syntax ist
sort subref @array
bzw.
sort { ... } @array

Was Du in der Vergleichsroutine machst, ist Deine Sache.
Man kann natürlich mehrere vorkonfigurierte Routinen haben und bei
Bedarf die "richtige" übergeben.
Oder man kann aus einer Beschreibung, was und wie sortiert werden soll,
eine dynamische Vergleichsfunktion machen. Je nachdem wie man das
implementiert, kann das dann recht langsam werden. Man muß immer im
Hinterkopf haben, daß diese Vergleichsfunktion sehr oft aufgerufen
wird.

Es ist natürlich aber folgendes denkbar: Man schreibt eine Funktion,
die aus einem String wie "2 1r 3n" folgenden String erzeugt:

# sort 2nd field, then 1st field reverse, then 3rd field numeric
sub {
$a->[1] cmp $b->[1]
|| $b->[0] cmp $a->[0]
|| $a->[2] <=3D> $b->[2]
}

Nehmen wir an, die Funktion heiße cmpcomp. Dann ginge folgendes
(ungetestet):

sort (eval cmpcomp("2 1r 3n")) @tabelle

Der Vorteil ist, daß dann beim Sortieren eine Subroutine aufgerufen
wird, die compiliert ist (durch das eval) und genauso schnell wie eine
"richtige" Subroutine.

Re: Tabellen sortieren

Post removed (X-No-Archive: yes)

Re: Tabellen sortieren

Post removed (X-No-Archive: yes)

Re: Tabellen sortieren

On 2006-10-06 15:28, Martin Trautmann wrote:
> On 6 Oct 2006 08:14:04 -0700, Ingo Menger wrote:
>> Man kann natürlich mehrere vorkonfigurierte Routinen haben und bei
>> Bedarf die "richtige" übergeben.
>
> Das erscheint mir eben als wenig elegant. In dem Fall bevorzuge ich eine
> einfache Holzhammermethode (immer nur ein Sortiermerkmal steht zur
> Verfuegung - dafuer kann aber manuell verkettet sortiert werden ueber
> eine Such-Historie: sortiert wurde nach A, naechste Sortierung
> uebernimmt diese Daten und sortiert diese nach B und erreicht damit eine
> Sortierung nach B-A)

Das funktioniert aber nicht bei allen Sortier-Algorithmen. Bei quicksort
z.B. wird die ursprüngliche Sortierung zerstört, wenn man nach einem
anderen Kriterium sortiert.

Perl 5.8 verwendet m.W. einen stabilen Sortier-Algorithmus (Merge-Sort).
Ältere Versionen von Perl haben eine quicksort-Variante verwendet. Wenn
Du also Sortierungen einfach so verknüpfen willst (was durchaus eine
legitime Variante ist), solltest Du sicherstellen, dass Dein Script nur
mit einer aktuellen Perl-Variante verwendet wird.


>> Oder man kann aus einer Beschreibung, was und wie sortiert werden soll,
>> eine dynamische Vergleichsfunktion machen. Je nachdem wie man das
>> implementiert, kann das dann recht langsam werden. Man muß immer im
>> Hinterkopf haben, daß diese Vergleichsfunktion sehr oft aufgerufen
>> wird.
>
> Etwas in der Art habe ich mir vorgestellt - und genau das befuerchtet,
> dass damit unter Umstaenden alles in die Knie geht.

Es gibt Methoden, das zu verbessern. Stichworte: Orcish Maneuver,
Schwarzian Transform, etc.
Die sind allerdings etwas datenabhängig, d.h. man muss die
Transformation an die zu sortierenden Daten anpassen.


>> Es ist natürlich aber folgendes denkbar: Man schreibt eine Funktion,
>> die aus einem String wie "2 1r 3n" folgenden String erzeugt:
[...]
>> Der Vorteil ist, daß dann beim Sortieren eine Subroutine aufgerufen
>> wird, die compiliert ist (durch das eval) und genauso schnell wie eine
>> "richtige" Subroutine.
>
> Hm, ich werde versuchen, das mal zu verdauen. Neuland. Mal sehen, wie weit ich
> damit komme...

Sowas zu Übungszwecken zu schreiben, ist sicher sehr lehrreich. Zur
Lösung des Problems ist es aber wahrscheinlich zielführender, eines der
fertigen Module wie Sort::Maker zu verwenden, als das Rad neu zu
erfinden.

hp


--
_ | Peter J. Holzer | > Wieso sollte man etwas erfinden was nicht
|_|_) | Sysadmin WSR | > ist?
| | | hjp@hjp.at | Was sonst wäre der Sinn des Erfindens?
__/ | http://www.hjp.at/ | -- P. Einstein u. V. Gringmuth in desd

Re: Tabellen sortieren

Martin Trautmann schrieb:
> On Fri, 06 Oct 2006 15:11:35 +0200, Frank Wiegand wrote:
>
>> Martin Trautmann schrieb:
>>
>>
>>>Ich habe eine Tabelle mit z.B.
>>>
>>>ID A B
>>>1 Aa E
>>>2 Aa D
>>>3 Ab D
>>>4 Ac C
>>
>> Was ist das? Eine menschenlesbare Perl-Datenstruktur? Eine Datei? ?
>
>
> eine Beispieltabelle - hier durch blankspace auf Lesbarkeit getrimmt, im
> Original ein .csv-Format. Derzeit wird's in ein array of arrays
> importiert. Aber Datenquelle und interne Datenhaltung sind noch beliebig
> anpassbar. Letztendlich soll aus einem Speicherformat ein Ausgabeformat
> erzeugt werden - z.B. als HTML-Tabelle oder wie mit diesen Beispieldaten
> eine Festbreitentabelle.
>
>
>>>ich wuerde die Tabelle nun gerne nach zuerst Spalte B, dann Spalte A
>>>sortieren
>>
>> Und was soll am Ende rauskommen? Eine Perl-Datenstruktur? Eine Datei? ?
>
>
> eine umsortierte Tabelle - also z.B. die Kenntnis: neue Sortierfolge ist
> dann ID {4 2 3 1}, um dann arrayweise eine Tabelle zu erzeugen.
>
> Ob das aber nun intern (array|hash) of (array|hash) ist, das ist mir
> recht egal. Das Problem ist schlichtweg die Umwandlung von Rohdaten in
> sortierte Enddaten zur tabellarischen Darstellung (Festbreitentabelle,
> HTML-Tabelle, Speicherformat .csv usw.)
>
>
>> Je nach Anforderungen bist mit
>>
>> - sort(1)
>> - split // und sort
>> - DBD::?
>> - ...
>>
>> am besten bedient.
>
>
> split verwende ich derzeit zum konvertieren von Rohdaten in arrays.
> sort habe ich moeglicherweise noch nicht ausreichend durchschaut, wie
> ich damit eine ganze Tabelle nach einem oder mehreren Merkmalen
> sortieren kann.
>
>
>>>Mit dem sort-module waere das vermutlich einfacher zu bewerkstelligen -
>>
>> Mein perl hat nur ein sort-Pragma, das wird dir sicher nicht helfen. Oder
>> was meinst du?
>
>
> erst mal Sort:: http://search.cpan.org/~jnh/Sort-Fields-0.90/ ,
> nach search.cpan.org aber wohl irgendwas aus
> Sort::Fields, Sort::Key, Sort::Array,
> Sort::ArrayOfArrays
> Data::Table
> usw.
>
> Sprich: schaffe ich das ohne weitere Module schon ausreichend gut mit
> dem normalen sort(), oder waere eines der Module hier dringend
> angeraten.
>
>
>>>oder schafft das auch schon das normale sort?
>>
>> Mit perl geht das schon, wie gesagt -- jenachdem, was du GENAU vorhast.
>
>
> Ok, hier ein paar laengere Erlaeuterungen...
> Vielleicht sollte ich also noch konkreter fragen:
>
> Gegeben sind Rohdaten in der Datei 'Beispiel.csv'
> # ID;A;B;N;X # erste Zeile Kommentar
> 1;Aa;E;1.23;x
> 2;Aa;D;23.45;x
> 3;Ab;D;0;x
> 4;Ac;C;-;
> 5;Aaa;E;;x
> 6;Aa;Ee;1;x
> ....
>
> Diese Datei soll eingelesen werden.
> Der Anwender sagt:
> - mich interessiert alles, wo X ein x enthaelt.
> - sortiere das nach B (aufwaerts) und N (abwaerts)
> - Zwischenschritt: Es ist bekannt, dass B in Spalte 3 und N in Spalte 4
> liegt; B ist Text, N enthaelt Zahlen.
>
> Das Ergebnis soll in fuer ihn lesbarer Form dargestellt werden, in der
> Darstellung mit B, A, N z.B. als:
>
> B A N
> --------------
> D Aa 23.45
> D Ab 0
> E Aa 1.23
> E Aaa
> Ee Aa 1
>
> War das genau genug? Wenn du's ausprobieren moechtest, stelle ich dir
> gerne auch Beispieldaten zur Verfuegung mit ca. 1000 Datensaetzen, 20
> Spalten, mit wenigen Spalten, die tatsaechlich gefuellt sind, und vielen
> Spalten, die seltenere Zusatzinfos enthalten und meist in der Uebersicht
> nicht angezeigt werden.
>
> oder ein konkretes Beispiel: http://www.fa-technik.adfc.de/Komponenten/Umwerfer/
> Erklaerungen, was die Spalten bedeuten, finden sich in der zugehoerigen
> Legende
>

Hallo Martin,

wäre das nicht am einfachsten (auch hinsichtlich Wartbarkeit und Datenpflege)
mit einer kleinen Datenbank zu lösen?

Übrigens (OT): die SRAM 68 Kette funktioniert auch prima mit 6/7 Kassetten -
z.B. die guten alten Uniglide ;)

Christoph

--

perl -e "print scalar reverse q/ed.enilno@ergn.l.hc/"

Re: Tabellen sortieren

Peter J. Holzer schrieb:

> On 2006-10-06 15:28, Martin Trautmann wrote:
> > On 6 Oct 2006 08:14:04 -0700, Ingo Menger wrote:
> >> Man kann natürlich mehrere vorkonfigurierte Routinen haben und bei
> >> Bedarf die "richtige" übergeben.
> >
> > Das erscheint mir eben als wenig elegant. In dem Fall bevorzuge ich eine
> > einfache Holzhammermethode (immer nur ein Sortiermerkmal steht zur
> > Verfuegung - dafuer kann aber manuell verkettet sortiert werden ueber
> > eine Such-Historie: sortiert wurde nach A, naechste Sortierung
> > uebernimmt diese Daten und sortiert diese nach B und erreicht damit eine
> > Sortierung nach B-A)
>
> Das funktioniert aber nicht bei allen Sortier-Algorithmen. Bei quicksort
> z.B. wird die ursprüngliche Sortierung zerstört, wenn man nach einem
> anderen Kriterium sortiert.
>
> Perl 5.8 verwendet m.W. einen stabilen Sortier-Algorithmus (Merge-Sort).
> Ältere Versionen von Perl haben eine quicksort-Variante verwendet. Wenn
> Du also Sortierungen einfach so verknüpfen willst (was durchaus eine
> legitime Variante ist), solltest Du sicherstellen, dass Dein Script nur
> mit einer aktuellen Perl-Variante verwendet wird.

Zudem dürften n Sortierungen ca. n-mal so lange dauern wie eine
Sortierung mit einer Vergleichsfunktion, die alle Attribute auf einmal
prüft, da der Aufruf der Subroutine dasjenige ist, was richtig Zeit
kostet. Solange die Menge der Daten klein ist, fällt das natürlich
kaum ins Gewicht.

> >> Es ist natürlich aber folgendes denkbar: Man schreibt eine Funktion,
> >> die aus einem String wie "2 1r 3n" folgenden String erzeugt:
> [...]
> >> Der Vorteil ist, daß dann beim Sortieren eine Subroutine aufgerufen
> >> wird, die compiliert ist (durch das eval) und genauso schnell wie eine
> >> "richtige" Subroutine.
> >
> > Hm, ich werde versuchen, das mal zu verdauen. Neuland. Mal sehen, wie w=
eit ich
> > damit komme...
>
> Sowas zu Übungszwecken zu schreiben, ist sicher sehr lehrreich. Zur
> Lösung des Problems ist es aber wahrscheinlich zielführender, eines d=
er
> fertigen Module wie Sort::Maker zu verwenden, als das Rad neu zu
> erfinden.

Unbedingt. Wobei die oben angedachte Transformation im Prinzip trivial
ist.
Man hat die Nummer des Feldes, nach dem sortiert werden soll, dies um 1
vermindert ergibt den Array-Index. Zu generieren ist pro Item entweder
$a->[] $b->[]
oder
$b->[] $a->[]
je nachdem, ob es reverse sein soll oder nicht. kann cmp oder
<=3D> sein. Die so generierten Vergleiche verknüpft man mit "||" und
schreibt drumherum "sub { }"
Fertig ist der Lack.

Also

sub cmpitem($$$) { # field number, reverse?, numeric?
my $fn =3D shift;
my $rev =3D shift;
my $num =3D shift;
my $inx =3D $fn-1;
my $cmp =3D $num ? "<=3D>" : "cmp";
my ($a, $b);
($a, $b) =3D $rev ? ('$b', '$a') : ('$a', '$b');
sprintf "%s->[%d] %s %s->[%d]", $a, $inx, $cmp, $b, $inx;
}

my @ex =3D ([2, "", ""], [1, "reverse", ""], [3, "", "numeric"]);

sub cmpcomp {
my @spec =3D @_;
"sub { " . (join(" || ", map { cmpitem(@$_) } @spec)) . "}"
}

sort (eval cmpcomp(@ex)) @tabelle;

Re: Tabellen sortieren

Post removed (X-No-Archive: yes)