TreeSet：高效地查找小于某个值的元素数量

Question

我需要一种快速计算TreeSet（整数）中小于X元素数量的方法。

我可以使用subSet()、headSet()和tailSet()方法，但它们非常缓慢（我只需要计数，而不是数字本身）。 有没有办法？

谢谢。

编辑：

我找到了一个解决方法，使事情更快！ 我正在使用BitSet及其cardinality()方法。 首先创建一个BitSet，并为添加到TreeSet中的每个元素设置相应的位。 现在，要计算小于X的元素数量，我使用：

bitset.get(0, X + 1).cardinality()

这比treeset.subSet(0, true, X, true).size()快得多。

有人知道为什么吗？ 我假设BitSet.cardinality()不使用线性搜索。

- mnmp

---

你可以尝试使用 Guava 的 TreeMultiset，它支持在 O(log n) 时间复杂度内执行 headMultiset(element).size() 操作，而非 O(n)。虽然它与 TreeSet 不完全相同，但是 headMultiset(element).elementSet().size() 也可以在 O(log n) 时间复杂度内完成。 - Louis Wasserman

为什么需要TreeSet？你是否经常更新数据结构？如果不更新数据结构，只需在哈希映射中保持元素数量小于X！如果您不经常更新它，请保持数字的排序链表。在插入/删除时，在O（1）中从列表中添加/删除，并更新哈希映射（O（n））。 - Masood_mj

感谢您的评论@Masood_mj。问题在于X不是一个特定的值，每次调用cardinality()函数时都会发生变化。因此，如果我想使用哈希映射，那么每次将Y添加或删除到哈希映射中时，我都必须更新所有键> Y的项（+1或-1全部）。我有什么遗漏吗？ - mnmp

我认为Java没有一种树可以在添加节点时让你知道节点在树中的路径。实现二叉树不应该很难（在网上搜索示例代码）。 - Masood_mj

谢谢，你可能知道 BitSet 是如何工作的吗？我只是好奇。也许它正在做你告诉我的相同的事情。 - mnmp

Answer 1

目前所有的答案都指向与Java中的TreeSet不同的数据结构，我建议使用Fenwick树，它在更新和查询时具有O(log(N))的时间复杂度；请参见链接以获取Java实现。

- P Marecki

Answer 2

'真正快速'需要有多快？大约有多少元素？

subSet()/headSet()/tailSet() 是 O(1) 的，因为它们返回原始 TreeSet 的视图，但如果您对 subSet() 进行 size() 操作，则仍会迭代所有原始元素，因此是O(N)。

您是否使用Java 8？这将大致相同，但您可以并行化成本。

Set<Integer> set = new TreeSet<>();
// .. add things to set

long count = set.parallelstream().filter(e -> e < x).count();

---

NB编辑

经过进一步的探索和测试，我无法证实“如果你对subSet()进行size()操作，仍然会遍历所有原始元素”的说法。我错了。parallelstream().count()在这台4核机器上比subSet().size()慢了约30％。

- KarlM

---

谢谢！我有十万个元素！我不知道count()，我以为使用subSet是问题所在。 - mnmp

你对以下说法的支持是什么：“subviewcount()方法（或者我猜你指的是size()方法）会遍历整个原始集合？” - user207421

谢谢询问。我看到了像https://dev59.com/smUo5IYBdhLWcg3w3ymi和https://dev59.com/GWYq5IYBdhLWcg3wridD这样的答案，但当我进行调查时，我无法根据源代码证实这些说法 - 版本可能已经改变等等。事实上，编写自己的测试后，size()似乎并不会因为N变化x100而有太大变化。我会继续寻找 - 可能会撤回答案 - @mnmp你找到任何改进了吗？ - KarlM

这里对于size()又是O(N)的另一个解释：https://dev59.com/rWUq5IYBdhLWcg3wJNHg - KarlM

Answer 3

如果您不需要更新数据结构，只需在哈希映射中保留少于X个元素的数量即可！

如果您不经常更新它，请保留一个有序链表。在插入/删除时，在O(1)中添加/删除列表并更新哈希映射(O(n))。

通过使用(排序)二叉树，您可以获得O(Log(n))获取和O(Log(n))更新。在树的每个元素中，还要保留其后代的数量。现在，要获取小于y的#项，您可以在二叉树中找到它，但也要在向右而不是向左移动时累加元素的数量。在更新时，您还需要更新新元素的祖先。

顺便说一下，如果您愿意接受近似答案，则可能会有更快的方法。

- Masood_mj

Answer 4

package ArrayListTrial;

import java.util.Scanner;

public class countArray {

    public static void main(String[] args) {
        // TODO Auto-generated method stub

        int[] array = new int[100];
        Scanner scan = new Scanner(System.in);
        System.out.println("input the number you want to compare:");
        int in = scan.nextInt();
        int count = 0;
        System.out.println("The following is array elements:");
        for(int k=0 ; k<array.length ; k++)
        {
            array[k] = k+1;
            System.out.print(array[k] + " ");
            if(array[k] > in)
            {
                count++;
            }
        }
        System.out.printf("\nThere are %d numbers in the array bigger than %d.\n" , count , in);

    }

}

- michael-bern

---

也许这是针对另一个问题的答案？ - KarlM

这不是任何问题的答案。被搜索的数组中充满了零。因此，任何特定值的计数都是预先已知的：无需搜索。@KarlM - user207421