3

ネストされたディクショナリMap<'a,Map<'b,'T>>があるため、 の組み合わせのa*bエントリは一意です。

効率的に事前計算するには、キーを反転する必要があります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
4

4 に答える 4

7

解決しようとしている問題は、有向グラフの転置と呼ばれ、次のように二重折り畳みを使用して計算できます。

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 Journal の記事「グラフ アルゴリズム: トポロジカル ソートとすべてのペアの最短パス」を参照してください。

于 2012-03-23T13:30:11.763 に答える
5

@pad のソリューションは、|/>andのような非標準の演算子を使用するよりも、間違いなく慣用的な F# だと思います|*>。の代わりにシーケンス式を使用するSeq.collectバージョンをお勧めします。これは次のようになります (2 番目の部分は @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-22T13:15:44.097 に答える
2

@pad の解決策は、私が思いついたものと非常によく似ています。この種の問題では、そこにたどり着くまで、自分の鼻に従って、機能する唯一のことを行っていることを示していると思います。

あるいは、折り畳みに固執したい場合は、次のようにすることができます。

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-22T13:14:13.617 に答える
2

あなたの意図がよくわかりません。しかし、関数の署名から、次のようなことができます。

let reverse (map: Map<'a,Map<'b,'T>>) =
    map |> Seq.collect (fun (KeyValue(a, m)) -> 
                                m |> Seq.map (fun (KeyValue(b, t)) -> b, (a, t)))
        |> Seq.groupBy fst
        |> Seq.map (fun (b, ats) -> b, ats |> Seq.map snd |> Map.ofSeq)
        |> Map.ofSeq
于 2012-03-22T12:36:46.810 に答える