將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個元素（已優化）

回答

相關問題