在 F# 中批量添加到地图

Question

我有一个简单的类型：

type Token =
    {
        Symbol:     string
        Address:    string
        Decimals:   int
    }

和内存缓存（它们在数据库中）：

let mutable private tokenCache : Map<string, Token> = Map.empty

令牌模块的一部分。

有时我要添加一些新条目，形式为 令牌数组，我想更新缓存。

这种情况很少发生（每百万次读取不到一次）。

当我用新批次更新数据库时，我也想更新缓存映射，我只是这样写的：

tokenCache <- tokens |> Seq.fold (fun m i -> m.Add(i.Symbol, i)) tokenCache

由于这种情况很少发生，我不太关心性能所以这个问题是出于好奇：

当我这样做时，令牌数组中的每个条目都会重新创建一次地图：10 个新令牌，10 个地图重新创建。我认为这是处理此问题的最 'F#' 方法。这让我开始思考：将地图转换为 KVP 列表、获取不同的输出并重新创建地图会不会更高效？还是有其他我没有想到的方法？

Answer 1

这不是对所述问题的回答，而是对您在评论中提出的问题的澄清。

你表达的这个前提是不正确的：

the map will be recreated once per entry in the tokens array

实际上并不是每次插入都完全重新创建地图。但同时，您在评论中表达的另一个假设也不正确：

so the immutability is from the language's perspective, the compiler doesn't recreate the object behind the scenes?

不变性是真实存在的。但是地图也不会每次都重新创建。有时会，但不是每次。

我不打算详细描述 Map 是如何工作的，因为那太复杂了。相反，我将在列表中说明原理。

F# 列表是“单链表”，这意味着每个列表由两部分组成：(1) 第一个元素（称为“头”）和 (2) 对其余元素（称为“头”）的引用（指针） “尾巴”）。这里要注意的关键是“其余元素”部分本身也是一个列表。

因此，如果您像这样声明一个列表：

let x = [1; 2; 3]

它在内存中会像这样表示：

x -> 1 -> 2 -> 3 -> []

名称 x 是对第一个元素的引用，然后每个元素都有对下一个元素的引用，最后一个元素是对空列表的引用。到目前为止一切顺利。

现在让我们看看如果向这个列表中添加一个新元素会发生什么：

let y = 42 :: x

现在列表 y 将表示为：

y -> 42 -> 1 -> 2 -> 3 -> []

但是这张图少了一半。如果我们在比 y 更广泛的范围内查看内存，我们会看到：

    x -> 1 -> 2 -> 3 -> []
         ^
         |
        /
y ->  42

因此您看到 y 列表由两部分组成（所有列表都一样）：第一个元素 42 和对其余元素的引用 1->2->3。但是“其余元素”位并不是 y 独有的，它有自己的名字 x.

所以你有两个列表 x 和 y，分别有 3 个和 4 个元素，但它们加在一起只占用 4 个内存单元，而不是 7 个。

另外要注意的是，当我创建 y 列表时，我不必从头开始重新创建整个列表，也不必复制 1、2，3 从 x 到 y。这些单元格留在原处，y 只得到对它们的引用。

第三点要注意的是，这意味着将元素添加到列表是一个复杂度为 O(1) 的操作。不涉及复制列表。

第四个（希望是最后一个）要注意的是，这种方法只有在 因为不变性 才可行。只是因为我知道 x 列表永远不会改变，所以我可以参考它。如果要更改，我会 forced to copy it 以防万一。

这种数据结构的每次迭代都建立在前一个迭代之上的排列称为“persistent data structure”（嗯，更准确地说，它是一种持久数据结构）。

对于链表，它的工作方式很容易看出，但它也适用于更复杂的数据结构，包括映射（表示为树）。

bulk adding to a map, in F#