连接的复杂性()

林肯 Concat() 操作绝不等同于函数 cons 操作。他们很不一样。对于每个cons操作,都会创建一个“new”列表。这实际上很快,因为游戏中的数据结构是专门为这种用途而设计的。对于每一个Concat操作,都会创建一个新的迭代器,而不是真正意义上的迭代器。为了说明每次都做了什么,请考虑下面的简短示例:

1:2:3:[]

功能性操作包括几个评估步骤。 3:[] 临时列表中的结果 [3] ,然后 2:[3] 列表中的结果 [2,3] 和 1:[2,3] . 那是3 简单的 创建列表的步骤。要“迭代”它,需要一些递归和匹配(或者任何与Haskell等价的东西)。大约需要3到4个 复杂的 步骤(每个列表段一个)。

new[] { 1 }.Concat(new[] { 2 }).Concat(new[] { 3 });

LINQ操作也包含几个步骤,需要进行评估。 new[] { 1 }.Concat(new[] { 2 }) 产生一个新的迭代器来遍历序列 [[1]+[2]] ,最后一个生成一个新的迭代器,遍历序列 [[[1]+[2]]+[3]] . 创建迭代器只需要两个简单的步骤,但是您应该注意序列的实际表示是多么复杂。这里使用5个迭代器,每个数组(3)使用一个迭代器,每个连接对(2)使用一个迭代器。我不会完成迭代的所有步骤,但这会执行更多的函数调用和属性访问(根据每个迭代器的要求)。

new[] { 1 }.Concat(new[] { 2 }.Concat(new[] { 3 }))

LINQ操作在结构上看起来更为等价,它的创建步骤与 [[1]+[[2]+[3]]] 使用相同数量的迭代器,并进行同样复杂的迭代。

您可能认为函数版本应该更复杂,因为我们需要一些递归函数。好吧,这并不是因为函数式语言就是这样做的,而且它们是为这种用途而优化的。它们的优点是使用可以在其他组合列表中重用的不可变序列。用这种方式使用LINQ生成复杂的序列并不是它真正要做的。语言没有优化(有些是JIT做的,但就是JIT做的),而且很明显这不是你想要在序列中迭代的方式。你正好击中了它的头部,我知道为什么它很复杂。

我认为为了获得更好的性能,更好的方法是创建链接列表来表示连接的序列。你可以使用 LinkedList<T> 类,创建自己的数据结构,使其想起函数列表,甚至更好,请使用F FSharpList<T> . 然后使用扩展方法和其他支持类进行扩展。

你可以试试。AsParallel,但我怀疑并行化是否值得,除非你的序列非常大,而且只能对可索引数据起作用