纯功能性（持久性）环形缓冲区

Question

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

• 按索引进行高效随机访问
• 加到前面
• 从后面移除

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

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

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

• 双向链表不能高效地进行索引查找，复杂度为O(n)
• 基于Phil Bagwell Ideal Hash Tree的Clojure PersistentVector，支持log32N中的索引访问，subvec可用于从头删除元素。
• 哈希数组映射的 trie 也可以通过将整数存储为键来使用，但可能效率不高。

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

Answer 1

finger tree (in the standard library as Data.Sequence) 是持久随机访问序列的首选。我认为它满足你的标准——随机访问索引是 O(log n) （更具体地说，索引与边缘距离的日志），其他是 O(1)。我不知道还有比这更好的持久数据结构。