Инвертировать вложенные словари в f # Map <'a, Map <' b, 'T >>) -> Map <' b, Map <'a,' T >> - PullRequest
Новая
       17

Инвертировать вложенные словари в f # Map <'a, Map <' b, 'T >>) -> Map <' b, Map <'a,' T >>

3 голосов
/ 22 марта 2012

У меня есть вложенный словарь 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 ]

7 голосов
/ 23 марта 2012

Проблема, которую вы пытаетесь решить, называется транспонированием ориентированного графа и может быть вычислена с использованием двойного сгиба следующим образом: 

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 Алгоритмы графов: топологическая сортировка и кратчайшие пути для всех пар для получения дополнительной информации.

5 голосов
/ 22 марта 2012

Я думаю, что решение от @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
2 голосов
/ 22 марта 2012
Решение

@ 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% быстрее.

2 голосов
/ 22 марта 2012

Я не уверен, что понимаю ваше намерение. Но из сигнатуры вашей функции мы можем сделать что-то вроде этого: 

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
...