Limitar um ListIterator para os primeiros elementos de N (optimizado)

Question

O que é uma maneira simples e rápida de obter um iterador que retorna no máximo N elementos desde o início de um List?

As versões mais simples que eu poderia vir para cima com são:

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

Infelizmente ambas as versões criar um List temporária que afeta significativamente o desempenho como eu estou chamando este método milhões de vezes em um loop apertado.

Existem outras funções de biblioteca que eu poderia usar para isso?

---

Nota:. Não posso evitar a iteração sobre a lista como eu estou passando-a para um método que leva um iterador como seu argumento e eu não posso modificar essa classe

Answer 1

Parece como se o apresentam será adicionado à goiaba, actualmente (a partir de R06) em beta:

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

Answer 2

Você já sabe que é uma lista, assim você pode simplesmente chamar o método List.subList(int fromIndex, int toIndex). De acordo com a especificação, o subList é apoiado pela lista original, por isso não é realmente a criação de um List soprado completo, apenas algum tipo de objeto proxy.

Answer 3

Este é um lugar onde um Decorator funciona muito bem: o seu decorador mantém uma contagem, que é incrementado por next(), e utilizado por hasNext() controle.

Exemplo (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 4

Por que não simplesmente

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

Eu não sou certo porque você mente sobre a criação dessa lista temporária. Ele não faz nada que eu considero caro. Na verdade, criando esta lista é de longe mais barato do que a iteração sobre isso, que eu suponho que você faz.

Answer 5

O método ArrayList.sublist(int,int) não cria uma cópia da lista original. Em vez disso, retorna uma instância subList que envolve o ArrayList originais. O iterador retornado pela sub-lista derivado de matriz não faz um copiar qualquer um.

Portanto, meu conselho é tentar usar ArrayList como o tipo de lista de base e o método sublist. Se isso não for rápido o suficiente, implementar sua própria variante do ArrayList que implementa um método limitedLengthIterator. Por exemplo, você deve ser capaz de se livrar do código que verifica a existência de modificações concorrentes.

Answer 6

Se você está preocupado com o desempenho, não use um Iterator, use um índice em um array. Isto vai dar um desempenho muito melhor. Conseguir os primeiros N elementos de uma matriz é trivial.

Answer 7

Esta versão acaba por ser mais rápido do que qualquer um dos outros exemplos:

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 uma lista temporária tem de ser criado de qualquer maneira, uma ArrayList é mais rápido do que as listas decorados devolvidos pelos outros métodos de biblioteca.

Meu palpite é que ArrayList está recebendo algum tratamento especial dentro da VM.

Talvez isso seria ineficiente para listas muito longas, mas as minhas listas são curtas (quase sempre menos de 50 elementos.)