2

我需要为一个大列表（float*float）编写一个查找函数。如果未找到键，则此函数应添加新条目，如果找到键，则应将值相加。我读过关于记忆计算的文章，实际上它并没有那么难做。这是我所拥有的：

let memoLookUp basearr lookarr =
    let t = new System.Collections.Generic.Dictionary<float,float>()
    for (a,b) in basearr do
        t.Add(a,b)
    for (a, b) in lookarr do
        if t.ContainsKey(a) then t.[a] <- t.[a] + b
        else t.Add(a,b)
    t

样本数据：

let basearr = [(41554., 10.0) ; (41555., 11.0) ; (41556., 12.0) ; (41557., 10.0) ; (41558., 13.0) ]

let lookarr = [(41555., 14.0) ; (41556., 15.0) ; (41559., 16.0)]

这将按预期返回。

我的问题是：

  • 如果列表很长（比如每个大约 30000 个），从性能的角度来看这样做是否明智？
  • 还是按日期排序（在每个数据列表的第一列中）然后使用更重要的方法会更好吗？
  • 或者在 f# 或 c# 中是否有内置的东西？
4

2 回答 2

4

您现有的代码可能有用地合并两个数组以具有更统一的行为。除非另有需要，（例如，如果 basearr 包含重复项，您希望程序崩溃）uniform 更好

let incrementalAdderImperative aseq = 
  let d= System.Collections.Generic.Dictionary<_,_>()
  Seq.iter(fun (k,v) ->  if d.ContainsKey(k) 
                         then d.[k] <- d.[k] + v
                         else d.Add(k,v)) aseq

要回答您的问题：

  • 如果列表很长（比如每个大约 30000 个），从性能的角度来看这样做是否明智？

您正在使用基于哈希的字典，依赖于 Dictionary 类。所以它根本不应该退化。请注意，这是字典实现的属性，而不是字典功能的属性，如 IDictionary 中所述。还有其他实现（例如 Map）

如果您担心性能，您应该使用（快速）估计将发生多少键以避免内部调整大小来初始化您的字典。并知道使用的具体类型（如基于哈希的字典等）

  • 按日期排序（在每个数据列表的第一列中）然后使用更重要的方法会更好吗？

如果按日期排序，则可以折叠。我认为这会更快，但你提到的数字并没有那么大。

let oneshotAdder reducer kvArr =
    kvArr |> Array.sortInPlaceBy fst
    let a = kvArr 
            |> Array.fold(fun (res) (k,v) ->  
                            match res with
                            | []                             -> (k,v)::res
                            | ((prevk,_)::xs) when k = prevk -> (k,reducer v (List.head res |> snd))::(List.tail res)
                            | _                              -> (k,v)::res)
                          List.empty
    dict a
let data = Array.concat ([basearr; lookarr] |> List.map List.toArray)
let dict2 = oneshotAdder (+) data

ps：在您给出的示例中， basearr 和 lookarr 是列表，而不是数组，因此假设您确实想要对数组进行操作，则无关操作。

  • 在 f# 或 c# 中甚至有内置的东西吗？

在 F# 中，您可以原生地执行 groupby 并将它们求和。集合变换的本质是传递函数，所以原生拥有它也就不足为奇了。在 C# 中，您可以使用 Linq 来获取此类枚举转换，这些转换在底层映射到 fsharp 中的某些函数。

let groupByAdder reducer (kvArr:('k*'v) array)  =
    kvArr |> Seq.groupBy fst 
          |> Seq.map (fun (k,vs) -> k , vs |> Seq.map snd |> (Seq.reduce reducer)) 
          |> dict
let dict3 = groupByAdder (+) data
于 2013-10-10T13:39:20.463 回答
1

我会做：

Seq.groupBy fst kvs
|> Seq.map (fun (k, vs) -> k, Seq.map snd vs |> Seq.reduce (+))
|> dict
于 2013-10-11T01:32:37.017 回答