在Haskell中列出操作性能

Question

我目前正在学习Haskell,我很好奇以下内容:

如果我在Haskell中向一个列表中添加一个元素,Haskell会返回一个(完全？)新列表,并且不会操纵原始列表.

现在假设我有一个包含一百万个元素的列表,并在最后添加一个元素.Haskell"复制"整个列表(100万个元素)并将元素添加到该副本中吗？或者是否有一个整洁的"技巧"在幕后进行,以避免复制整个列表？

如果没有"技巧",复制大型列表的过程是不是像我想的那样昂贵？

Answer 1

这是一个非常复杂的问题,因为Haskell和GHC的两个特性:

1. 懒惰的评价
2. 列表融合

列表融合意味着在某些情况下,GHC可以将列表处理代码重写为不分配列表单元的循环.因此,根据使用它的上下文,相同的代码可能不会产生额外的成本.

延迟评估意味着如果不消耗操作的结果,那么您不需要支付计算它的成本.因此,例如,这很便宜,因为您只需要构建列表的前十个元素:

example = take 10 ([1..1000000] ++ [1000001])

实际上,在该代码中,take 10可以与列表追加融合,因此它与刚才相同[1..10].

但是,我们假设我们正在使用我们制作的所有列表中的所有元素,并且编译器没有融合我们的列表操作.现在回答你的问题:

如果我在Haskell中向List中添加一个元素,Haskell会返回一个(completly？)新列表,并且不会操作原始列表.现在假设我有一个包含一百万个元素的列表,并在最后添加一个元素.Haskell"复制"整个列表(100万个元素)并将元素添加到该副本中吗？或者是否有一个整洁的"技巧"在幕后进行,以避免复制整个列表？

有一些技巧可以避免复制整个列表,但是通过追加它可以打败它们.要理解的是,通常设计功能数据结构,以便"修改"它们的操作将利用结构共享来尽可能多地重用旧结构.例如,附加两个列表可以像这样定义:

(++) :: [a] -> [a] -> [a]
[] ++ ys = ys
(x:xs) ++ ys = x : xs ++ ys

查看此定义,您可以确定列表ys将在结果中重用.因此,如果我们拥有xs = [1..3],ys = [4..5]并且xs ++ ys一次完全评估并保留在内存中,它将看起来像这样的记忆:

           +---+---+    +---+---+    +---+---+
      xs = | 1 | -----> | 2 | -----> | 3 | -----> []
           +---+---+    +---+---+    +---+---+

           +---+---+    +---+---+ 
      ys = | 4 | -----> | 5 | -----> []
           +---+---+    +---+---+    
             ^
             |
             +------------------------------------+
                                                  |
           +---+---+    +---+---+    +---+---+    |
xs ++ ys = | 1 | -----> | 2 | -----> | 3 | -------+
           +---+---+    +---+---+    +---+---+

这是很长的说法:如果你这样做xs ++ ys,并且它没有融合,并且你消耗了整个列表,那么这将创建一个副本xs但重用内存ys.

但现在让我们再看看你的问题:

现在假设我有一个包含一百万个元素的列表,并在最后添加一个元素.Haskell"复制"整个列表(100万个元素)并将元素添加到该副本中吗？

那将是类似的[1..1000000] ++ [1000001],是的,它将复制整个百万元素.但另一方面,[0] ++ [1..1000000]只会复制[0].经验法则是这样的:

• 在列表的开头添加元素是最有效的.
• 在列表末尾添加元素通常效率低下,特别是如果您反复执行此操作.

这类问题的一般解决方案是:

1. 修改您的算法,以便在他们有效支持的访问模式中使用列表.
2. 不要使用列表; 使用一些其他序列数据结构,有效地支持您手头的问题所需的访问模式.另一个答案提到差异清单,但值得一提的是:
   • Data.Sequence
   • Data.Set
   • Data.Vector

Answer 2

这取决于您使用的数据结构.如果您使用的是普通的Haskell列表,则这些列表类似于C或C++中的典型链表实现.使用这种结构,附加是O(n)复杂度,而前置是O(1)复杂度.如果您尝试追加一百万个元素,则需要O(500000500000)时间(O(1)+ O(2)+ O(3)+ ... + O(1000000))大约500000500000次操作.这与您使用的语言无关,无论是Haskell,C,C++,Python,Java,C#,还是汇编程序.

但是,如果你要使用类似的结构Data.Sequence.Seq,那么它在内部使用适当的结构来提供O(1)prepends和appends,但是成本是它可以占用更多的RAM.但是,所有数据结构都需要权衡,取决于您要使用的是哪一个.

或者,您也可以使用Data.Vector.Vector或者Data.Array.Array都提供固定长度的连续内存阵列,但是附加和前置是昂贵的,因为您必须将整个阵列复制到RAM中的新位置.但索引是O(1),并且在这些结构之一上映射或折叠会快得多,因为数组的块一次可以适合您的CPU缓存,而不是链接列表或元素分散在各处的序列你的RAM.

Haskell"复制"整个列表(100万个元素)并将元素添加到该副本中吗？

不一定,编译器可以确定将最后一个值的next指针更改为指向新值而不是空列表是否安全,或者如果它不安全则可能需要复制整个列表.但是,这些问题是数据结构所固有的,而不是语言.一般来说,我会说Haskell的列表比C链表更好,因为编译器更能分析何时比程序员安全,并且C编译器不会进行这种分析,他们就像他们完全一样"有人说.