Limitare un ListIterator ai primi N elementi (ottimizzato)

Question

Qual è un modo semplice e veloce per ottenere un iteratore che restituisce al massimo N elementi dall'inizio di un Elenco ?

Le versioni più semplici che ho potuto trovare sono:

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

Sfortunatamente entrambe le versioni creano un Elenco temporaneo che influisce in modo significativo sulle prestazioni, come sto chiamando questo metodo milioni di volte in un ciclo stretto.

Ci sono altre funzioni di libreria che potrei usare per questo?

---

Nota: non posso evitare di scorrere l'elenco mentre lo sto passando a un metodo che utilizza un iteratore come argomento e non posso modificare quella classe.

Answer 1

Sembra che caratteristica verrà aggiunta a guava, attualmente (a partire da r06) in beta:

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

Answer 2

Sai già che è un elenco, quindi puoi semplicemente chiamare il metodo List.subList (int fromIndex, int toIndex) . Come da specifica, la lista secondaria è supportata dalla lista originale, quindi non sta davvero creando un Elenco completo, ma solo una sorta di oggetto proxy.

Answer 3

Questo è un posto dove un Decorator funziona molto bene: il tuo decoratore tiene conto, che viene incrementato di next () e utilizzato dal controllo hasNext () .

Esempio (intenzionalmente 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

Perché non semplicemente

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

Non sono sicuro del motivo per cui ti dispiace per la creazione di tale elenco temporaneo. Non fa nulla che considererei costoso. In effetti, creare questo elenco è di gran lunga più economico che ripeterlo, cosa che presumo tu faccia.

Answer 5

Il metodo ArrayList.sublist (int, int) non crea una copia dell'elenco originale. Restituisce invece un'istanza SubList che avvolge ArrayList originale. Neanche l'iteratore restituito dall'elenco secondario derivato da Array ne fa una copia.

Quindi il mio consiglio è di provare a usare ArrayList come tipo di elenco di base e metodo sublist . Se ciò non è abbastanza veloce, implementa la tua variante di ArrayList che implementa un metodo limitedLengthIterator . Ad esempio, dovresti essere in grado di sbarazzarti del codice che controlla le modifiche simultanee.

Answer 6

Se sei preoccupato per le prestazioni, non usare un Iteratore, usa un indice su un array. Ciò darà prestazioni molto migliori. Ottenere i primi N elementi di un array è banale.

Answer 7

Questa versione risulta essere più veloce di qualsiasi altro esempio:

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

Se è necessario creare comunque l'elenco temporaneo, un ArrayList è più veloce degli elenchi decorati restituiti dagli altri metodi della libreria.

La mia ipotesi è che ArrayList stia ricevendo un trattamento speciale all'interno della VM.

Forse questo sarebbe inefficiente per elenchi molto lunghi, ma i miei elenchi sono brevi (quasi sempre meno di 50 elementi.)