假设我创建了一个Vector使用unfoldr,而不是unfoldrN,并且它没有融合,所以实际上需要创建向量.系统如何决定制作它的大小？我在文档中找不到任何相关内容.源代码显示它调用unstream,它有很多复杂的代码,我无法做出头或尾.
我不完全确定,但我追查源代码unfoldr直到Data.Vector.Generic.Mutable.unstream.其文件说明:
创建一个新的可变向量,并用"Stream"中的元素填充它.如果"流"的最大大小未知,则向量将呈指数增长.
所以,我的猜测是它以小尺寸(大约10个)开始并开始填充矢量.一旦向量填满,它就会使其大小加倍(或使其大小增大50%,或者通过其他比例增加其大小)并将旧元素复制到新向量中.指数增长确保如果用n个元素填充向量,则最多将执行O(log(n))个副本,因此总体复杂度将为O(n log(n)),这与线性时间"足够接近" .
实际比率似乎是2,根据enlarge_delta函数,它只返回max 1 (length 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).