Begrenzen einen ListIterator auf die ersten N Elemente (optimiert)

Question

Was ist eine einfache und schnelle Möglichkeit, einen Iterator zu erhalten, die von Anfang an einem List höchstens N Elementen zurückzugibt?

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 schaffen beide Versionen eine temporäre List, die die Leistung erheblich beeinflusst, wie ich in einer engen Schleife dieser Methode Millionen Mal nenne.

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

---

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

Answer 1

Es scheint, als ob die Funktion Guave hinzugefügt werden, die derzeit (Stand R06) in der beta:

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

Answer 2

Sie wissen bereits, es ist eine Liste, so dass Sie nur die List.subList(int fromIndex, int toIndex) Methode aufrufen. Gemäß der Beschreibung wird der subList von der ursprünglichen Liste gesichert, so ist es nicht wirklich eine vollständige geblasenen List, nur eine Art von Proxy-Objekt zu schaffen.

Answer 3

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 durch Steuer hasNext() verwendet.

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 4

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 ich teuer betrachten würde. In der Tat ist diese Liste zu schaffen bei weitem billiger als über sie iterieren, die ich nehme an, Sie tun.

Answer 5

Die ArrayList.sublist(int,int) Methode erstellen keine Kopie der ursprünglichen Liste. Stattdessen gibt es eine Unterliste Instanz, die die ursprüngliche Arraylist wickelt. Der Iterator der sublist abgeleitet von Array zurückgegeben keine Kopie entweder machen.

Also mein Rat ist mit ArrayList als Basistyp und der sublist Methode zu versuchen. Wenn das nicht schnell genug ist, eine eigene Variante von ArrayList implementieren, die eine limitedLengthIterator Methode implementiert. Zum Beispiel sollten Sie in der Lage sein, den Code, um loszuwerden, die für die gleichzeitigen Änderungen überprüft.

Answer 6

Wenn Sie über die Leistung betrifft, nicht einen Iterator verwenden, einen Index für ein Array verwenden. Dies gibt viel bessere Leistung. Erhalten der ersten N Elemente eines Arrays ist trivial.

Answer 7

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 Bibliothek Methoden zurückgegeben.

Meine Vermutung ist, dass ArrayList ist eine besondere Behandlung innerhalb der VM zu bekommen.

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