1

在java中，我从一个总是要排序的列表中创建一个SortedSet（但只有ArrayList类型）。我认为一一添加它们的性能会很差（以 AVL 树为例），因为它必须对树进行大量重新排序。

我的问题是，我应该如何创建这个集合？以某种方式尽可能快地构建平衡树？

我计划使用的具体实现是来自http://fastutil.dsi.unimi.it/docs/it/unimi/dsi/fastutil/ints/IntSortedSet.html的 IntRBTreeSet 或 IntAVLTreeSet

在写完这篇文章之后，我认为糟糕的性能无论如何不会对我影响太大（数据量太少），但我仍然对在一般情况下如何完成它感兴趣。

4

5 回答 5

3

具有树实现的集合将列表中的中间元素放在顶部。所以算法如下：

  1. 找到 List 的中间元素
  2. 将其插入集合
  3. 对中间元素左侧和右侧的两个子列表重复
于 2009-02-23T04:29:55.437 回答
2

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

于 2009-02-23T04:13:49.297 回答
1

在所有关于使用 Set 的讨论中，我突然想到这个问题可能会被重新陈述。为什么要使用 Set 呢？如果您只是想检查成员资格，并且您的源列表已排序，那么对该对象进行二进制搜索 - 这将比您可以想象的任何 n-tree 一样快（并且可能更快），而且并不难代码。

So, envision a OrderedListSet interface that just wraps the underling List object. As long as the comparator used to order the list is also used for the binary search, this should be pretty straight-forward.

All Set operations will start with a getIndex(Object ob) call, then the appropriate action is taken on the List.

于 2009-02-26T06:10:00.633 回答
0

在元素到来时插入元素的简单方法是否存在性能问题？

如果不是，请不要优化。

于 2009-02-23T07:47:29.643 回答
0

内置的 TreeSet ( http://java.sun.com/j2se/1.4.2/docs/api/java/util/TreeSet.html ) 类使用红黑树作为它的支持树（并且，已经注意到，红黑树的插入速度非常快）。这是关于红黑树的好信息（在插入大部分已经排序的数据时，它们没有典型的二叉树实现的问题）。

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

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

于 2009-02-24T05:21:44.587 回答