TreeSet：有效地小于一个值的元素数量

Question

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

我可以使用

子集()
headSet()
tailSet()

方法，但它们真的很慢（我只需要计数，而不是数字本身）。有办法吗？

谢谢。

编辑：

我找到了一个可以让事情变得更快的解决方法！我正在使用 BitSet 和它的 cardinality() 方法。我首先创建一个 BitSet，对于添加到 TreeSet 的每个元素，我在 BitSet 中设置相应的索引。现在，要计算小于 X 的元素数量，我使用：

bitset.get(0, X+1).基数()

这比 treeset.subSet(0, true, X, true).size().

快得多

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

Answer 1

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);

    }

}

Answer 2

'really fast' 需要多快？你大概有多少元素？

subSet()/headSet()/tailSet() 是 O(1) 因为它们 return 原始树集的视图，但是如果你 size() 你的 subSet() 你仍然在迭代所有原始元素，因此 O(N).

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

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

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

注意编辑

随着进一步的探索和测试，我无法证实这一说法 "if you size() your subSet() you are still iterating over all the original elements"。我错了。 parallelstream().count() 在这台 4 核机器上比 subSet().size()

慢 ~30%

Answer 3

如果不更新数据结构，只需要在一个hashmap中保持元素个数小于X即可！

如果您不经常更新，请保留一个排序的数字链表。在 O(1) 中的列表 insert/remove、add/remove 并更新哈希图 (O(n))。

您可以通过使用（排序的）二叉树来获取 O(Log(n)) 和更新 O(Log(n))。在树的每个元素中，还保留其后代的数量。现在要获得 # items < than y，您可以在二叉树中找到它，而且只要您向右而不是向左移动，就会对元素的数量求和。在更新时，您还需要更新新元素的祖先。

顺便说一句，如果您愿意接受大概的答案，也可以有更快的方法。

Answer 4

由于到目前为止所有答案都指向不同于 Java 的 TreeSet 的数据结构，我建议使用 Fenwick 树，它的更新和查询复杂度为 O(log(N))；请参阅 link 了解 Java 实施。

TreeSet：有效地小于一个值的元素数量

TreeSet: number of elements less than a value efficiently

java

count

subset

treeset