标准容器的比较

这是对OCaml标准库所提供的不同容器的一个粗略的比较。以下的n代表容器中元素的数量。

值得注意的是,大O所代表的是当前实现下的效率,并不为官方文档保证。希望以后这些实现不会 变得更糟糕吧。总之,文档才是理解这些模块最好的来源。当然,你也可以尝试阅读源代码。

参见: 标准库示例

Lists: 不可变的单链表

添加一个元素会创建一个新的链表l,从x指向链表tl。tl不会被改变,因此不会被拷贝。

  • 添加一个元素: O(1), cons 操作符 ::
  • 长度: O(n), List.length
  • 索引第i个元素: O(i)
  • 寻找一个元素: O(n)

这个结构比较适合IO和模式匹配。

但不太适合索引。

数组和字符串:可变数组

数组和字符串很相似。只不过字符串是用来紧凑地存贮字符,和一些方便的语法而已。

  • 添加一个元素: O(n)
  • 长度: O(1), Array.length
  • 索引第i个元素: O(1)
  • 寻找一个元素: O(n)

比较适合一些已知大小的元素,下标索引,和在位编辑。数组和字符串的长度都是固定的。如果你想改变 字符串的长度,Buffer模块比较合适。

Set 和 Map:不可变的树

如链表,他们都是不可变的,但是他们有可能共享一些子树。他们比较适合用于保存一些旧版本的数据。

  • 添加一个元素: O(log n)
  • 返回元素的数量: O(n)
  • 寻找一个元素: O(log n)

集合和映射对于编译和元编程(meta-programming)都很有用,但是在某些情况,哈希表会更加合适。

Hashtbl: 自动增长的哈希表

Ocaml的哈希表是可变的,可以把键值存储在同一个数据结构。

  • 添加一个元素:如果表的初始大小比元素数量要大,则是O(1),如果往很小的表插入n个元素,则平均是O(log n)
  • 返回元素的数量: O(1)
  • 寻找一个元素: O(1)

Buffer: 可变长字符串

Buffer提供了一个有效的方式在一个数据结构中累计字节。他们是可变的,

  • 添加一个元素:如果buffer足够大则是O(1),如果buffer远远小于n,那么则平均是O(log n)。
  • 添加一个 k 字符长的字符串: O(k * 添加一个元素)
  • 长度: O(1)
  • 索引第i个元素: O(1)

Queue

OCaml的队列是可变的FIFO,。

  • 添加一个元素:O(1)
  • 获取一个元素: O(1)
  • 长度: O(1)

Stack

Ocaml的栈是可变的LIFO。他们除了可变以外和链表没有区别。

  • 添加一个元素:O(1)
  • 获取一个元素: O(1)
  • 长度: O(1)