Limite a ListIterator a los primeros N elementos (optimizado)

Question

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

Las versiones más simples que pudiera surgir con 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(); 
} 

Desafortunadamente ambas versiones crear un temporal List que afecta significativamente el rendimiento como Estoy llamando a este método millones de veces en un círculo cerrado.

¿Hay alguna otra función de biblioteca que pueda usar para esto?

---

Nota: No puedo evitar la iteración en la lista como yo estoy pasando a un método que toma un iterador como su argumento y no puedo modificar esa clase.

Answer 1

parece como si el feature se añadirá a la guayaba, actualmente (r06) en beta:

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

Answer 2

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

Ejemplo (intencionalmente incompleta):

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

Por qué no simplemente

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

No estoy seguro de por qué te importa acerca de la creación de esa lista temporal. No hace nada que considere costoso. De hecho, crear esta lista es mucho más barato que iterar sobre él, lo que supongo que es necesario.

Answer 4

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

Answer 5

Esta versión resulta ser más rápido 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 tiene que ser creado de todos modos, una ArrayList es más rápido que las listas decoradas devueltos por los otros métodos de biblioteca.

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

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

Answer 6

Si usted está preocupado por el rendimiento, no use un iterador, utilizar un índice en una matriz. Esto dará un rendimiento mucho mejor. Obtener los primeros N elementos de una matriz es trivial.

Answer 7

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

Así que mi consejo es intentar usar ArrayList como su 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 busca modificaciones concurrentes.