Schwartz'sche Transformation

Begonnen von RichardCZ, 28 Juni 2020, 11:46:44

Vorheriges Thema - Nächstes Thema

RichardCZ

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!"
Witty House Infrastructure Processor (WHIP) is a modern and
comprehensive full-stack smart home framework for the 21st century.

rudolfkoenig

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.

RichardCZ

Was mein Codemessie-Vorredner eigentlich sagen wollte war:

1) Da wurde objektiv ein Bug gefunden und wir hatten bislang nur Glück, dass er nicht aktiv zugeschlagen hat. Danke für's Finden und Melden. Vielleicht könnte man mal darüber nachdenken cmp und <=> Vorkommen allgemein zu begutachten. Ist ja nicht das Erste Mal, dass es da ein Problem gab.

2) "und kostet bei einem Verzeichnis mit 200+ Dateien < 0.01s." ist nur ein rhetorisches Beispiel. Kaum zu glauben, dass man immer nur auf < 0.01s Laufzeit kommt. Insbesondere sowohl auf der neuen PCIe4 SSD und auf der RasPi microSD oder USB Stick oder NFS Share gleichermaßen.

3) Danke für die Info zu dieser Technik und die Mühe das an einem konkreten FHEM Code-Beispiel zu zeigen.




Nicht der Rede wert.
Witty House Infrastructure Processor (WHIP) is a modern and
comprehensive full-stack smart home framework for the 21st century.

RichardCZ

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.
Witty House Infrastructure Processor (WHIP) is a modern and
comprehensive full-stack smart home framework for the 21st century.