Ich muss eine Liste von Listen projektieren, die alle Kombinationen mit jedem Element aus jeder Liste zurückgibt. Zum Beispiel:
%Vor%Ich habe eine Funktion:
%Vor%und ein Testfall:
%Vor% Die Funktion ist jetzt ziemlich langsam, mit N = 10 dauert es mehr als 10 Sekunden. Außerdem denke ich, dass die Lösung unnatürlich ist, weil ich dieselbe Liste auf zwei verschiedene Arten zusammenbrechen muss. Irgendwelche Vorschläge, wie ich die Leistung und Lesbarkeit der Funktion verbessern kann?
Versuchen Sie zuallererst, die Listenverkettung (@) zu vermeiden, wann immer es möglich ist, da es O (N) statt O (1) vorangestellt ist.
Ich würde mit einem (relativ) einfach zu verfolgenden Plan anfangen, wie man das kartesische äußere Produkt von Listen berechnet.
Erste Version:
%Vor%Dies ist die direkte Übersetzung der obigen Sätze in den Code.
Beschleunige dies jetzt: Benutze Listenverkettungen und Karten statt Listenkompressen:
%Vor%Dies kann noch schneller gemacht werden, indem die Listen auf Anfrage über eine Sequenz berechnet werden:
%Vor%Diese letzte Form verwende ich selbst, da ich meistens nur die Ergebnisse durchlaufen muss, anstatt sie alle auf einmal zu haben.
Einige Benchmarks auf meinem Rechner: Testcode:
%Vor%Ergebnisse in FSI:
%Vor%Sie Implementierung ist langsam wegen der @ (d. h. List concat) -Operation, die eine langsame Operation ist, und es wird mehrmals in rekursiver Weise ausgeführt. Der Grund dafür, dass @ langsam ist, besteht darin, dass List in der funktionalen Programmierung eine Verknüpfungsliste ist. Um eine Liste zu erstellen, müssen Sie zuerst bis zum Ende der Liste gehen (nacheinander Elemente durchlaufen) und dann eine weitere Liste anhängen.
Sehen Sie sich die vorgeschlagenen Referenzen in Kommentaren an. Ich hoffe, die werden dir helfen.
Tags und Links f# performance list