在f＃Map <'a，Map <'b,'T>>中反轉嵌套字典） - > Map <'b，Map <'a,'T>>

我有一個嵌套字典Map<'a,Map<'b,'T>>，所以對於a*b的組合，條目是唯一的。在f＃Map <'a，Map <'b,'T>>中反轉嵌套字典） - > Map <'b，Map <'a,'T>>

爲了有效地預先計算，我需要反轉在Map<'b,Map<'a,'T>>

我有一些更高階的方法來完成這項工作的關鍵（|/>將應用運行在一個嵌套序列|//>相同，但2水平深，|*>將枚舉嵌套序列的笛卡爾積），但我想知道是否有更好的方法來做到這一點，以防萬一有美麗的代碼分享這一個。

let reversenmap (x:Map<'a,Map<'b,'T>>) :Map<'b,Map<'a,'T>> = 
     let ret = x |> Map.toSeq |/> Map.toSeq |*> squash12 
     let ret2 = ret |> Seq.groupByn2 (fun (a,b,t) -> b) 
             (fun (a,b,t) -> a) |//> Seq.head 
                 |//> (fun (a,b,c) -> c) 
     ret2 |> Seq.toMapn2

來源

2012-03-22 nicolas

我認爲@pad的解決方案肯定比使用非標準的運營商如|/>和|*>更爲習慣使用F＃。我可能會更喜歡使用序列的表達，而不是Seq.collect一個版本，它看起來像這樣（第二部分是相同的，從@pad版本）：

let reverse (map: Map<'a,Map<'b,'T>>) = 
    [ for (KeyValue(a, m)) in map do 
     for (KeyValue(b, v)) in m do yield b, (a, v) ] 
    |> Seq.groupBy fst 
    |> Seq.map (fun (b, ats) -> b, ats |> Seq.map snd |> Map.ofSeq) 
    |> Map.ofSeq

來源

2012-03-22 13:15:44

序列表達式使枚舉非常自然。有非標準的運營商確實是一個劣質的解決方案。 – nicolas 2012-03-22 13:35:44

序列表達式不應該使用'seq {...}'而不是'[...]'？這提醒我，'seq {1..5}'和'{1..5}'之間是否有實際區別？ – 2012-03-22 16:41:17

@JoelMueller你的意思是'[1..5]'而不是'{1..5}'？如果是這樣，差異在於所得到的類型和評估方法。 'seq {...}'返回一個'seq <'a>'並且被延遲評估，就像'IEnumerable '（其中它是一個別名）。 '[...]'返回一個'列表'並立即評估。你可以返回一個無限長的'seq <'a>'，但是你不能用''list''來完成。 – 2012-03-23 02:57:40

我不知道我理解你的意圖。但是從你的函數的簽名，我們可以做這樣的事情：

來源

2012-03-22 12:36:46 pad

它很有意義。謝謝 – nicolas 2012-03-22 13:37:01

@墊的解決方案非常相似，我想出了 - 我猜它只是表明這些各種各樣的問題，你跟着你的鼻子做唯一可以工作的東西，直到你到達那裏。

另外，如果你想堅持的褶皺，你可以這樣做：

let invertNesting (map : Map<'a, Map<'b, 'c>>) = 
    let foldHelper (oldState : Map<'b, Map<'a, 'c>>) (k1 : 'a) (innerMap : Map<'b, 'c> = 
     innerMap |> Map.fold (fun tempState k2 v -> 
            let innerMap' = match (tempState |> Map.tryFind k2) with 
                | Some(m) -> m 
                | None -> Map.empty 
            let innerMap'' = innerMap' |> Map.add k1 v 
            tempState |> Map.add k2 innerMap'') oldState 
    map |> Map.fold foldHelper Map.empty

雖然@Tomas Petricek的解決方案是更具可讀性對我來說，這似乎是約25％的速度。

來源

2012-03-22 13:14:13

很有意思。我記得不得不寫一些類似的東西，但是天真地寫了2遍。 – nicolas 2012-03-23 08:56:44

你如何計時你的代碼btw？只是來自Diagnostics命名空間的常規計時器？ – nicolas 2012-03-23 08:57:38

事後看來，最後一條評論確實沒有提供足夠的細節。是@nicolas，我使用System.Diagnostics命名空間中的Stopwatch類進行計時，多次運行每個測試並平均其運行時間。這是內部和外部字典大小相等的地方。隨着字典大小的增加，加速比似乎也會降低 - 這種情況的啓動速度要快兩倍，但對於我測試的最大尺寸而言，速度會降低大約25％。 – 2012-03-26 12:31:12

你正在試圖解決的問題被稱爲有向圖的和轉置可以使用雙眼皮如下計算：

let invert xyzs = 
    Map.fold (fun m x yzs -> 
    Map.fold (fun m y z -> 
     let m' = defaultArg (Map.tryFind y m) Map.empty 
     Map.add y (Map.add x z m') m) m yzs) Map.empty xyzs

見F＃的.NET期刊文章Graph algorithms: topological sort and all-pairs shortest paths獲得更多信息。

來源

2012-03-23 13:30:11

看起來像釘了它。讓我通過緩慢的神經元來緩解這種情緒。 – nicolas 2012-03-24 08:46:33

相當不錯...感謝指點圖連接（原文如此）我覺得那些野獸很好。 – nicolas 2012-03-24 08:53:23

在f＃Map <'a，Map <'b,'T>>中反轉嵌套字典） - > Map <'b，Map <'a,'T>>

回答

相關問題