Java集合 - 前n个和后n个元素

Question

我有一个非常独特的需求，我的集合只应该保存前n个和后n个元素。这些元素是可比较的，而且集合本身是有界的，这意味着在向集合添加条目时进行评估。

例如，当以下一组值被插入到“前10个和后10个”集合中：

5、15、10、1、12、8、11、2、16、14、9、3、20、7

集合仅应保留以下内容：

20、16、15、14、12、7、5、3、2、1

我考虑维护两个n/2元素的SortedSet，然后在最后合并它们，但这种方法不够简洁，并需要在消费结果之前执行合并步骤。

希望有人能提供更好的解决方案。

- Anand Nadar

---

你可能只需要一个Treeset - subset方法可以让你轻松访问前/后5个元素，lower/higher方法用于测试包含关系。+ pollFirst/Last可删除正确的项。但你仍然需要编写代码。 - assylias

我确实阅读了TreeSet API（subset和tailset），但由于大多数操作都是基于元素而不是索引，所以我无法弄清楚如何实现。 - Anand Nadar

TreeSet是排序的，所以如果大小为10，则可以知道subset(0,4)是前5个，而subset(5,9)是后5个（或者反之亦然，我不确定）。 - assylias

assylias，也许我的问题不够清晰。将插入到集合中的条目数量很大（~100,000），但在任何给定时间，我只想保留前N个或后N个。其他条目将被丢弃。 - Anand Nadar

我的想法是使用TreeSet，在添加元素之前检查大小，如果大小小于等于N，则插入并且什么也不做。否则，插入然后删除中间元素。由于自然排序，需要丢弃的是中间元素。但是如何删除中间元素呢？我可能需要迭代；这似乎是唯一低效的方法。 - Anand Nadar

你说得对，这并不像我想象的那么简单。使用两个集合或许并不是一个坏主意... - assylias

Answer 1

1. 如果您想要排序和唯一性，请使用java.util.Collection中的TreeSet。您的数据将自动按照自然顺序排序，并且唯一性将得到保证。

2. 使用Collections.reverse()根据您的需要反转集合...

- Kumar Vivek Mitra

---

我有一个TreeSet，并且元素是基于我的比较实现进行排序的，但是这个集合需要限制到n个元素并且不包含不必要的元素。主要是为了优化内存，因为插入的元素数量将会很高。 - Anand Nadar

在插入数据时，要用逻辑来处理它，例如 if (mtree.size()>n){ // 已达到限制} else { mtree.add(value) }。 - Kumar Vivek Mitra

通过这种方式，我能够实现“前N个”或“后N个”，但无法处理“前N个和后N个”这种情况。 - Anand Nadar

我还没有清晰的想法...你能否请举个例子...这样我就可以为您轻松编写代码了。 - Kumar Vivek Mitra

Vivek，我想使用TreeSet来实现这个功能；前N个 - 从尾部丢弃。后N个 - 从头部丢弃。前N和后N个 - 从中间丢弃。现在的问题仅仅是如何从TreeSet的中间删除元素。例如，在一个前10个和后10个的场景中，当添加第11个元素时，第6个元素必须被删除。 - Anand Nadar

Answer 2

因为我喜欢像这样的星期天下午写集合,

import static org.junit.Assert.assertEquals;
import java.util.Arrays;
import org.junit.Test;

public class TopBottom {

    public int[] top;
    public int[] bottom;

    public TopBottom(int size) {
        top = new int[size];
        Arrays.fill(top, Integer.MIN_VALUE);
        bottom = new int[size];
        Arrays.fill(bottom, Integer.MAX_VALUE);
    }

    public void add(int element) {
        int n = Arrays.binarySearch(top, element);
        if (n < -1) {
            System.arraycopy(top, 1, top, 0, -2 - n);
            top[-2 - n] = element;
        }
        int m = Arrays.binarySearch(bottom, element);
        if (m < 0 && bottom.length >= -m) {
            System.arraycopy(bottom, -1 - m, bottom, 0 - m, bottom.length + m);
            bottom[-1 - m] = element;
        }
    }

    public void add(int... elements) {
        for (int each: elements) {
            add(each);
        }
    }

    public String toString() {
        StringBuilder buf = new StringBuilder();
        buf.append('[');
        for (int each: bottom) {
            buf.append(each);
            buf.append(", ");
        }
        for (int each: top) {
            buf.append(each);
            buf.append(", ");
        }
        buf.setLength(buf.length() - 2);
        buf.append("]");
        return buf.toString();
    }

    public static class Examples {

        @Test
        public void shouldHoldOnlyTopFiveAndBottomFive() {
            TopBottom tp = new TopBottom(5);
            tp.add(5, 15, 10, 1, 12, 8, 11, 2, 16, 14, 9, 3, 20, 7);
            assertEquals("[1, 2, 3, 5, 7, 12, 14, 15, 16, 20]", tp.toString());
        }

    }

}

它使用Arrays#binarySearch方法，该方法（除了查找现有元素）还返回已排序列表中插入点，如果缺少元素。插入点以(-1-index)的形式返回，因此检查n和m是否为负数，以及后面的表达式-1-n来获取插入点或前后点。

- akuhn

---

我用了一种略有不同的方法来解决这个问题；无法确定哪种解决方案更快。我的实现方式是，对于每次插入，将TreeSet元素转换为数组；然后查找位于位置(n/2)的元素，并从TreeSet中删除它。本质上是从TreeSet中删除中间元素。由于我们处理的是树中有限(n)数量的元素，因此性能应该是可以接受的。 - Anand Nadar