设计由许多线程读取并由少数编写的高性能排序数据结构

Question

我有一个有趣的数据结构设计问题,超出了我目前的专业知识.我正在寻找解决这个问题的数据结构或算法答案.

要求:

• (pointer address, size)在一个位置存储合理数量的对(实际上是两个数字;第一个用作排序键)
• 在高度线程化的应用程序中,许多线程将查找值,以查看特定指针是否在其中一(address, size)对内 - 即,如果该对定义了内存范围,则指针是否在列表中的任何范围内.线程将更少地添加或删除此列表中的条目.
• 读取或搜索值必须尽可能快,每秒发生数十万到数百万次
• 添加或删除值,即改变列表,更少发生 ; 表现并不那么重要
• 列表内容过时是可接受但不理想的,即线程的查找代码找不到应该存在的条目,只要在某些时候条目将存在.

我希望避免一个天真的实现,例如有一个关键部分来序列化对排序列表或树的访问.哪些数据结构或算法可能适合此任务？

---

用Delphi标记,因为我正在使用该语言执行此任务.语言无关的答案非常受欢迎.

但是,我可能无法使用任何语言的任何标准库而不需要太多关心.原因是内存访问(对象的分配,释放等及其内部存储器,例如树节点等)受到严格控制,必须通过我自己的功能.我在同一程序中其他地方的当前代码使用红/黑树和一点点特里,我自己写了这些.对象和节点分配通过自定义内存分配例程运行.这超出了问题的范围,但这里提到的是为了避免像'使用STL结构foo'这样的答案.我热衷于算法或结构答案,只要我有正确的参考或教科书,我就可以实现自己.

Answer 1

我将使用TDictionary<Pointer, Integer>(from Generics.Collections) 与TMREWSync(from SysUtils) 组合进行多读独占写访问。TMREWSync只要没有作者活跃，就允许多个读者同时访问字典。字典本身提供了 O(1) 的指针查找。

如果您不想使用 RTL 类，答案就是：使用哈希映射与多读独占写同步对象。

编辑：刚刚意识到你的对确实代表了内存范围，所以哈希映射不起作用。在这种情况下，您可以使用排序列表（按内存地址排序），然后使用二分搜索来快速找到匹配范围。这使得查找时间复杂度为 O(log n) 而不是 O(1)。