arrays - 当 Data.Vector.unfoldr 不融合时会发生什么？

Question

假设我使用 unfoldr 创建一个 Vector，而不是 unfoldrN，它不会融合，所以实际上需要创建向量。系统如何决定其大小？我在文档中找不到任何有关此内容的信息。源代码显示它调用了unstream，其中有很多复杂的代码我无法理解。

Answer 1

我不完全确定，但我从 unfoldr 一直追踪到 Data.Vector.Generic.Mutable.unstream 的源代码。其文档指出:

Create a new mutable vector and fill it with elements from the 'Stream'. The vector will grow exponentially if the maximum size of the 'Stream' is unknown.

所以，我的猜测是它从一个较小的尺寸(例如 10 左右)开始并开始填充向量。一旦向量已满，它就会将其大小加倍(或使其大小增大 50%，或按其他比例增加其大小)并将旧元素复制到新向量中。指数增长确保如果你用 n 个元素填充向量，你最多会执行 O(log(n)) 个副本，因此整体复杂度将为 O(n log(n))，这“足够接近”线性时间.

实际比率似乎是 2，根据 enlarge_delta 函数，该函数仅返回 max 1(长度 v)，该值被传递给 grow 将这么多元素添加到向量中。

<小时/>

如Carl注意，指数复制是 O(n)，而不仅仅是 O(n log(n))。事实上，使用ratio=2，复制元素的数量将是(减去一些舍入)2^0+2^1+...+2^(log(n)) = 2^(log(n)+1) -1 = 2n-1，因此 O(n)。