Sortieren (was: [vienna.pm] Anfaengerfrage)

Peter J . Holzer hjp at wsr.ac.at
Wed Sep 27 10:58:17 CDT 2000


On 2000-09-27 15:38:01 +0200, Rob Ermers wrote:
> * * * vienna-pm-list * * *
> 
> 
> Hallo Freunde,
> 
> Ich will Roland Bauer gerne nochmals meinen herzlichen Dank aussprechen für
> seinen "Entwurf", der genau so funktioniert wie ich es mir gehofft hatte.
> Einfach Klasse!
> 
> Ich frage mich jetzt noch wie ich das mit dem Sortieren im Griff kriegen
> kann. Weil der Text in kyrillisch ist, ist es in meinen Daten vom
> ASCII-Standpunkt aus gesehen ein Chaos: a (= kyrr. f) folgt f (=kyrr. a), c
> (= kyrr. s) folgt p (=kyrr. z), usw.
> Kann ich etwas mit den vielen Optionen bei "sort"? Oder muss ich irgendeine
> LC-Option ändern, d.h. teilweise meine eigene Locale basteln? Oder kann man
> am besten Perl 'was schönes ins Ohr flüstern?

Theoretisch:
    use locale;
irgendwo am Anfang des Programms und alles sollte automatisch gehen,
wenn Dein System eine passende Locale hat und Perl Locales unterstützt.

Praktisch hat das bei mir noch nie geklappt (ist aber einige Zeit her,
daß es zuletzt probiert habe), sicherer bist Du wahrscheinlich
unterwegs, wenn Du das von Hand machst:

    @a = sort
	    {
		my $aa = $a;
		$aa =~ tr/äöü/aou/;
		$aa =~ s/ß/ss/;

		my $bb = $b;
		$bb =~ tr/äöü/aou/;
		$bb =~ s/ß/ss/;

		return $aa cmp $bb
	    }
	    @a;

würde z.B. das Array @a so sortieren, als ob alle Umlaute durch die
entsprechenden einfachen Umlaute und ß durch ss ersetzt wären. Der Trick
besteht darin, aus jedem String einen anderen String zu erzeugen, und
diesen zweiten String für den größer/gleich/kleiner-Vergleich
heranzuziehen.

(Hah, und jetzt komme ich doch dazu, die Schwartzian Transform aus dem
Ärmel zu schütteln :-)

Auf den ersten Blick fällt auf, daß hier die gleichen
Transformationen auf beide Strings angewendet werden. Wenn man
weiterhin weiß, daß Sortieralgorithmen einen mehr als linearen Aufwand
haben (i.A. O(n log(n))), könnte man auf die Idee kommen, daß das ein
bißchen ineffizient ist, diese Transformationen für jeden Vergleich
durchzuführen, und daß es sinnvoller wäre, diese Transformation einmal
für jedes Element durchzuführen, bevor man sortiert.

Auf die Idee ist Randall Schwartz natürlich auch schon gekommen, und er
hat etwas erfunden, was man die Schwartzian transform nennt:


    @a = map { $_->[0] } 
	     sort { $a->[1] cmp $b->[1] } 
		  map { [$_,
			 do { my $x = $_;
			      $x =~ tr/äöü/aou/;
			      $x =~ s/ß/ss/;
			      $x;
			    }
			]
		      } 
		      @a;     


Da das ganze ein relativ komplizierter Ausdruck ist und trotz meiner
IMHO etwas besseren Einrückung als der üblichen etwas unübersichtlich,
spalte ich es in mehrere Schritte auf:

    @a1 = map { [$_,
		 do { my $x = $_;
		      $x =~ tr/äöü/aou/;
		      $x =~ s/ß/ss/;
		      $x;
		    }
		]
	      } 
	      @a;     

    @a2 = sort { $a->[1] cmp $b->[1] } @a1;

    @a = map { $_->[0] } @a2;

Im ersten Schritt wird ein neues Array @a1 aus @a erzeugt, wobei jedes
Element durch das Ergebnis des Blocks in geschwungenen Klammern ersetzt
wird. Das ist bei der Schwartzian Transform immer eine Referenz auf eine
Liste aus zwei Elementen (Erzeugt durch die eckigen klammern). Das erste
Element ist das unveränderte Element aus dem zu sortierenden Array (also
$_), das zweite ist das transformierte Element, nach dem dann
schlußendlich sortiert werden soll. Das kann ein beliebiger Ausdruck
sein, in dem $_ vorkommt, hier ist ein ein ganzer Block 
     do { my $x = $_;
	  $x =~ tr/äöü/aou/;
	  $x =~ s/ß/ss/;
	  $x;
	}
der die notwendigen Transformationen durchführt (man könnte statt dessen
auch eine sub definieren und hier aufrufen). 

Wenn @a den Inhalt:
    ( 'ärzte', 'ast', 'arbeit' )
hat, dann hat danach @a1 den Inhalt
    (
	['ärzte', 'arzte'],
	['ast', 'ast'],
	['arbeit', 'arbeit']
    )

Im zweiten Schritt wird dann sortiert, wobei aus jeder Teilliste immer
das zweite Element ($a->[1] bzw. $b->[1]) alphabetisch verglichen wird.

Ergebis:
    (
	['arbeit', 'arbeit'],
	['ärzte', 'arzte'],
	['ast', 'ast']
    )

(da "arzte" nach "arbeit" aber vor "ast" im Alphabet kommt).

Im letzten Schritt wird dann von jeder Teilliste wieder wieder das
erste Element ($_->[0]) herausgekletzelt, und die entstehende Liste @a
zugewiesen, so daß schlußendlich in @a steht:

    (
	'arbeit',
	'ärzte',
	'ast'
    )


Übungsaufgaben (für die perl-kurs-Liste :-):

1) Erweiterung auf Großbuchstaben.

2) Implementation der neuen (seit zehn Jahren oder so) österreichischen 
   Telefonbuchsortierreihenfolge ('ä' ist dabei ein eigener Buchstabe
   zwischen 'a' und 'b'). 

3) Implementation der alten österreichischen
   Telefonbuchsortierreihenfolge ('ä' wird dabei gleich sortiert wie
   'a', es sei denn, zwei Wörter wären dann völlig gleich ("Äpfel" und
   "Apfel"), dann wird das Wort mit dem Umlaut nach dem Wort ohne Umlaut
   sortiert).


Nachlese:

    http://www.5sigma.com/perl/schwtr.html

    http://www.hpl.hp.com/personal/Larry_Rosler/sort/

	hp

PS: Bitte aussagekräftigere Subjects: "Einsteigerfrage" sagt nicht
allzuviel aus.



-- 
   _  | Peter J. Holzer      | Any setuid root program that does an
|_|_) | Sysadmin WSR / LUGA  | exec() somewhere is just a less
| |   | hjp at wsr.ac.at        | user friendly version of su.
__/   | http://www.hjp.at/   |    -- Olaf Kirch on bugtraq 2000-08-07
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 371 bytes
Desc: not available
Url : http://mail.pm.org/archives/vienna-pm/attachments/20000927/991e6feb/attachment.bin


More information about the Vienna-pm mailing list