首页 文章

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

提问于
浏览
206

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

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

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

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

我缺少任何其他形式的数据结构,可能有用吗?

1 回答

  • 313

    列出Rock

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

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

    列表给出Θ(1)缺点和模式匹配 . 标准库以及前提条件库中充满了有用的列表函数,这些函数应该丢失代码( foldrmapfilter ) . 列表是持久的,也就是纯粹的功能,这是非常好的 . Haskell列表实际上不是"lists"因为它们是coinductive(其他语言称之为这些流)所以像

    ones :: [Integer]
    ones = 1:ones
    
    twos = map (+1) ones
    
    tenTwos = take 10 twos
    

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

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

    另一方面

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

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

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

    序列是功能性的

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

    • 纯功能 . Data.Sequence 是一个完全持久的数据结构 .

    • 禁止快速访问树的开头和结尾 . Θ(1)(摊销)以获得第一个或最后一个元素,或附加树 . 事物列表最快, Data.Sequence 最多是一个常数较慢 .

    • Θ(log n)访问序列的中间 . 这包括插入值以生成新序列

    • 高品质的API

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

    阵列不适合胆小的人

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

    Vector是一个“更好”的数组

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

    您还有其他选择

    如果您只想要能够在最后有效插入的列表,则可以使用difference list . 搞砸性能的列表的最佳示例往往来自 [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
    

    实际上, Data.Traversable 定义了一个在任何事物"list like"中或多或少具有通用性的API .

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


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

    newList oldList = 7 : drop 5 oldList
    

    不要复制它 . 因此,即使 oldList 非常长,这个"modification"也会非常快 . 同样

    newSequence newValue oldSequence = Sequence.update 3000 newValue oldSequence
    

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

    您无法使用 VectorsArrays 轻松完成此操作 . 它们可以被修改,但这是真正的命令性修改,因此无法在常规Haskell代码中完成 . 这意味着 Vector 包中的操作会使 snoccons 之类的修改必须复制整个向量,所以需要 O(n) 时间 . 唯一的例外是你可以在 ST monad(或 IO )中使用可变版本( Vector.Mutable ),并像在命令式语言中那样进行所有修改 . 完成后,您可以将矢量转换为要与纯代码一起使用的不可变结构 .

    我的感觉是,如果列表不合适,您应该默认使用 Data.Sequence . 仅当您的使用模式不涉及进行许多修改,或者您需要ST / IO monad中的极高性能时,才使用 Data.Vector .

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

相关问题