elegante Art, Gegenstände zu zählen

Ich weiß nicht, dass das das eleganteste ist, aber es scheint vernünftig:

Gemeinsame Lisp-Funktionen auf höherer Ebene kombinieren:

Es skaliert jedoch nicht zu großen Listen. Wenn Sie O (n) Performance benötigen, verwenden Sie stattdessen eine auf Hashtabellen basierende Lösung, z. B. die weniger elegante:

Verwenden von Common Lisp-Erweiterungen:

Sie können einfach finally return result sagen, wenn es Ihnen nicht wichtig ist, das Endergebnis zu sortieren.

Verwenden Sie höherwertige Funktionen sort und reduce .

Erstes Sortieren (mit string & lt; ), dann Reduzieren (aufeinanderfolgende string = Werte in Cons-Zellen):

Jedes Mal, wenn Sie eine Liste durchqueren und danach einen Wert zurückgeben wollen, sei es eine neue Liste oder ein aggregiertes Ergebnis, denken Sie an ein fold , in Python und Lisps auch" reduce "genannt. Falten ist eine großartige Abstraktion, da es erlaubt, generischen Code zu schreiben, der für viele Anwendungsfälle anwendbar ist, nur indem man einige Elemente optimiert. Was ist ähnlich zwischen der Suche nach einer Summe aus mehreren Zahlen, der Suche nach einem Produkt oder der Suche nach einer minimalen Ganzzahl? Sie sind alle Falten, weil Sie die Liste durchlaufen und dann einige Ergebnisse basierend auf ihrem Inhalt zurückgeben. In Emacs Lisp würden sie so aussehen:

Aber Falten sind noch allgemeiner. Was ist ähnlich zwischen dem Finden einer Summe, dem Zählen einer Anzahl gerader Zahlen in einer Liste, dem Entfernen jeder ungeraden Zahl und dem Erstellen einer Liste mit jeder um 5 erhöhten Zahl? Jede solche Funktion kann implementiert werden, indem ein Basiswert genommen wird, der sukzessive transformiert wird, bis das Ergebnis erhalten wird. Du nimmst diesen Grundwert, metaphorischer Klecks Ton, nennst es "Akkumulator", nimmst dann ein Element aus einer Liste und machst auf diesem Element etwas zu diesem Klecks Ton, mach daraus einen Entwurf einer prächtigen Skulptur. Dann nimmst du das nächste Element aus einer Liste und tust deiner Skulptur etwas Neues. Das wiederholst du, bis die Liste leer ist und du ein Meisterwerk hast. Es ist, als wäre jedes Element einer Liste eine einzelne Anweisung in einem großen Rezept. Denken Sie daran, dass Sie völlig frei sind, etwas mit dem Ton zu tun, Sie müssen die Listenelemente im Ergebnis nicht direkt verwenden - technisch bedeutet dies, dass der Akkumulator (und somit das Ergebnis) davon sein kann verschiedene -Typen .

  

Hinweis zum Reduzieren vom Ende: Listen in Lisps sind keine intelligenten Arrays wie in Python oder Java, sie sind verkettete Listen, daher ist das Zugreifen auf oder Ändern eines Elements irgendwo in einer Liste eine O (n) Operation, während "consing" zu Der Anfang einer Liste ist O (1). Mit anderen Worten, das Anhängen eines Elements an das Ende einer Liste ist teuer, daher fügt Lispers normalerweise Elemente am Anfang einer Liste hinzu und kehrt dann die Liste schließlich um, die als push / nreverse idiom . Wenn wir das gewöhnliche Reduzieren in den letzten 2 Funktionen machen würden, würden wir 1 zu dem Akkumulator verdrücken und (1) erhalten, dann cons 2 zu Akkumulator und erhalten (2 1), bis wir das richtige Ergebnis erhalten, aber umgekehrt. Wir könnten später reverse function verwenden, aber glücklicherweise unterstützt Emacs ' reduce :from-end keyword argument, also gibt es 5, dann 4, dann 3 und so weiter.

Es ist jetzt klar, dass Ihre Operation eine Falte ist, durchqueren Sie den ursprünglichen Alist und zählen Sie das Vorkommen jeder Taste. Bevor wir unsere Falte schreiben, sprechen wir zuerst über Alisten. Alist in Lisp ist die Hash-Tabelle eines armen Mannes. Sie basteln normalerweise nicht mit den Hash-Tabellen-Implementierungsdetails einer Programmiersprache, oder? Sie arbeiten mit einer API. In Python sieht diese API aus wie die eckige Klammer-Syntax ( d['a'] = 1 ) und die dict-Methode ( d.keys() ). Für APIs enthält API die Funktion assoc , die ein Element zurückgibt, das einen Schlüssel bereitstellt.

Warum rede ich über Implementierungsdetails? Weil Sie über assoc arbeiten und es Ihnen egal ist, wie genau dieser Alist aussieht, abstrahieren Sie das weg. Ein weiterer Teil der API ist, dass wenn Sie ein neues Element hinzufügen oder ein existierendes ändern möchten, Sie einfach ein gepunktetes Paar auf das Alist setzen. So soll man mit Alists arbeiten, unabhängig von ihrer internen Struktur. Warum funktioniert das? Wenn ich zum Beispiel den Wert für den Schlüssel a auf 10 ändern möchte, würde ich einfach (cons '(a . 10) my-alist) ausführen, und my-alist würde am Ende '((a . 10) (a . 1) (b . 2)) sein. Aber es ist kein Problem, weil assoc nur das erste gepunktetes Paar zurückgibt und den Rest ignoriert, so dass Sie Alist wie jede andere Schlüssel / Wert-Datenstruktur behandeln können. In diesem Sinne schreiben wir unsere erste ernsthafte Falte.

Was passiert hier? Wir nehmen Ihre Daten und eine leere Liste, die bald unser gewünschtes Ergebnis wird. Bei jedem Schritt nehmen wir ein Paar von Daten und fragen: enthält unser Ergebnis Informationen über dieses Paar? Wenn nicht, dann fügen wir es zum Ergebnis hinzu und setzen 1 - wir haben diesen Schlüssel das erste Mal getroffen. Wenn wir jedoch Informationen über dieses Paar in unserem Ergebnis finden, müssen wir es erneut zu unserem Ergebnis hinzufügen, diesmal jedoch mit einer um 1 erhöhten Zahl. Wiederholen Sie diesen Vorgang für jedes Element in Ihren Daten und Sie erhalten:

Denken Sie daran, dass assoc sich nur um das erste Vorkommen eines Schlüssels kümmert? Dieser Alist würde sich genauso verhalten, als wäre er nur (("Alpha" . 4) ("Gamma" . 3) ("Rho" . 1) ("Beta" . 5)) , also sind wir hier gut. Könnten wir aber unsere Falte ändern, um stattdessen das kürzere Ergebnis zu erhalten? Warte mal, was ist nötig, um unsere Falte zu kompliziert zu machen, wenn wir das Ergebnis danach noch optimieren könnten? Nach allem, was ist Computerprogrammierung, wenn nicht Reihe von Datentransformationen?Es gibt keinen Grund, warum Sie nicht einfach alle "veralteten" Paare aus Ihrem Alist entfernen könnten, verwenden Sie einfach cl-remove-duplicates mit korrekten Argumenten , und du bist fertig.

Wir sind also stolz auf uns selbst, wir haben eine Falte geschrieben, eine Säule funktionaler Programmierung, doch sorgfältige Untersuchung deckt eine Ineffizienz auf: Wir durchqueren den Akkumulator mit assoc , um ein Paar zu finden und dessen Wert zu erhöhen. assoc benötigt O (n), reduce selbst benötigt O (n), daher ist unser Algorithmus O (n²) (lesen Sie dazu Reihenfolge des Wachstums , wenn Sie nicht Big-O-Notation verstehen). Es ist klar, dass wir besser mit einer geeigneten optimierten Hash-Tabelle arbeiten sollten und diese in eine Alistabelle konvertieren sollten, wenn wir sie brauchen. Schreibe unsere Falte um:

(gethash k d 0) entspricht Pythons d.get('k', 0) , wobei das letzte Argument der Standardwert ist. cl-incf (Common Lisp äquivalent incf ) ist ein intelligentes Makro, das sein Argument vor Ort inkrementiert (lesen Sie dazu setf um intelligente Zuweisungen zu verstehen). make-hash-table erfordert eine benutzerdefinierte Testfunktion, da Zeichenfolgen nicht mit der Standardfunktion eql verglichen werden können. Um einen Alist zu erhalten, konvertiere einfach die Ergebnis-Hash-Tabelle unserer Fold mit ht->alist function, die wir entweder aus Wilfreds ht.el Bibliothek, oder schreiben Sie uns:

Hier ist, was ich denke, ist eine elegante funktionale Lösung mit Emacs Alist-Funktionen, die eine wiederverwendbare frequencies -Funktion ähnlich wie Eli Antwort: