haskell - 纯功能性(持久性)环形缓冲区

Question

我想使用纯功能数据结构和以下操作来实现环形缓冲区

• 通过索引进行高效随机访问
• 添加到前面
• 从背面移除

使用持久数据结构的原因是因为我有一个写入器线程和多个读取器线程，并且我想避免读取器阻塞写入器。

这可以通过让读取器线程仅在拍摄快照时持有锁，然后使用快照进行处理来轻松完成。

支持这些操作的现有可用数据结构是什么？

• 双向链表无法高效地进行索引查找，且时间复杂度为 O(n)
• Clojure PersistedVector 基于 Phil Bagwell 理想哈希树，支持 log32N 中的索引访问，并且可以使用 subvec 从头开始​​删除元素。
• 也可以通过将整数存储为键来使用哈希数组映射的 trie，但可能效率不高。

在这种情况下还可以使用其他哪种纯函数式数据结构？

Answer 1

finger tree (在标准库中为 Data.Sequence )是持久随机访问序列的首选。我认为它满足你的标准——随机访问索引是O(log n)(更具体地说，索引到边缘的距离的对数)，其他是O(1).我不知道有任何持久数据结构比这做得更好。