有限的SortedSet

Question

有限的SortedSet

7

我正在寻找一个有限元素数量的SortedSet实现。因此，如果添加的元素超过指定的最大值，则比较器决定是否添加该项并从集合中删除最后一项。

SortedSet<Integer> t1 = new LimitedSet<Integer>(3);
t1.add(5);
t1.add(3);
t1.add(1);
// [1,3,5]
t1.add(2);
// [1,2,3]
t1.add(9);
// [1,2,3]
t1.add(0);
// [0,1,2]

有没有一种优雅的方式在标准 API 中实现这个功能？

我已经编写了一个 JUnit 测试来检查实现：

@Test
public void testLimitedSortedSet() {
final LimitedSortedSet<Integer> t1 = new LimitedSortedSet<Integer>(3);
t1.add(5);
t1.add(3);
t1.add(1);
System.out.println(t1);
// [1,3,5]
t1.add(2);
System.out.println(t1);
// [1,2,3]
t1.add(9);
System.out.println(t1);
// [1,2,3]
t1.add(0);
System.out.println(t1);
// [0,1,2]
Assert.assertTrue(3 == t1.size());
Assert.assertEquals(Integer.valueOf(0), t1.first());
}

- Andreas

3个回答

2

没有现有的Java库可以做到这一点。

但是，您可以使用组合构建下面这样的库。我相信这将很容易实现。

public class LimitedSet implements SortedSet {

    private TreeSet treeSet = new TreeSet();

    public boolean add(E e) {
        boolean result = treeSet.add(e);
        if(treeSet.size() >= expectedSize) {
            // remove the one you like ;)
        }
        return result;
    }

    // all other methods delegate to the "treeSet"

}

更新在阅读您的评论后，

由于您需要始终删除最后一个元素：

您可以考虑在内部维护一个堆栈
这将增加内存复杂度为O(n)
但是仅需O(1)即可检索最后一个元素......就是常数时间

我相信它应该能达到预期效果。

- Kowser

我考虑过这个问题。但是我希望有一个高效的实现存在 :-). 从TreeSet中移除最后一个元素可能会很耗时，因为整个列表必须被遍历。对于Java 1.6，我可以使用NavigableSet，它有一个pollLast()方法，应该很快。 - Andreas

由于您需要始终删除最后一个元素，因此可以考虑在内部维护一个堆栈。这将增加O(n)的内存复杂度，但可以仅使用O(1)...常数时间检索最后一个元素。我相信这应该能解决问题。 - Kowser

虽然您已经选择了一个答案，但我很好奇您的想法是什么。 - Kowser

我不确定你所说的内部堆栈是什么意思。我认为TreeSet有一个双向链表来存储元素并记住第一个和最后一个元素。因此，pollLast()方法不应该遍历整个列表，因为最后一个元素是已知的。为了优化add()操作，可以进行预检查，以确定是否应该添加元素。 - Andreas

2

我认为这是典型的装饰器模式应用，类似于由Collections类公开的装饰集合：unmodifiableXXX，synchronizedXXX，singletonXXX等。我会采用Guava的ForwardingSortedSet作为基类，并编写一个类来装饰现有的SortedSet以实现您所需的功能，类似以下内容：

public final class SortedSets {

    public <T> SortedSet<T> maximumSize(
        final SortedSet<T> original, final int maximumSize){

        return new ForwardingSortedSet<T>() {

            @Override
            protected SortedSet<T> delegate() {
                return original;
            }

            @Override
            public boolean add(final T e) {
                if(original.size()<maximumSize){
                    return original.add(e);
                }else return false;
            }

            // implement other methods accordingly
        };
    }

}

- Sean Patrick Floyd

好主意！当我需要实现多个“特殊”的集合时，我会使用它。 - Andreas

你当前的代码违反了Collection#add合约，该合约明确规定当拒绝一个元素时，不能简单地返回false。最好定义一个offer方法来代替。 - DieterDP

@DieterDP 我不确定。我认为，“如果集合因为其他原因而拒绝添加特定元素而不是该元素已经存在”条款足以适用于这种情况。我肯定会避免引入一个没有被接口支持的方法。因此，也许可以编写一个LimitedSortedSet接口，它扩展SortedSet并具有此方法。但考虑到SO答案的范围，我选择不要走完整个过程。 - Sean Patrick Floyd

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Thomas · Accepted Answer

使用标准API时，您需要自己完成这项工作，即扩展排序集类之一，并将所需逻辑添加到add()和addAll()方法中。不应该太难。

顺便说一下，我并不完全理解你的例子：

t1.add(9);
// [1,2,3]

之后集合中不应该包含 [1,2,9] 吗？

编辑: 我想现在我明白了：你只想保留添加到集合中的最小的3个元素，对吧？

编辑 2: 一个示例实现（未优化）可能如下所示：

class LimitedSortedSet<E> extends TreeSet<E> {

  private int maxSize;

  LimitedSortedSet( int maxSize ) {
    this.maxSize = maxSize;
  }

  @Override
  public boolean addAll( Collection<? extends E> c ) {
    boolean added = super.addAll( c );        
    if( size() > maxSize ) {
      E firstToRemove = (E)toArray( )[maxSize];
      removeAll( tailSet( firstToRemove ) );
    }   
    return added;
  }

  @Override
  public boolean add( E o ) {    
    boolean added =  super.add( o );
    if( size() > maxSize ) {
      E firstToRemove = (E)toArray( )[maxSize];
      removeAll( tailSet( firstToRemove ) );
    }
    return added;
  }
}

请注意，tailSet()返回包括参数在内的子集（如果存在于集合中）。这意味着，如果您无法计算出下一个更高的值（不需要在集合中），则必须重新添加该元素。这在上面的代码中完成。

如果您可以计算出下一个值，例如，如果您有一组整数，则执行tailSet（lastElement + 1）将足以，您不必重新添加最后一个元素。

或者，您可以自己迭代集合并删除所有跟随要保留的最后一个元素的元素。

另一种选择，尽管可能需要更多的工作，是在插入元素之前检查大小并相应删除。

更新：正如msandiford正确指出的那样，应删除的第一个元素是索引为maxSize的元素。因此，没有必要重新添加最后一个想要的元素。

重要提示：正如DieterDP所正确指出的那样，上面的实现违反了Collection＃add（） api合同，该合同规定，如果集合拒绝添加除重复项之外的任何元素，则必须抛出异常。

在上面的示例中，首先添加了该元素，但由于大小限制或其他元素可能被删除，因此会违反合同。

要解决此问题，您可能需要更改add（）和addAll（）以在这些情况下抛出异常（或者可能在任何情况下都抛出异常，以使它们无法使用），并提供添加元素的替代方法，这些方法不会违反任何现有的api合同。

在任何情况下，上述示例应谨慎使用，因为对于不知道违规的代码使用它可能会导致不必要且难以调试的错误。