Limite un ListIterator a los primeros N elementos (optimizado)

Question

¿Cuál es una forma simple y rápida de obtener un iterador que devuelve como máximo N elementos desde el inicio de una List ?

Las versiones más simples que podría encontrar son:

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

Lamentablemente, ambas versiones crean una List temporal que afecta significativamente el rendimiento, ya que estoy llamando a este método millones de veces en un circuito cerrado.

¿Hay otras funciones de biblioteca que podría usar para esto?

---

Nota: No puedo evitar la iteración sobre la lista, ya que la paso a un método que toma un iterador como argumento y no puedo modificar esa clase.

Answer 1

Parece como si feature se agregará a guava, actualmente (a partir de r06) en beta:

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

Answer 2

Ya sabes que es una lista, por lo que solo puedes llamar al método List.subList (int fromIndex, int toIndex) . Según la especificación, la lista secundaria está respaldada por la lista original, por lo que en realidad no está creando una List completa, simplemente algún tipo de objeto proxy.

Answer 3

Este es un lugar donde un Decorator funciona muy bien: tu decorador mantiene un conteo, el cual se incrementa en next () , y es usado por control hasNext () .

Ejemplo (intencionalmente incompleto):

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

Por qué no simplemente

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

No estoy seguro de por qué le importa la creación de esa lista temporal. No hace nada que yo consideraría caro. De hecho, crear esta lista es mucho más barato que iterar sobre ella, lo que supongo que sí.

Answer 5

El método ArrayList.sublist (int, int) no crea una copia de la lista original. En su lugar, devuelve una instancia de SubList que envuelve el ArrayList original. El iterador devuelto por la lista secundaria derivada de Array tampoco hace una copia.

Por lo tanto, mi consejo es que intentes usar ArrayList como tu tipo de lista base y el método sublist . Si eso no es lo suficientemente rápido, implemente su propia variante de ArrayList que implementa un método limitedLengthIterator . Por ejemplo, debería poder deshacerse del código que verifica las modificaciones simultáneas.

Answer 6

Si le preocupa el rendimiento, no use un iterador, use un índice en una matriz. Esto dará mucho mejor rendimiento. Obtener los primeros N elementos de una matriz es trivial.

Answer 7

Esta versión resulta ser más rápida que cualquiera de los otros ejemplos:

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

Si la lista temporal debe crearse de todos modos, un ArrayList es más rápido que las listas decoradas que devuelven los otros métodos de la biblioteca.

Supongo que ArrayList está recibiendo un tratamiento especial dentro de la VM.

Tal vez esto sería ineficiente para listas muy largas, pero mis listas son cortas (casi siempre menos de 50 elementos).