固定大小的集合,用于保存Java中的顶级(N)值

Question

我需要保持前N(<1000)个整数,同时尝试从一个大整数列表中添加值(大约一百万个大小的惰性列表).我想尝试将值添加到集合中,但是只需要保留前N个(最高值)整数.是否有任何首选数据结构用于此目的？

Answer 1

我建议使用一些排序的数据结构,例如TreeSet.在插入之前,检查集合中的项目数量,如果它达到1000,则删除最小的数字(如果它小于新添加的数字),并添加新的数字.

TreeSet<Integer> set = ...;

public void add (int n) {
    if (set.size () < 1000) {
       set.add (n);
    } else {
       Integer first = set.first();
       if (first.intValue() < n) {
          set.pollFirst();
          set.add (n);
       }
    }
}

Answer 2

Google Guava MinMaxPriorityQueue类.

您还可以使用比较器(使用orderedBy(Comparator<B> comparator)方法)使用自定义排序.

注意:此集合不是已排序的集合.

见javadoc

例:

@Test
public void test() {
    final int maxSize = 5;

    // Natural order
    final MinMaxPriorityQueue<Integer> queue = MinMaxPriorityQueue
            .maximumSize(maxSize).create();
    queue.addAll(Arrays.asList(10, 30, 60, 70, 20, 80, 90, 50, 100, 40));

    assertEquals(maxSize, queue.size());
    assertEquals(new Integer(50), Collections.max(queue));

    System.out.println(queue);
}

输出:

[10,50,40,30,20]

Answer 3

您的问题在这里得到解答： Size-limitedqueue thatholds last N elements in Java

总结一下：默认的 java sdk 中没有数据结构，但 Apache commons collections 4 有一个 CircularFifoQueue。