Haskell:列表,数组,向量,序列

Question

Haskell:列表,数组,向量,序列

r.s*_*cky 221 haskell

我正在学习Haskell,并阅读了几篇关于Haskell列表和(插入语言)数组的性能差异的文章.

作为一个学习者,我显然只是在不考虑性能差异的情况下使用列表.我最近开始调查,发现Haskell中有许多数据结构库.

有人可以解释一下列表,数组,向量,序列之间的区别,而不是深入研究数据结构的计算机科学理论吗？

此外,是否有一些常见的模式,您将使用一个数据结构而不是另一个？

是否有任何其他形式的数据结构我缺少并可能有用？

Answer 1

Phi*_* JF 329

列出摇滚

到目前为止,Haskell中顺序数据最友好的数据结构是List

 data [a] = a:[a] | []

Run Code Online (Sandbox Code Playgroud)

列表给出Θ(1)缺点和模式匹配.标准库,并为此事的序幕,充满了有用的列表功能应该垃圾代码(foldr,map,filter).列表是持久的,也就是纯粹的功能,这是非常好的.Haskell列表并不是真正的"列表",因为它们是coinductive(其他语言称之为这些流),所以类似于

ones :: [Integer]
ones = 1:ones

twos = map (+1) ones

tenTwos = take 10 twos

Run Code Online (Sandbox Code Playgroud)

工作得很好.无限的数据结构摇滚.

Haskell中的列表提供了一个非常类似于命令式语言中的迭代器的界面(因为懒惰).因此,它们被广泛使用是有道理的.

另一方面

列表的第一个问题是索引它们(!!)需要Θ(k)时间,这很烦人.此外,追加可能很慢++,但Haskell的懒惰评估模型意味着如果它们发生,它们可以被视为完全摊销.

列表的第二个问题是它们的数据位置较差.当内存中的对象没有彼此相邻布局时,真实处理器会产生高常量.因此,在C++ std::vector中,我所知道的任何纯链接列表数据结构都具有更快的"snoc"(将对象放在最后),尽管这不是一个持久的数据结构,因此不如Haskell的列表友好.

列表的第三个问题是它们的空间效率很差.一串额外的指针推高你的存储空间(按常数因素).

序列是功能性的

Data.Sequence内部基于指树(我知道,你不想知道这一点),这意味着它们有一些不错的属性

纯粹的功能. Data.Sequence是一个完全持久的数据结构.
快速访问树的开头和结尾.Θ(1)(摊销)以获得第一个或最后一个元素,或附加树.事物列表最快,Data.Sequence最多是一个不变的慢.
Θ(log n)访问序列的中间.这包括插入值以生成新序列
高品质的API

另一方面,Data.Sequence对数据局部性问题没有太大作用,只适用于有限集合(它比列表更不懒惰)

阵列不适合胆小的人

数组是CS中最重要的数据结构之一,但它们与懒惰的纯函数世界不太匹配.数组提供对集合中间的Θ(1)访问和非常好的数据局部性/常数因子.但是,由于它们不适合Haskell,它们很难使用.当前标准库中实际上有许多不同的数组类型.这些包括完全持久的数组,IO monad的可变数组,ST monad的可变数组,以及上面的非盒装版本.有关更多信息,请查看haskell wiki

Vector是一个"更好"的数组

该Data.Vector软件包提供了更高级别和更清晰的API的所有阵列优势.除非你真的知道自己在做什么,否则你应该使用这些,如果你需要像数组一样的性能.当然,一些警告仍然适用 - 像数据结构这样的可变数组在纯粹的懒惰语言中不会很好用.不过,有时你想要O(1)性能,并 Data.Vector在可用的包中给你.

你还有其他选择

如果您只想要能够在末尾有效插入的列表,则可以使用差异列表.搞砸性能的列表的最佳示例往往来自[Char]前奏的别名String. Char列表很方便,但往往比C字符串慢20倍,所以随意使用Data.Text或非常快Data.ByteString.我敢肯定还有其他面向序列的库我现在没想到.

结论

我需要在Haskell列表中进行顺序收集的90%以上是正确的数据结构.列表与迭代器类似,使用列表的函数可以使用toList它们附带的函数轻松地与任何其他数据结构一起使用.在一个更美好的世界中,前奏将完全参数化,以确定它使用的容器类型,但目前 []是标准库.因此,使用列表(几乎)每个地方都绝对没问题.
您可以获得大多数列表函数的完全参数化版本(并且使用它们很高尚)

Prelude.map                --->  Prelude.fmap (works for every Functor)
Prelude.foldr/foldl/etc    --->  Data.Foldable.foldr/foldl/etc
Prelude.sequence           --->  Data.Traversable.sequence
etc

Run Code Online (Sandbox Code Playgroud)

实际上,Data.Traversable定义一个在"list like"之类的内容中或多或少具有通用性的API.

尽管如此,虽然你可以很好并且只编写完全参数化的代码,但我们大多数人并不是并且在所有地方使用列表.如果你正在学习,我强烈建议你也这样做.

编辑:根据意见,我意识到,我从来没有解释何时使用Data.VectorVS Data.Sequence.数组和向量提供极快的索引和切片操作,但基本上是瞬态(命令性)数据结构.纯函数数据结构,Data.Sequence并且可以[]有效地从旧值生成新值,就像您修改了旧值一样.

  newList oldList = 7 : drop 5 oldList

Run Code Online (Sandbox Code Playgroud)

不修改旧列表,也不必复制它.因此即使oldList非常长,这种"修改"也会非常快.同样

  newSequence newValue oldSequence = Sequence.update 3000 newValue oldSequence

Run Code Online (Sandbox Code Playgroud)

将产生一个新的序列,其中有一个newValuefor代替其3000元素.同样,它不会破坏旧序列,只会创建一个新序列.但是,它非常有效地执行此操作,取O(log(min(k,kn)),其中n是序列的长度,k是您修改的索引.

你不能轻易地用Vectors和做Arrays.它们可以被修改,但这是真正的命令性修改,因此无法在常规Haskell代码中完成.这意味着Vector包中的操作会进行修改,snoc并且cons必须复制整个向量,因此需要O(n)时间.唯一的例外是你可以Vector.Mutable在STmonad(或IO)中使用mutable version()并像在命令式语言中那样进行所有修改.完成后,您将"冻结"矢量以转换为要与纯代码一起使用的不可变结构.

我的感觉是,Data.Sequence如果列表不合适,您应该默认使用.使用Data.Vector仅当您需要的ST/IO单子内极高的性能,如果您的使用模式并不涉及让许多修改,或.

如果所有关于STmonad的谈话让你感到困惑:更有理由坚持纯粹的快速和美丽Data.Sequence.

我听过的一个见解是,列表基本上与Haskell中的数据结构一样是一个控制结构.这是有道理的:在不同的语言中使用C风格的循环,你会在Haskell中使用`[1 ..]`列表.列表也可以用于回溯等有趣的事情.将它们视为控制结构(某种程度)确实有助于理解它们的使用方式. (42认同)
很好的答案.我唯一的抱怨是"序列功能正常"在他们身上有点贬低.序列是功能性的awesomesauce.另一个好处是快速加入和分裂(log n). (20认同)
关于(纯)向量和复制的关注部分通过流融合来缓解,例如:`import qualified Data.Vector.Unboxed as VU; main = print(VU.cons'a'(VU.replicate 100'b'))`在Core中编译为404字节(101个字符)的单个分配:http://hpaste.org/65015 (4认同)
@DanBurton Fair.我做的可能是"Data.Sequence".手指树是计算史上最棒的发明之一(Guibas应该有一天可能获得图灵奖),而"Data.Sequence"是一个很好的实现,并且有一个非常有用的API. (3认同)
"UseData.Vector只有在你的使用模式不需要做很多修改时,或者如果你需要在ST/IO monad中有极高的性能......"有趣的措辞,因为如果你*进行了很多修改(如重复(100k)时间)演变100k元素),然后你*做*需要ST/IO Vector才能获得可接受的性能, (3认同)

归档时间：	13 年，6 月前
查看次数：	31758 次
最近记录：	8 年，9 月前