Bei der Schwartz'schen Transformation handelt es sich um ein recht elegantes Sortierverfahren für komplexere (bzw. gekapselte) Datenstrukturen.
Hat einen eigenen (englischen) Wikipedia-Eintrag:
https://en.wikipedia.org/wiki/Schwartzian_transformauf Deutsch bekommt man die Sache relativ gut anschaulich hier erklärt:
http://perl-seiten.privat.t-online.de/html/perl_schw.htmlIn Kürze erklärt besteht der "Witz" dieser Technik darin Daten vor ihrer Sortierung aufzubereiten, so dass innerhalb des eigentlichen Sort-Blocks keine zeit- bzw. rechenintensiven Funktionen stehen müssen. Denjenigen unter uns, die im Laufe ihres Studiums - oder Lebens - etwas mit Komplexitätstheorie gequält wurden, ist bekannt, dass ein optimales Sortierverfahren eine Laufzeitkomplexität von
O(n * log(n)) hat (wenn n Elemente sortiert werden).
Wenn ich nun in einem sort-Block eine Funktion aufrufen muss um aus $a und $b Daten zu bekommen die mich interessieren, dann läuft diese Funktion
im besten Fall 2 * n * log(n) mal durch. (im schlimmsten Fall 2 x n²)
Da wäre es doch schön, wenn die Funktion nur n-mal laufen würde. Das geht.
Man kann das dadurch erreichen, dass man sich vor dem sort mittels map aus den gegebenen Daten ein einfaches Array aufbaut bei dem man betreffende Funktion (zur Datenextraktion, Konversion, ...) pro Element nur
einmal aufruft und dann in einer einfachen Datenstruktur die Originaldaten und die konvertierten Daten - leicht zugänglich - bereitstellt.
Gibt es in FHEM konkrete Stellen wo das Sinn machen würde? Gibt es.
Schauen wir uns dieses Stück Code in fhem.pl an (dabei sind uns bareword filehandles etc. egal)
Uns interessiert vorwiegend das "stat":
my @files = sort grep {/^$file$/} readdir(DH);
@files = sort { (stat("$dir/$a"))[9] cmp (stat("$dir/$b"))[9] } @files
if(AttrVal("global", "archivesort", "alphanum") eq "timestamp");
closedir(DH);Das stat holt sich vom Filesystem den Zeitstempel der letzten Modifikation. (
https://perldoc.perl.org/functions/stat.html)
Wir können natürlich auf das OS vertrauen und hoffen, dass da einiges gecached wird, aber im Prinzip fragen wir
pro Vergleich die Statusinfo von
zwei Dateien an.
Nach der Schwartz'schen Transformation würde der Code wie folgt aussehen:
my @files = sort grep {/^$file$/} readdir(DH);
if (AttrVal('global', 'archivesort', 'alphanum') eq 'timestamp') {
@files = map { $_->[0] }
sort { $a->[1] <=> $b->[1] }
map { [$_, (stat("$dir/$_"))[9] ] } @files;
}
closedir(DH);Zunächst einmal haben wir einen Bug gefunden und entfernt - nämlich die Verwendung von cmp anstelle von <=>, stat liefert ja bei Index 9
last modify time in seconds since the epoch
und das ist ja nun wahrlich etwas was man numerisch und nicht lexikalisch sortieren sollte.
Hier interessiert uns aber mehr, dass der neue Code wesentlich effizienter ist, weil bei - sagen wir - 100 Dateien nun
stat eben nur 100 mal statt (im besten Fall) 400 mal aufgerufen wird.
"Vorwärts immer, rückwärts nimmer!"
