代码之家 › 专栏 › 技术社区 › Daddy Warbox

数据结构:我应该在这些条件下使用哪一个?

multiway-tree data-structures sorting performance java

6

Daddy Warbox · 技术社区 · 15 年前

这不应该是一个困难的问题,但在我继续之前,我只希望有人能把它弹开。我只需要根据这些预期活动决定要使用的数据结构:

顺便说一下,这是在Java中。

我的最佳猜测是,我将滚动一些自定义链接哈希集(按排序顺序排列链接),或者可能只使用树集。但我还不完全确定。建议?

编辑: 我想因为任意删除/恢复,我应该坚持使用树集,对吗?

实际上,不一定。六羟甲基三聚氰胺六甲醚。。。

2 回复 | 直到 11 年前

1

3

Steve314 15 年前

理论上,我认为正确的数据结构是一个多路径树——最好是像B+树这样的树。传统上,这是一种基于磁盘的数据结构,但由于高速缓存和虚拟内存层的存在,现代主内存具有许多相似的特性。

按照顺序,B+树的迭代非常有效,因为(1)您只迭代叶节点的链接列表-不需要分支节点,以及(2)您得到了非常好的位置。

查找、删除和插入任意元素与任何平衡树一样是对数(n),尽管有不同的常量因子。

在树中使用的方法主要是选择一种算法,该算法在对块(叶节点)的链接列表进行操作时具有良好的性能,最小化使用叶节点的需要-快速排序或合并排序的变体看起来像是可能的候选者。在分支节点中对项目进行排序后,只需通过叶节点将摘要信息重新混合。

但是 -实事求是地说,如果你非常确定你需要它,这只是你会做的事情。你最好用标准容器。算法/数据结构优化是最好的优化方式,但它可能还为时过早。

2

3

Roman 15 年前

如果您希望数据结构存储非唯一值,请使用Google集合中的标准LinkedHashSet或LinkedMultiset。