从有序列表树构造

在Java中，即时通讯创建SortedSet从一个总是要排序（但只是ArrayList类型）的列表。我认为一个接一个地添加它们会有很差的性能（例如在AVL树的情况下），因为它将不得不对树进行重新排序。从有序列表树构造

我的问题是，如何应该我要创建这个集？以一种尽可能快的方式建立一棵平衡的树？

具体实施我打算用要么IntRBTreeSet或IntAVLTreeSet从http://fastutil.dsi.unimi.it/docs/it/unimi/dsi/fastutil/ints/IntSortedSet.html

写作这件事之后，我认为表现不佳不会影响我太多反正（太小的数据量），但我还在对如何在一般情况下完成这项工作感兴趣。

来源

2009-02-23 gcrain

具有树实现的集合将从顶部的列表中获取中间元素。因此，算法将是如下：

找到列表的中间元素
将其插入设置
重复两个子列表的左侧和中间元素的右边

来源

2009-02-23 04:29:55

我认为这是一个不错的选择。仍然可以快速访问（数组）列表来插入它们，列表元素将以何种方式排序（不是很高）。 – gcrain 2009-02-26 04:30:14

红黑树对于一般情况来说是个不错的选择，它们插入速度非常快。请参阅Chris Okasaki's paper以获得优雅而快速的实施。 Functional Java库有一个通用的Set类，它由根据本文实现的红黑树支持。

来源

2009-02-23 04:13:49 Apocalisp

您是否因简单的插入元素而出现性能问题？

如果没有，请不要优化。

来源

2009-02-23 07:47:29 starblue

有效点。但为了讨论的缘故，我们假设他确实有性能问题。 – 2009-02-24 02:01:45

在TreeSet（http://java.sun.com/j2se/1.4.2/docs/api/java/util/TreeSet.html）类中构建的类使用红黑树作为其支持树（并且，已经注意到，红黑树对于插入来说相当快）。这里是红黑树上的good info（当插入大部分已经订购的数据时，它们没有典型二叉树实现的问题）。

如果您正在处理大量数据集（足够大以便需要基于磁盘的备份或重要的分页文件交换），那么B +树就是一个非常好的选择（请参阅JDBM以了解基于Java的自平衡版本B +树 - 它没有实现Set，但如果需要可以这样使用）。

根据您的应用程序实际使用此数据的方式，您可能需要考虑GlazedLists库，并使您的列表“生效”。如果你所做的只是静态分析，那么这可能是矫枉过正的，但它是处理基于列表的数据的绝佳方式。绝对值得一读。

来源

2009-02-24 05:21:44

随着关于使用Set的所有讨论，在我看来，问题可能会被重新阐述。为什么要使用Set？如果您只想检查成员资格，并且对源列表进行排序，那么对该对象执行二进制搜索 - 与您可以设想的任何n-tree相比，该搜索速度会更快（也可能更快），并且这并不难码。

所以，设想一个OrderedListSet接口，它只是包装下属的List对象。只要用于排列列表的比较器也用于二分搜索，这应该是非常直接的。

所有Set操作将以getIndex（Object ob）调用开始，然后在列表上执行相应的操作。

来源

2009-02-26 06:10:00

问题是列表被排序，但它不在保证顺序的数据结构中。所以我可以假设它的顺序，但不能绝对确保我的代码将工作 – gcrain 2009-02-26 22:32:17

从有序列表树构造

回答

相关问题