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

获取迭代器的简单而快速的方法是什么？从List开始返回至多N个元素？将ListIterator限制为前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其显著影响性能我在紧密的循环中调用这个方法数百万次。

是否有任何其他库函数可用于此？

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

来源

2009-10-24 finnw

看起来好像feature将处于测试阶段被添加到番石榴，目前（如R06的）：

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

来源

2010-08-05 01:29:10

除了'Iterators'，请注意['Iterables'也有'limit（）'方法]（http：//docs.guava- libraries.googlecode.com/git/javadoc/com/google/common/collect/Iterables.html#limit(java.lang.Iterable,%20int））。所以如果你有'List'，最简单的做'Iterables.limit（aList，3）'。 – Jonik 2014-07-08 07:52:43

这是一个地方，其中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(); 
    }

来源

2009-10-24 18:59:17 kdgregory

为什么不干脆

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

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

来源

2009-10-24 19:14:20 meriton

的接收方法需要一个迭代器和不幸的是我不能改变的。你的代码和我的第二个例子是一样的，只是它不检查列表是否小于最大长度（在这种情况下subList（）会抛出一个异常。） – finnw 2009-10-25 12:09:24

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

来源

2009-10-24 19:16:05 RichN

这个问题是你必须确定列表中有足够的可用项目，否则您将得到一个'IndexOutOfBoundsException'。我不知道这个限制是否也存在于其他提出的解决方案中，但是最好有一个内置选项来遍历_at most_n个元素。 – Itai 2016-10-09 12:19:11

这个版本原来是比任何其他示例的速度更快：

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正在虚拟机中得到一些特殊待遇。

也许这将是低效的很长的名单，但我的名单是短（几乎总是少于50元。）

来源

2009-10-25 12:17:20 finnw

顺便说一句，我对你的“这比这个更快”的结论感到警惕，因为Java中的微基准非常非常容易出错。有一百种方法来获得误导性的结果。我真的认为你应该尝试坚持干净的subList（）。iterator（）解决方案。 – 2009-11-04 01:33:54

@Kevin，我在我使用它的真实应用程序中进行了测量。在一般情况下，我并没有声称它速度更快。 – finnw 2009-11-04 11:07:39

如果你担心性能，请不要使用迭代器，使用索引上数组。这会带来更好的性能。获取数组的前N个元素是微不足道的。

来源

2009-10-25 14:01:22

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

所以我的建议是尝试使用ArrayList作为您的基准列表类型和sublist方法。如果速度不够快，请实施您自己的ArrayList变体，该变体实施limitedLengthIterator方法。例如，你应该能够摆脱检查并发修改的代码。

来源

2009-10-25 14:27:57

但包装实际上比原始ArrayList – finnw 2009-10-25 16:28:46

@finnw慢 - 但它应该比复制列表快。 – 2011-10-26 23:31:49

取决于迭代次数。 – finnw 2011-10-27 11:54:39

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

回答

相关问题