将ListIterator限制为前N个元素（已优化）

StackOverflow https://stackoverflow.com/questions/1618759

题

从 List 的开头获取最多返回N个元素的迭代器有什么简单快捷的方法？

我能提出的最简单的版本是：

＃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();
}

不幸的是，两个版本都会创建一个临时 List ，这会严重影响性能，因为我在紧密循环中调用了这个方法数百万次。

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

注意：我无法避免遍历列表，因为我将它传递给一个以迭代器作为参数的方法，我无法修改该类。

有帮助吗？

解决方案

好像是功能将被添加到番石榴，目前（自r06起）测试版：

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

其他提示

您已经知道它是一个列表，因此您只需调用 List.subList（int fromIndex，int toIndex）方法即可。根据规范，subList由原始列表支持，因此它并没有真正创建一个完整的 List ，只是某种代理对象。

这是一个装饰器非常有效的地方：你的装饰师会保持计数，它由 next（）递增，并由control 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();
    }

为什么不简单

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

我不确定你为什么要介意创建那个临时列表。它没有做任何我认为昂贵的事情。事实上，创建这个列表远比迭代它便宜，我假设你这样做。

ArrayList.sublist（int，int）方法不会创建原始列表的副本。相反，它返回一个包装原始ArrayList的SubList实例。从Array派生的子列表返回的迭代器也不会复制。

所以我的建议是尝试使用 ArrayList 作为基本列表类型和子列表方法。如果这还不够快，请实现自己的 ArrayList 变体，该变体实现 restrictedLengthIterator 方法。例如，您应该能够删除检查并发修改的代码。

如果您担心性能，请不要使用Iterator，请在阵列上使用索引。这将提供更好的性能。获取数组的前N个元素是微不足道的。

此版本比其他任何示例都快：

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 比其他库方法返回的修饰列表更快。

我的猜测是 ArrayList 在VM中得到一些特殊处理。

对于很长的列表，这可能效率不高，但我的列表很短（几乎总是少于50个元素。）

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top