具有快速查找/插入/删除功能的循环缓冲区

Question

我有一个问题，我没有找到足够有效的解决方案。我需要加速一个固定大小为 1.000.000 个元素的循环缓冲区。目前使用单向链表实现。

目前，我已将实现更改为使用数组而不是链表。我使用写入和读取指针来避免移动数组的每个索引。我需要在我的 fifo 中进行大量查找，并且我需要从索引中删除项目(好吧，我知道这违反了 fifo 规则)。

首先我想到了一个与fifo数组相匹配的排序索引表。查找的复杂度为 O(log n)，但每次我需要更新我的 fifo 时，我还需要更新我的索引表。这是我未能有效完成的部分(复杂性很小)。

关于跟踪 FIFO 顺序并在插入/删除/搜索操作中提供良好性能的实现的任何提示？

谢谢。

Answer 1

一种方法是使用:

1. 一个包含 n 个元素的数组，用于存储项目
2. A Fenwick tree有 n 个元素来存储占用率。

我们使用分域树在元素存在时写入 1，如果元素不存在则写入 0。

一旦你有了这个结构，你就可以找到第 k^th 个存在的元素并在 O(logn) 时间内执行删除。 (由于 FIFO 环绕，实际的实现细节可能有点繁琐 - 它可能有助于跟踪数组中的总占用率以及从指向第一个元素的指针到数组末尾的占用率。)

请注意，此结构将允许您在任何地方删除项目，但只能在 FIFO 的末尾插入项目 - 不清楚这是否符合您的要求？