代码之家 › 专栏 › 技术社区 › finnw

将ListIterator限制为前n个元素(优化)

guava iterator collections java

finnw · 技术社区 · 16 年前

获取迭代器的简单快速方法是什么?迭代器从一开始最多返回n个元素 List ?

我能想到的最简单的版本是:

第1类:

import com.google.common.collect.Iterators;

// ...

public static <E> Iterator<E> lengthLimitedIterator(Iterable<E> source, int maxLen) {
    return Iterators.partition(source.iterator(), maxLen).next().iterator();
}

第2类:

public static <E> Iterator<E> lengthLimitedIterator(List<E> source, int maxLen) {
    return source.subList(0, Math.min(source.size(), maxLen)).iterator();
}

不幸的是,两个版本都创建了一个临时的 列表 当我在一个紧密的循环中无数次调用这个方法时,它会显著地影响性能。

我可以使用其他库函数吗?

注意:我不能避免遍历列表,因为我将它传递给一个以迭代器为参数的方法,并且我不能修改该类。

7 回复 | 直到 15 年前

Werner Lehmann 15 年前

似乎是 feature 将添加到guava,目前(截至r06)在beta:

public static <T> Iterator<T> limit(Iterator<T> iterator, int limitSize)

RichN 16 年前

你已经知道这是一个列表了,所以你可以打电话给 List.subList(int fromIndex, int toIndex) 方法。按照规范,子列表是由原始列表支持的,因此它并不是真正创建一个完整的列表 List ,只是某种代理对象。

kdgregory 16 年前

这里是一个 Decorator 工作得很好:您的装饰器保留一个计数,该计数的增量为 next() ,并由控件使用 hasNext() .

示例(故意不完整):

public class LengthLimitedIterator<T>
implements Iterator<T>
{
    private Iterator<T> _wrapped;
    private int _length;
    private int _count;

    public LengthLimitedIterator(Iterator<T> wrapped, int length)
    {
        _wrapped = wrapped;
        _length = length;
    }


    public boolean hasNext()
    {
        if (_count < _length)
            return _wrapped.hasNext();
        return false;
    }

    public T next()
    {
        // FIXME - add exception if count >= length
        _count++;
        return _wrapped.next();
    }

meriton 16 年前

为什么不简单

list.subList(0, 42).iterator();

我不知道你为什么介意创建这个临时列表。它不会做任何我认为昂贵的事情。事实上,创建这个列表要比遍历它便宜得多,我假设您这样做了。

Stephen C 16 年前

这个 ArrayList.sublist(int,int) 方法不创建原始列表的副本。相反,它返回包装原始数组列表的子列表实例。从数组派生的子列表返回的迭代器也不进行复制。

所以我的建议是尝试使用 ArrayList 作为基本列表,键入 sublist 方法。如果速度不够快,请实现您自己的变量 数组列表 实现了一个 limitedLengthIterator 方法。例如,您应该能够去掉检查并发修改的代码。

Peter Lawrey 16 年前

如果您关心性能,请不要使用迭代器,在数组上使用索引。这将提供更好的性能。获取数组的前n个元素是很简单的。

finnw 16 年前

这个版本比其他任何一个例子都要快:

public static <E> Iterator<E> lengthLimitedIterator(List<E> source, int maxLen) {
    maxLen = Math.min(maxLen, source.size());
    ArrayList<E> tempList = new ArrayList<E>(maxLen);
    for (int i = 0; i < maxLen; ++ i) {
       tempList.add(source.get(i));
    }
    return tempList.iterator();
}

如果仍然必须创建临时列表,则 ArrayList 比其他库方法返回的修饰列表快。

我猜是这样的 数组列表 正在接受一些特殊的治疗。

对于很长的列表,这可能效率很低,但我的列表很短(几乎总是少于50个元素)。