Begrenzen Sie einen ListIterator auf die ersten N-Elemente (optimiert)

Question

Was ist eine einfache und schnelle Möglichkeit, einen Iterator zu erhalten, der am Anfang einer List am meisten N Elemente zurückgibt?

Die einfachsten Versionen ich tun konnte, sind:

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

Leider beide Versionen eine temporäre List schaffen, die Leistung erheblich beeinträchtigt als Ich rufe diese Methode millionenfach in einer engen Schleife an.

Gibt es noch andere Bibliotheksfunktionen, die ich dafür verwenden könnte?

---

Hinweis: ich die Liste nicht vermeiden kann iterieren, wie ich es auf ein Verfahren bin vorbei, die einen Iterator als Argument und ich kann nicht diese Klasse ändern.

Answer 1

scheint, als ob die feature wird Guave hinzugefügt werden, die derzeit (Stand R06) in der Beta:

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

Answer 2

Dies ist ein Ort, an dem ein Decorator funktioniert sehr gut: Ihr Dekorateur eine Zählung hält, die von next() erhöht wird, und wird von Steuer hasNext().

Beispiel (absichtlich unvollständig):

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

Answer 3

Warum nicht einfach

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

Ich bin nicht sicher, warum Sie über die Schaffung dieser temporären Liste kümmern. Es tut nichts, was ich als teuer erachten würde. In der Tat ist das Erstellen dieser Liste bei weitem billiger als das Iterieren darüber, was ich davon ausgehe.

Answer 4

Sie wissen bereits, es ist eine Liste, so können Sie einfach die List.subList(int fromIndex, int toIndex) Methode aufrufen. Gemäß der Spezifikation wird die Unterliste von der ursprünglichen Liste unterstützt, so dass es nicht wirklich eine vollständige List erstellt, nur eine Art von Proxy-Objekt.

Answer 5

Diese Version erweist sich als schneller als alle anderen Beispiele:

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

Wenn die temporäre Liste ohnehin erstellt werden, ein ArrayList ist schneller als die eingerichteten Listen von den anderen Bibliotheksverfahren zurückgeführt.

Meine Vermutung ist, dass ArrayList eine spezielle Behandlung innerhalb der VM bekommt.

Vielleicht wäre dies für sehr lange Listen ineffizient sein, aber meine Listen sind kurz (fast immer weniger als 50 Elemente.)

Answer 6

Wenn Sie über die Leistung betrifft, nicht einen Iterator verwenden, einen Index zu verwenden, auf eine Anordnung. Dies wird zu einer viel besseren Leistung führen. Das Abrufen der ersten N Elemente eines Arrays ist trivial.

Answer 7

Die Methode ArrayList.sublist(int,int) erstellt keine Kopie der ursprünglichen Liste. Stattdessen wird eine SubList-Instanz zurückgegeben, die die ursprüngliche ArrayList umschließt. Der Iterator, der von der aus Array abgeleiteten Teilliste zurückgegeben wird, erstellt auch keine Kopie.

So ist mein Tipp zu versuchen, ArrayList als Ihre Basis-Liste Typ und die sublist Methode zu verwenden. Wenn das nicht schnell genug ist, implementieren Sie Ihre eigene Variante von ArrayList, die eine limitedLengthIterator-Methode implementiert. Zum Beispiel sollten Sie in der Lage sein, den Code zu entfernen, der nach gleichzeitigen Änderungen sucht.