我正在学习Haskell,并阅读了几篇关于Haskell列表和(插入语言)数组的性能差异的文章 .
作为一个学习者,我显然只是在不考虑性能差异的情况下使用列表 . 我最近开始调查并发现Haskell中有许多数据结构库 .
有人可以解释一下列表,数组,向量,序列之间的区别,而不是深入研究数据结构的计算机科学理论吗?
此外,是否有一些常见的模式,您将使用一个数据结构而不是另一个?
我缺少任何其他形式的数据结构,可能有用吗?
到目前为止,Haskell中顺序数据最友好的数据结构是List
data [a] = a:[a] | []
列表给出Θ(1)缺点和模式匹配 . 标准库以及前提条件库中充满了有用的列表函数,这些函数应该丢失代码( foldr , map , filter ) . 列表是持久的,也就是纯粹的功能,这是非常好的 . Haskell列表实际上不是"lists"因为它们是coinductive(其他语言称之为这些流)所以像
foldr
map
filter
ones :: [Integer] ones = 1:ones twos = map (+1) ones tenTwos = take 10 twos
工作得非常好 . 无限的数据结构摇滚 .
Haskell中的列表提供了一个界面,就像命令式语言中的迭代器一样(因为懒惰) . 因此,它们被广泛使用是有道理的 .
列表的第一个问题是索引它们 (!!) 需要Θ(k)时间,这很烦人 . 此外,附加可能很慢 ++ ,但Haskell的懒惰评估模型意味着如果它们发生的话,这些可以被视为完全摊销 .
(!!)
++
列表的第二个问题是它们的数据位置较差 . 当内存中的对象没有彼此相邻布局时,真实处理器会产生高常量 . 因此,在C std::vector 中,比我知道的任何纯链表数据结构更快"snoc"(放置对象),尽管这不是一个持久的数据结构,因此不如Haskell的列表友好 .
std::vector
列表的第三个问题是它们的空间效率很差 . 一串额外的指针推高你的存储空间(按常数因素) .
Data.Sequence 内部基于finger trees(我知道,你不想知道这一点)这意味着它们有一些不错的属性
Data.Sequence
纯功能 . Data.Sequence 是一个完全持久的数据结构 .
禁止快速访问树的开头和结尾 . Θ(1)(摊销)以获得第一个或最后一个元素,或附加树 . 事物列表最快, Data.Sequence 最多是一个常数较慢 .
Θ(log n)访问序列的中间 . 这包括插入值以生成新序列
高品质的API
另一方面, Data.Sequence 对数据局部性问题没有太大作用,只适用于有限集合(它比列表更不懒惰)
数组是CS中最重要的数据结构之一,但它们与懒惰的纯函数世界不太匹配 . 数组提供对集合中间的Θ(1)访问和非常好的数据局部性/常数因子 . 但是,由于它们不适合Haskell,它们很难使用 . 实际标准库中实际上有许多不同的数组类型 . 这些包括完全持久的数组,IO monad的可变数组,ST monad的可变数组,以及上面的非盒装版本 . 了解更多信息the haskell wiki
Data.Vector 包提供了更高级别和更清晰的API的所有阵列优势 . 除非你真的知道自己在做什么,否则你应该使用这些,如果你需要像数组一样的性能 . 当然,一些警告仍然适用 - 像数据结构这样的可变数组在纯粹的懒惰语言中并不好用 . 尽管如此,有时你想要O(1)性能, Data.Vector 在可用的包中给你 .
Data.Vector
如果您只想要能够在最后有效插入的列表,则可以使用difference list . 搞砸性能的列表的最佳示例往往来自 [Char] ,前奏已将别名为 String . Char 列表很方便,但往往比C字符串慢20倍,所以随意使用 Data.Text 或非常快 Data.ByteString . 我现在没想到 .
[Char]
String
Char
Data.Text
Data.ByteString
我需要在Haskell列表中进行顺序收集的90%是正确的数据结构 . 列表与迭代器类似,使用列表的函数可以使用它们附带的 toList 函数轻松地与任何其他数据结构一起使用 . 在一个更美好的世界中,前奏将完全参数化,以确定它使用的容器类型,但目前 [] 垃圾标准库 . 因此,使用列表(几乎)每个地方都可以 .你可以完全得到大多数列表函数的参数化版本(并且很高兴使用它们)
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.Traversable
尽管如此,虽然你可以很好并且只编写完全参数化的代码,但我们大多数人并不是并且在所有地方使用列表 . 如果你正在学习,我强烈建议你也这样做 .
编辑:基于评论,我意识到我从未解释何时使用 Data.Vector vs Data.Sequence . 数组和向量提供极快的索引和切片操作,但基本上是瞬态(命令性)数据结构 . 纯函数数据结构(如 Data.Sequence 和 [] )可以有效地从旧值生成新值,就像您修改了旧值一样 .
newList oldList = 7 : drop 5 oldList
不要复制它 . 因此,即使 oldList 非常长,这个"modification"也会非常快 . 同样
oldList
newSequence newValue oldSequence = Sequence.update 3000 newValue oldSequence
将生成一个带有 newValue for的新序列,代替其3000元素 . 同样,它不会破坏旧序列,只会创建一个新序列 . 但是,它非常有效地执行此操作,取O(log(min(k,k-n)),其中n是序列的长度,k是您修改的索引 .
newValue
您无法使用 Vectors 和 Arrays 轻松完成此操作 . 它们可以被修改,但这是真正的命令性修改,因此无法在常规Haskell代码中完成 . 这意味着 Vector 包中的操作会使 snoc 和 cons 之类的修改必须复制整个向量,所以需要 O(n) 时间 . 唯一的例外是你可以在 ST monad(或 IO )中使用可变版本( Vector.Mutable ),并像在命令式语言中那样进行所有修改 . 完成后,您可以将矢量转换为要与纯代码一起使用的不可变结构 .
Vectors
Arrays
Vector
snoc
cons
O(n)
ST
IO
Vector.Mutable
我的感觉是,如果列表不合适,您应该默认使用 Data.Sequence . 仅当您的使用模式不涉及进行许多修改,或者您需要ST / IO monad中的极高性能时,才使用 Data.Vector .
如果所有关于 ST monad的谈话让你感到困惑:更有理由坚持纯粹的快速和美丽 Data.Sequence .
1 回答
列出Rock
到目前为止,Haskell中顺序数据最友好的数据结构是List
列表给出Θ(1)缺点和模式匹配 . 标准库以及前提条件库中充满了有用的列表函数,这些函数应该丢失代码(
foldr
,map
,filter
) . 列表是持久的,也就是纯粹的功能,这是非常好的 . Haskell列表实际上不是"lists"因为它们是coinductive(其他语言称之为这些流)所以像工作得非常好 . 无限的数据结构摇滚 .
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
函数轻松地与任何其他数据结构一起使用 . 在一个更美好的世界中,前奏将完全参数化,以确定它使用的容器类型,但目前[]
垃圾标准库 . 因此,使用列表(几乎)每个地方都可以 .你可以完全得到大多数列表函数的参数化版本(并且很高兴使用它们)
实际上,
Data.Traversable
定义了一个在任何事物"list like"中或多或少具有通用性的API .尽管如此,虽然你可以很好并且只编写完全参数化的代码,但我们大多数人并不是并且在所有地方使用列表 . 如果你正在学习,我强烈建议你也这样做 .
编辑:基于评论,我意识到我从未解释何时使用
Data.Vector
vsData.Sequence
. 数组和向量提供极快的索引和切片操作,但基本上是瞬态(命令性)数据结构 . 纯函数数据结构(如Data.Sequence
和[]
)可以有效地从旧值生成新值,就像您修改了旧值一样 .不要复制它 . 因此,即使
oldList
非常长,这个"modification"也会非常快 . 同样将生成一个带有
newValue
for的新序列,代替其3000元素 . 同样,它不会破坏旧序列,只会创建一个新序列 . 但是,它非常有效地执行此操作,取O(log(min(k,k-n)),其中n是序列的长度,k是您修改的索引 .您无法使用
Vectors
和Arrays
轻松完成此操作 . 它们可以被修改,但这是真正的命令性修改,因此无法在常规Haskell代码中完成 . 这意味着Vector
包中的操作会使snoc
和cons
之类的修改必须复制整个向量,所以需要O(n)
时间 . 唯一的例外是你可以在ST
monad(或IO
)中使用可变版本(Vector.Mutable
),并像在命令式语言中那样进行所有修改 . 完成后,您可以将矢量转换为要与纯代码一起使用的不可变结构 .我的感觉是,如果列表不合适,您应该默认使用
Data.Sequence
. 仅当您的使用模式不涉及进行许多修改,或者您需要ST / IO monad中的极高性能时,才使用Data.Vector
.如果所有关于
ST
monad的谈话让你感到困惑:更有理由坚持纯粹的快速和美丽Data.Sequence
.