2016-04-16 20 views
1

Ich habe eine verschachtelte Karte wie folgt:Elemente verschachtelte Karte hinzufügen effizient

Map<int, Map<int, int>> 

Und ich möchte so effizient in der Lage sein, ein Element der verschachtelten Karte hinzuzufügen und ordentlich wie möglich.

Meine aktuelle Lösung ist so etwas wie diese:

let AddStuff (collection:Map<int, Map<int, int>>) firstID secondID value = 
    let newValue = collection.[firstID].Add(secondID, value) 
    let newCollection = collection.Add(firstID, newValue) 
    newCollection 

Dies scheint mir nicht der F# Weg, um Dinge zu tun, so frage mich, was ist der beste Weg zu einer verschachtelten Karte hinzufügen?

bearbeiten Einige erwarteten Eingabe/Ausgabe:

let aMap = map[(1, map[(1, 1)])] 
let firstID = 1 
let secondID = 2 
let value = 2 

let newMap = aMap firstID secondID value 

// newMap = map[(1, map[(1, 1); (2, 2)])] 

Edit 2

Es scheint, dass partialCollection am Ausgang keine Wirkung hatte, so habe ich es von der Funktion entfernt.

+0

Das Problem wäre leichter zu verstehen, wenn Sie auch einige Testfälle (Eingabe und erwartete Ausgabe) liefern. –

+0

@MarkSeemann Sorry, Bearbeitungsprobleme. Ich habe die 3. Zeile in der Funktion geändert, um partialCollection darzustellen – Hayden

+0

Ich sehe, Sie gerade Ihre Frage bearbeitet, wie Sie festgestellt haben, dass 'Map.Add' in F # ist im Wesentlichen" hinzufügen oder ersetzen ". Was du jetzt hast, sieht für mich so aus, als wäre es der richtige Weg, also hast du im Wesentlichen deine eigene Frage beantwortet, indem du sie redest, soweit ich das beurteilen kann. – rmunn

Antwort

1

um in der Art etwas mehr funktionsfähig zu sein, könnte man jene .Add Methode ruft mit Aufrufen an die Map.add Funktion (eine Funktion auf dieersetzenModul, kein Methodenaufruf auf die einzelnen Objekte Map). Sie können auch das Argument collection für Ihre AddStuff-Funktion auf das letzte Argument verschieben, damit es einfacher mit dem Operator |> verwendet werden kann. Dann würde es wie folgt aussehen:

let AddStuff firstID secondID value (collection:Map<int, Map<int, int>>) = 
    let newValue = collection.[firstID] |> Map.add secondID value 
    collection |> Map.add firstID newValue 

Und man konnte es gerne verwenden:

let newMap = aMap |> AddStuff firstID secondID value 

Bis zu Ihnen, zu entscheiden, welche Art Sie mögen besser, aber Ich mag die |> Stil besser selbst, wie es lässt Ich denke in Bezug auf "diese Daten werden durch diese Operationen piped".

Edit: Diese Funktion könnte etwas schöner mit einigen Leerzeichen aussehen:

let AddStuff firstID secondID value (collection:Map<int, Map<int, int>>) = 
    let newValue = 
     collection.[firstID] 
     |> Map.add secondID value 
    collection |> Map.add firstID newValue 
+0

Das ist eine noch bessere Verbesserung! Vielen Dank – Hayden

0

In Ordnung, so wie @rmunn sagte im Kommentarbereich ist Map.Add im Wesentlichen "hinzufügen oder ersetzen"

Also meine ursprüngliche Funktion, die war:

let AddStuff (collection:Map<int, Map<int, int>>) firstID secondID value = 
    let newValue = collection.[firstID].Add(secondID, value) 
    let partialCollection = collection.Remove(firstID) 
    let newCollection = partialCollectioncollection.Add(firstID, newValue) 
    newCollection 

Jetzt wird:

let AddStuff (collection:Map<int, Map<int, int>>) firstID secondID value = 
    let newCollection = collection.Add(firstID, collection.[firstID].Add(secondID, value)) 
    newCollection 
1

ist es ein Problem mit den Lösungen, die Sie bisher haben. Mit den Indexerwürfen nach einem Schlüssel suchen, der nicht in der Karte enthalten ist - Sie können nicht etwas hinzufügen, das nicht bereits auf der obersten Ebene der Karte ist. Also ein Anruf wie AddStuff aNewMap 7 11 3 wird brechen.

Hier ist eine nette Art und Weise, es zu tun - zunächst eine allgemeine Update-Funktion definieren:

/// Update a value for key if it exists, 
/// otherwise return a new map with that value 
let update key f maybeColl = 
    match maybeColl with 
    | Some coll -> 
     let maybeElem = Map.tryFind key coll 
     Map.add key (f maybeElem) coll 
    | None -> 
     Map.ofList [key, f None] 

dann Ihre Funktion von Updates komponieren:

/// Given a two-level map, adds a value to the nested map. 
let add2 firstKey secondKey value coll = 
    (Some coll) 
    |> update firstKey (
     update secondKey (fun _ -> value)) 

machen update leicht zusammensetzbare bedeutet, dass Sie leicht schreiben eine add3 oder eine Funktion, die zum Beispiel einen Wert in der verschachtelten Map abbilden würde.

+0

Danke für Ihre Antwort, aber meine vollständige Lösung überprüft bereits, ob der Schlüssel innerhalb der Funktion drin ist – Hayden

0

Sie haben nach Effizienz und Ordentlichkeit gefragt. Ein ziemlich sauberer Ansatz besteht darin, Linsen zu verwenden, um Eigenschaften eines unveränderlichen Typs zu aktualisieren.

module Lenses = 
    // A Lens is a type that allows "focusing" on a property of a type 
    // A Lens consists of a get and set function 

    // Inspired by: http://www.haskellforall.com/2012/01/haskell-for-mainstream-programmers_28.html 

    //       getter  setter 
    type Lens<'T, 'V> = Lens of ('T -> 'V)*('V -> 'T -> 'T) 

    let inline get (Lens (g, _)) v  = g v 
    let inline set (Lens (_, s)) n v = s n v 

    // >-> chains two Lenses, allows focusing on property of a property of a type 
    let (>->) (f : Lens<'T, 'V>) (s : Lens<'V, 'U>) : Lens<'T, 'U> = 
    Lens (get f >> get s, fun n v -> set f (set s n (get f v)) v) 

    // fstL is a Lens that focuses on the first element in a pair 
    let fstL<'T, 'U> : Lens<'T*'U, 'T> = 
    Lens (fst, fun n v -> (n, snd v)) 
    // sndL is a Lens that focuses on the second element in a pair 
    let sndL<'T, 'U> : Lens<'T*'U, 'U> = 
    Lens (snd, fun n v -> (fst v, n)) 
    // mapzL is a Lens that focuses on an element in a map, z is the zero value if not present 
    let mapzL k z  : Lens<Map<'K, 'V>, 'V> = 
    let get v = 
     match Map.tryFind k v with 
     | Some e -> e 
     | _ -> z 
    let set = Map.add k 
    Lens (get, set) 
    // mapzL is a Lens that focuses on an element in a map 
    let inline mapL k = mapzL k LanguagePrimitives.GenericZero 

open Lenses 

[<EntryPoint>] 
let main argv = 
    // Creates an empty map of a map 
    let empty  : Map<string, Map<int, float>> = Map.empty 

    // Uses Lenses to update the map 
    // Has to pass Map.empty to mapzL as Map doesn't have a Zero member 
    let modified1 = empty  |> set (mapzL "A" Map.empty >-> mapL 2) 3. 
    let modified2 = modified1 |> set (mapzL "B" Map.empty >-> mapL 3) 4. 
    let modified3 = modified2 |> set (mapzL "B" Map.empty >-> mapL 4) 5. 

    printfn "%A" empty 
    printfn "%A" modified1 
    printfn "%A" modified2 
    printfn "%A" modified3 

    0 
Verwandte Themen