Limiter un ListIterator aux N premiers éléments (optimisé)

Question

Qu'est-ce qu'un moyen simple et rapide d'obtenir un itérateur qui renvoie au plus N éléments à partir du début d'une Liste ?

Les versions les plus simples que je pourrais trouver sont:

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

n ° 2:

public static <E> Iterator<E> lengthLimitedIterator(List<E> source, int maxLen) {
    return source.subList(0, Math.min(source.size(), maxLen)).iterator();
}

Malheureusement, les deux versions créent une liste temporaire qui affecte considérablement les performances, car j'appelle cette méthode des millions de fois dans une boucle serrée.

Existe-t-il d'autres fonctions de bibliothèque que je pourrais utiliser pour cela?

Remarque: je ne peux pas éviter de parcourir la liste car je la passe à une méthode qui prend un itérateur comme argument et je ne peux pas modifier cette classe.

Answer 1

On dirait que La fonctionnalité sera ajoutée à la goyave, actuellement (version r06) en version bêta:

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

Answer 2

Vous savez déjà que c'est une liste, vous pouvez simplement appeler la méthode List.subList (int fromIndex, int toIndex) . Conformément à la spécification, la sous-liste est protégée par la liste d'origine. Elle ne crée donc pas vraiment une liste complète, mais une sorte d'objet proxy.

Answer 3

C’est un endroit où un Décorateur fonctionne très bien: votre décorateur tient le compte, qui est incrémenté de next () et utilisé par le contrôle hasNext () .

Exemple (intentionnellement incomplet):

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

Pourquoi ne pas simplement

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

Je ne suis pas sûr de savoir pourquoi vous vous inquiétez de la création de cette liste temporaire. Il ne fait rien que je considérerais cher. En fait, créer cette liste coûte de loin moins cher que de parcourir cette liste, ce que je suppose, à votre avis.

Answer 5

La méthode ArrayList.sublist (int, int) ne crée pas de copie de la liste d'origine. Au lieu de cela, il retourne une instance de SubList qui encapsule l'ArrayList d'origine. L'itérateur renvoyé par la sous-liste dérivée de Array ne fait pas de copie non plus.

Mon conseil est donc d'essayer d'utiliser ArrayList comme type de liste de base et la méthode sublist . Si ce n'est pas assez rapide, implémentez votre propre variante de ArrayList qui implémente une méthode limitedLengthIterator . Par exemple, vous devriez pouvoir vous débarrasser du code vérifiant les modifications simultanées.

Answer 6

Si les performances vous préoccupent, n'utilisez pas d'Iterator, utilisez un index sur un tableau. Cela donnera une bien meilleure performance. Obtenir les N premiers éléments d’un tableau est trivial.

Answer 7

Cette version s'avère plus rapide que tous les autres exemples:

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 liste temporaire doit quand même être créée, un ArrayList est plus rapide que les listes décorées renvoyées par les autres méthodes de la bibliothèque.

Je suppose que ArrayList reçoit un traitement spécial au sein de la machine virtuelle.

Cela serait peut-être inefficace pour de très longues listes, mais mes listes sont courtes (presque toujours moins de 50 éléments.)