Data.Map verwenden oder nicht verwenden

Question

Ich arbeite derzeit an einer Haskell-API. Letztere bietet einige Funktionen, die derzeit eine Liste der Listen als Eingabe, d.h. [(String,[(String, Double)])] .

Zur Veranschaulichung sehen Sie hier ein Beispiel für die Liste der Listen oben erwähnt:

[
    ("A",   [
                ("I1", 1),
                ("I2", 2),
            ]
    ),
    ("B",   [
                ("I1", 3),
            ]
    )
]

Ich habe einige privat Hilfsfunktionen. Eine Hilfsfunktion sucht nach bestimmten Einträgen in dieser Liste ( Data.List.find = O(n) ); eine weitere Funktion führt Schnittmengen aus; und eine weitere Funktion wandelt die oben dargestellte Liste in die folgende um:

[
    ("I1",  [
                ("A", 1),
                ("B", 3),
            ]
    ),
    ("I2",  [
                ("A", 2),
            ]
    )
]

Die Funktion, die die Transformation durchführt, verwendet Data.Map da es einige Funktionen bietet, die diesen Prozess sehr vereinfachen, wie Data.Map.unionWith y Data.Map.insertWith . Nun, da die Transformationsfunktion die Data.Map.fromList y Data.Map.toList dachte ich, es wäre schön, eine Karte der Karten anstelle einer Liste der Listen von Anfang an. Also änderte ich meine Beispieleingabe, um sie an die Karte der Karten Anforderung.

Zur Veranschaulichung hier noch einmal die Liste von oben als Karte der Karten :

Map.fromList [
    ("A",   Map.fromList [
                ("I1", 1),
                ("I2", 2),
            ]
    ),
    ("B",   Map.fromList [
                ("I1", 3),
            ]
    )
]

Dank dieses Schrittes hat mein Code ein paar Zeilen verloren, und dank der Data.Map.lookup Die Suche nach dem Gewünschten dauert jetzt nur noch O(log n) Zeit.

Trotzdem frage ich mich gerade, ob das wirklich eine gute Lösung ist? Ist eine Karte der Karten der richtige Weg? Oder sollte die Transformationsfunktion mit Data.Map.fromList y Data.Map.toList und lassen Sie den Rest mit Liste der Listen ? Oder besser noch, gibt es eine Datenstruktur, die für diese Art von Arbeit besser geeignet ist?

Ich bin sehr gespannt auf Ihre Antworten.

Answer 1

Die Initialisierung der Map-of-Maps dauert nur noch O(n) .

Betrachten Sie zunächst die Liste der Listen.

Nehmen wir an, die äußere Liste ist [ a ₁ , a ₂ , ..., a _p ], und jedes innere Element ist ein _j \= ( l _j , [ b ₀ , b ₁ , ..., b _{q j} ]). Dann dauert die Konstruktion der Liste der Listen O(n = ∑) _j=1 p q _j ).

Die Initialisierung einer inneren Karte erfordert m _j . = O(q _j ). Die Initialisierung der Map-of-Maps dauert O(∑ _j=1 p m _j ) = O(n).

Answer 2

Das riecht nach Graphen und Kanten. Ein etwas anderer Ansatz, der funktionieren kann oder auch nicht, besteht darin, das Problem so zu überarbeiten, dass anstelle von [(String,[(String,Double)])] operieren Sie einfach mit 2 Tupeln von Zeichenketten. Dann haben Sie [((String, String), Double)] und die resultierende Karte ist vom Typ Data.Map.Map (String, String) Double .

Alternativ, wenn der Platz für String-Schlüssel begrenzt ist und daher effizient in Maschinen-Ints abgebildet werden kann, sollten Sie eine IntMap verwenden. Gleiche Semantik wie eine Karte, außer dass die Schlüssel Maschine ints (Int32 oder Int64) sein MUSS. Dies wird eine viel bessere Leistung haben.

Answer 3

Natürlich hängt dies von Ihren tatsächlichen Daten ab, aber vielleicht könnten Sie stattdessen eine Multimap verwenden? Es gibt verschiedene Implementierungen (z.B. http://hackage.haskell.org/packages/archive/Holumbus-Distribution/0.0.1.1/doc/html/Holumbus-Data-MultiMap.html ), aber ich habe sie nicht ausprobiert.