问提高F#映射插入性能
EN

Stack Overflow用户

提问于 2020-05-08 19:04:28

回答 1查看 217关注 0票数 5

我目前正在做一些关于F#地图和C#字典的测试。我意识到它们在实现方面有很大的不同，但它们确实为各自的语言提供了相同的用途。

我设计了一个简单的测试来检查插入时间，因为F#映射是不可变的，因此它必须为每次插入创建一个全新的映射。我想知道这到底有多成功。

测试如下：

 //F# 
 module Test = 
    let testMapInsert () = 
        let sw = Stopwatch()
        let rec fillMap endIdx curr map =
            if curr = endIdx then 
                map 
            else 
                fillMap endIdx (curr + 1) (map |> Map.add curr curr)
        sw.Start ()
        let q = fillMap 100000000 Map.empty
        sw.Stop ()
        printfn "%A" sw.ElapsedMilliseconds

 //C#
 class Program
    {
        static void Test(int x) {
            var d = new Dictionary<int,int>();
            for (int i = 0; i < x; i++) {
                d.Add(i,i);
            }
        }
        static void Main(string[] args) {
            Stopwatch sw = new Stopwatch();
            sw.Start();
            Test(10000000);
            sw.Stop();
            System.Console.WriteLine(sw.ElapsedMilliseconds);
            //FSHARP.Test.testMapInsert(); f# function called in c#.

        }
    }

执行1000万次元素插入会产生以下时间(以毫秒为单位)：

C#: 332

F#: 13605

我认为C#字典会更快一些，但这是非常不同的。

对于这种用例，有没有一种方法可以加速F#字典？或者，这只是一种方式，F#映射在这些情况下与线程安全的性能进行了权衡？

.net

dictionary

回答 1

Stack Overflow用户

回答已采纳

发布于 2020-05-08 21:01:35

正如评论中提到的，区别不是基于C#和F#之间的区别，而是基于不可变的基于树的映射和基于哈希表的可变字典之间的区别。

使用#time，我在F# interactive中获得了以下性能：

#time 
// Immutable tree-based F# map (~14 sec)
let mutable map = Map.empty
for i in 0 .. 10000000 do
  map <- Map.add i i map

// Mutable hashtable-based .NET dictionary (~0.3 sec)
let dict = System.Collections.Generic.Dictionary<_, _>()
for i in 0 .. 10000000 do
  dict.Add(i, i)

有趣的问题是-你能让不可变的F#映射变得更快吗？原则上，如果您知道正在使用已排序的数组，则可以更快地构建映射。F#映射没有任何允许您执行此操作的操作，但可以添加它。

当我定义自己的映射类型，它与F#映射共享内部结构时：

type MapTree<'Key, 'Value when 'Key : comparison > = 
  | MapEmpty 
  | MapOne of 'Key * 'Value
  | MapNode of 'Key * 'Value * MapTree<'Key, 'Value> *  MapTree<'Key, 'Value> * int

然后我可以定义ofSortedArray操作：

let height = function
  | MapEmpty -> 0
  | MapOne _ -> 1
  | MapNode(_, _, _, _, h) -> h

let rec ofSortedArray (data:_[]) i j = 
  if i = j then MapOne(data.[i])
  elif i > j then MapEmpty 
  else 
    let m = i + (j - i) / 2
    let l, r = ofSortedArray data i (m - 1), ofSortedArray data (m + 1) j
    let k, v = data.[m]
    MapNode(k, v, l, r, 1 + (max (height l) (height r)))

这仍然比不上可变哈希表的效率，但我得到了以下结论：

// Immutable tree-based F# map, using sorted array 
let arr = [| for i in 0 .. 10000000 -> i, i |] // ~1 sec
let map = ofSortedArray arr 0 10000000         // ~3 sec