用于大量连接和单次迭代的最快不可变列表数据结构

Question

我正在使用Haskell.标准列表连接是天真和缓慢的.我的情况是我有一个算法,它建立一个单独的列表连接(顺序无关紧要,所以它可以是前置或附加或组合)多次,然后返回它.结果将只使用一次.高性能至关重要.

所以,这是一个非常简单的情况.我听说过差异列表,这有助于解决这种情况.但那是最好的选择吗？

列表可能会变得很大:100,000个条目.

Answer 1

这是一个经验问题,应该凭经验回答.合理的替代方案包括

• 有缺点的标准清单(在你的问题中称为"前置")

• 差异列表(约翰休斯列表)与恒定时间追加

• 支持常数时间追加的代数数据类型:

  data Alist a = ANil | ASingle a | AAppend (Alist a) (Alist a)
  

• 最终列表清单concat.

所有这些都需要线性时间.但是不变因素很重要,唯一的方法就是建立和衡量.如果您愿意,可以通过将每个列表操作记录到编写器monad中来创建完全忠实于原始代码但仅执行列表操作的微基准测试.但这可能是屁股的巨大痛苦而且不值得.相反,编写一个简单的基准测试,编译(打开优化)和测量.

请告诉我们结果.

Answer 2

如果订单无关紧要,只需使用普通列表即可.前置(consing)是O(1)并且整个列表的行走是O(n),这与你感兴趣的操作一样好.

如果您实际上关心的是附加而不是前置,则差异列表很有用,因为虽然前置对于普通列表来说很快,但是附加是O(n).差异列表允许O(1)追加.除了易于附加之外,差异列表在每种情况下都比正常列表慢或慢.

Answer 3

如果你可以逐个追加元素,那么普通列表就可以了.

如果只能附加块,那么列表列表会更好,因为添加新块变为O(1)而不是O(N),其中N是块大小.

有两个因素可以帮助列表快速列出:

• 怠惰
• 列表融合

只有当你由一个优秀的生产者生成列表并由一个好的消费者消费它时,两者才会起作用.因此,如果您的生产者和消费者是好的并且您以单线程方式使用列表,那么GHC将生成只有循环而根本没有中间列表,因为列表融合.存在两种不同的列表融合实现:所谓的构建/折叠和流融合.另见http://www.haskell.org/haskellwiki/Correctness_of_short_cut_fusion

如果生产者和消费者都很好但列表融合不参与(因为你没有使用优化标志,因为GHC不支持特定的融合优化,或者如果你使用GHC以外的编译器而没有融合支持),你仍然会得到合理的由于懒惰而表现.在这种情况下,将生成中间列表,但立即由垃圾收集器收集.