提高 F# 地图插入性能

Question

我目前正在对 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# 映射在这些情况下为了线程安全而与性能进行权衡？

Answer 1

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

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

#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# 地图共享内部结构的自己的 Map 类型时：

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

如果你真的想使用它，你需要你自己版本的 F# 映射 - 或者你可以向 F# 核心库发送拉取请求，添加对这样的支持！