我目前正在学习Haskell,并对以下内容感到好奇:
如果我将元素添加到Haskell的列表中,Haskell将返回(完全?)新列表,并且不会操纵原始列表。
现在,假设我有一个一百万个元素的列表,并在最后追加一个元素。 Haskell是否“复制”整个列表(一百万个元素)并将该元素添加到该副本中?还是在幕后进行一些巧妙的“技巧”以避免复制整个列表?
如果没有“技巧”,复制大列表的过程是否不像我想的那样昂贵?
最佳答案
这取决于您使用的数据结构。如果您使用的是普通的Haskell列表,则这些列表类似于C或C++中典型的链表实现。使用这种结构,追加和索引(最坏情况)为O(n)复杂度,而前置为O(1)复杂度。如果您经常追加内容,并且列表呈线性增长,则其有效值为O(n ^ 2)。对于大型列表,这是一个问题。这与您使用的是哪种语言无关,无论是Haskell,C,C++,Python,Java,C#甚至是汇编语言。
但是,如果使用 Data.Sequence.Seq
之类的结构,则它在内部使用适当的结构来提供O(1)前置和追加,但是代价是它可能占用更多的RAM。但是,所有数据结构都需要权衡取舍,这取决于您要使用哪种结构。
另外,您也可以使用Data.Vector.Vector
或Data.Array.Array
,它们都提供固定长度的连续内存阵列,但是追加和前置操作很昂贵,因为您必须将整个阵列复制到RAM中的新位置。但是,索引为O(1),并且在这些结构之一上进行映射或折叠会更快,因为数组的块可以一次放入您的CPU缓存中,而链表或序列的元素散布在各处你的RAM。
Haskell是否“复制”整个列表(一百万个元素)并将该元素添加到该副本中?
不一定,编译器可以确定仅更改最后一个值的next
指针以指向新值而不是空列表是否安全,或者如果不安全,则可能需要复制整个列表。这些问题是数据结构固有的,不是语言固有的。通常,我想说Haskell的列表比C链接的列表要好,因为与程序员相比,编译器在安全的情况下更能分析这种情况,并且C编译器不会进行此类分析,它们只是按照自己的方式进行分析。被告知。