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_transform
auf Deutsch bekommt man die Sache relativ gut anschaulich hier erklärt: http://perl-seiten.privat.t-online.de/html/perl_schw.html
In 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
Zitatlast 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!"
Um den vom Erich-Fanboy gemeldeten Bug in Kontext zu setzen: das ist ein Problem fuer FHEM-Logs, die vor Oktober 2001 oder nach November 2286 angelegt wurden, wenn man zusaetzlich das Attribut archivesort auf timestamp gesetzt hat. Habs gefixt.
Wg. Optimieren: die besagte Stelle wird bei der Voreinstellung einmal im Monat fuer das FHEM-Log, und einmal jaehrlich fuer die FileLogs aufgerufen, und kostet bei einem Verzeichnis mit 200+ Dateien < 0.01s. Ich optimiere sie gerne, wenn jemand deswegen Probleme meldet.
Da refactoring ein multi-pass Prozess ist (wie schon erwähnt), sind natürlich meine Codebeispiele
nicht das letzte Wort.
Via PM erreichte mich ein Vorschlag von @noansi mit einer kleinen Optimierung (kein doppeltes sort in bestimmten Fällen).
Und da ich eleganten Code nicht meide wie der Teufel das Weihwasser, habe ich den Vorschlag dankbar aufgegriffen:
https://gl.petatech.eu/root/HomeBot/-/commit/2d2318a360f4af95a4e12ddea8d010aac7c2117a
Danke Ansgar.