Wenn man Karten als Repräsentationen endlicher Funktionen betrachtet, kann eine Karte von zwei oder mehr Variablen entweder in Curry- oder in Nicht-Curry-Form gegeben werden; das heißt, die Typen Map (a,b) c und Map a (Map b c) sind isomorph oder etwas ähnliches.Haskell: `Map (a, b) c` gegen` Map a (Map b c) `?
Welche praktischen Überlegungen gibt es - Effizienz usw. - für die Wahl zwischen den beiden Darstellungen?
Die Ord Instanz von Tupeln verwendet Lexikographische Ordnung, so Map (a, b) c wird von a zuerst sowieso sortieren, so dass die Gesamt um die gleiche sein wird. praktische Überlegungen in Bezug auf:
Da Data.Map ist ein binärer Suchbaum Splitting bei einem Schlüssel zu einem Nachschlag vergleichbar ist, so eine Submap für ein deutlich teurer sein wird, nicht a in der uncurried Form gegeben bekommen als in dem Curry-Form.
Die Curry-Form kann insgesamt einen weniger ausgeglichenen Baum ergeben, aus dem offensichtlichen Grund, mehrere Bäume statt nur einer zu haben.
Die Curry-Form wird einen zusätzlichen Aufwand für die Speicherung der verschachtelten Karten haben.
Die verschachtelten Karten der Curry-Form, die "Teilanwendungen" darstellen, können geteilt werden, wenn einige a Werte das gleiche Ergebnis liefern.
In ähnlicher Weise gibt "partielle Anwendung" der Curry-Form Ihnen die vorhandene innere Karte, während die uncurried Form eine neue Karte erstellen muss.
So ist die uncurried Form ist
deutlich besser im Allgemeinen
, aber die Curry-Form besser sein können, wenn Sie erwarten, „partielle Anwendung“ oft zu tun und von Teilen von Map b c Werte profitieren würden.
Beachten Sie, dass einige Sorgfalt notwendig sein wird, um sicherzustellen, dass Sie tatsächlich profitieren von dieser potenziellen Freigabe; Sie müssen explizit alle freigegebenen inneren Maps definieren und den einzelnen Wert beim Erstellen der vollständigen Map wiederverwenden.
Bearbeiten: Tikhon Jelvis weist in den Kommentaren darauf hin, dass der Speicheraufwand der Tupelkonstruktoren - von denen ich nicht dachte, dass dies zu berücksichtigen ist - überhaupt nicht vernachlässigbar ist. Es gibt sicherlich einige Gemeinkosten für die Curry-Form, aber dieser Overhead ist proportional dazu, wie viele verschiedene a Werte es gibt. Der Overhead des Tupelkonstruktors in der unvermittelten Form ist andererseits proportional zur Gesamtzahl der Schlüssel.
Wenn also im Durchschnitt für jeden gegebenen Wert a drei oder mehr verschiedene Schlüssel verwendet werden, sparen Sie wahrscheinlich Speicher mit der Curry-Version. Die Bedenken bezüglich unsymmetrischer Bäume gelten natürlich weiterhin. Je mehr ich darüber nachdenke, desto mehr vermute ich, dass die Curry-Form eindeutig besser ist, außer vielleicht, wenn Ihre Schlüssel sehr spärlich und ungleich verteilt sind.
Beachten Sie, dass, weil arity von Definitionen nicht egal zu GHC, die gleiche Sorgfalt erforderlich, wenn Funktionen definieren, wenn Sie Unterausdrücke gemeinsam genutzt werden sollen; dies ist ein Grund, warum Sie manchmal Funktionen in einem Stil wie folgt definiert sehen:
foo x = go
where z = expensiveComputation x
go y = doStuff y z
+1, aber re: der erste Aufzählungspunkt, würde keine Submap erfordern Worst-Case-lineare Zeit in der uncurried Version gegenüber logarithmischen in der Curry-Version? Oder verhindert faule Bewertung das? –
@larsmans: Lazy Auswertung verhindert, dass es einfach zu bestimmen, was "Worst Case" bedeutet. :] Du bezahlst nur für die teure Rechnung, wenn du etwas tust, das es zwingt, was ohnehin oft etwas teuer ist. Das stimmt, ich glaube, Sie haben Recht, aber es würde wahrscheinlich absichtlich pathologische Daten und Zugangsmuster erfordern, um diesen schlimmsten Fall in der Praxis zu erkennen. –
Ich dachte daran, die "Map b c" herauszuholen, gefolgt von einer O (n) oder größeren Folge von Zugriffen, aber ich wusste nicht, dass in diesem Fall die Kosten der Kartenkonstruktion von den tatsächlichen Zugriffen dominiert werden. –
Tupeln sind faul in beiden Elementen, so dass die Tupel Version führt ein wenig mehr Faulheit. Ob das gut oder schlecht ist, hängt stark von Ihrer Verwendung ab. (Insbesondere können Vergleiche die Tupelelemente erzwingen, aber nur dann, wenn viele Duplikate a Werte vorhanden sind.)
Darüber hinaus denke ich, dass es davon abhängen wird, wie viele Duplikate du hast. Wenn a fast immer anders ist, wenn b ist, wirst du eine Menge kleiner Bäume haben, also könnte die Tupel-Version besser sein. Auf der anderen Seite, wenn das Gegenteil der Fall ist, kann die Nicht-Tupel-Version Sie ein wenig Zeit sparen (nicht ständig a neu kompilieren, sobald Sie den entsprechenden Teilbaum gefunden haben und Sie suchen nach b).
Ich erinnere mich an Versuche, und wie sie gemeinsame Präfixe einmal speichern. Die Nicht-Tupel-Version scheint ein bisschen so zu sein. Ein Trie kann effizienter sein als ein BST, wenn es viele gemeinsame Präfixe gibt, und weniger effizient, wenn dies nicht der Fall ist.
Aber das Endergebnis: benchmarken Sie es !! ;-)
+1 Ich denke wie du. Die uncurried-Form könnte auch schneller sein, wenn viele Suchen durchgeführt werden, die bereits für ein fehlendes a * und * fehlschlagen. Die Anzahl der eindeutigen curry-Schlüssel (a, b) ist viel größer als die Anzahl der eindeutigen a's. – Ingo
Es wird nicht wirklich faul sein, da es durch Schlüsselvergleiche gezwungen wird, sobald Sie es in den Baum einfügen, und im Allgemeinen sind die 'Map'-Kombinatoren (etwas unnötigerweise) streng in der Taste unabhängig. –
(Sie werden jedoch gezwungen sein, den zusätzlichen Scheck zu bezahlen, weil GHC nicht schlau genug sein wird, um zu wissen, dass die Seiten des Tupels bereits durch den ersten Vergleich erzwungen wurden, und nur das äußere '(,)' würde erzwungen werden Einfügen in eine leere 'Map') –
Abgesehen von den Effizienzaspekten gibt es auch eine pragmatische Seite zu dieser Frage: Was wollen Sie mit dieser Struktur machen?
Möchten Sie zum Beispiel eine leere Map für einen gegebenen Wert vom Typ a speichern können? Wenn dem so ist, dann könnte die uncurried Version praktischer sein!
Hier ist ein einfaches Beispiel: Nehmen wir an, wir wollen String -bewertete Eigenschaften von Personen speichern - sagen wir den Wert einiger Felder auf der Stackoverflow-Profilseite dieser Person.
type Person = String
type Property = String
uncurriedMap :: Map Person (Map Property String)
uncurriedMap = fromList [
("yatima2975", fromList [("location","Utrecht"),("age","37")]),
("PLL", fromList []) ]
curriedMap :: Map (Person,Property) String
curriedMap = fromList [
(("yatima2975","location"), "Utrecht"),
(("yatima2975","age"), "37") ]
Mit der curried Version gibt es keine gute Möglichkeit, die Tatsache zu erfassen, dass "PLL" Benutzer das System bekannt ist, aber in den Informationen nicht gefüllt hat. Ein Personen-/Eigenschaftspaar ("PLL",undefined) wird Runtime-Abstürze verursachen, da Map in den Schlüsseln streng ist.
Sie könnten die Art von curriedMap zu Map (Person,Property) (Maybe String) ändern und speichern Nothing s drin, und das sehr gut könnte die beste Lösung in diesen Fall sein; aber wo es eine unbekannte/variierende Anzahl von Eigenschaften (z. B. abhängig von der Art der Person) gibt, die auch in Schwierigkeiten geraten wird.
Also, ich denke, es hängt auch davon ab, ob Sie eine Abfrage Funktion wie diese benötigen:
data QueryResult = PersonUnknown | PropertyUnknownForPerson | Value String
query :: Person -> Property -> Map (Person, Property) String -> QueryResult
Das ist schwer zu schreiben (wenn nicht unmöglich) in der curried Version, aber leicht in der uncurried Version.
Ich denke, Map (a, b) c ist wahrscheinlich viel mehr Speicher (und möglicherweise Zeit) effizient. Wenn es einen Weg gibt (ich bin mir nicht sicher, habe Karten nicht viel benutzt), um einen Präfix-Schlüsselbereich zu falten, dann könnte man mit dieser Darstellung, wie ich meine, immer noch so etwas wie eine Curry-Anwendung ausführen. – DarkOtter