Dad*_*box 6 java sorting performance data-structures multiway-tree
这不应该是一个困难的问题,但我希望有人在我继续之前将其反弹.我只需根据这些预期的活动来决定使用哪种数据结构:
顺便说一下,这是Java.
我最好的猜测是,我要么滚动一些自定义链接哈希集(按排序顺序排列链接),要么只使用树集.但我还不完全确定.建议？
编辑:我想因为任意删除/恢复,我应该坚持使用树集,对吧？
实际上,不一定.嗯...
小智 3
理论上，我认为正确的数据结构是多路树 - 最好是 B+ 树之类的东西。传统上这是一种基于磁盘的数据结构，但现代主内存由于缓存和虚拟内存层而具有许多相似的特征。
B+ 树的有序迭代非常高效，因为 (1) 您只需迭代叶节点的链表 - 不需要分支节点，并且 (2) 您可以获得非常好的局部性。
与任何平衡树一样，查找、删除和插入任意元素都是 log(n)，尽管常数因子不同。
在树中进行排序主要是选择一种算法，该算法在对块链表（叶节点）进行操作时提供良好的性能，最大限度地减少使用叶节点的需要 - 快速排序或合并排序的变体似乎是可能的候选者。一旦项目在分支节点中排序，只需通过叶节点将摘要信息传播回来。
但是- 实际上，只有当您非常确定需要它时，您才会这样做。您最好使用一些标准容器。算法/数据结构优化是最好的优化，但仍然为时过早。