Ogranicza ListIterator do pierwszych elementów N (zoptymalizowanych)

Question

Co to jest prosty i szybki sposób na uzyskanie iteratora, który zwraca co najwyżej N elementów od początku List?

Najprostsze wersje mogłem wymyślić to:

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

Niestety obie wersje utworzyć tymczasowy List co znacząco wpływa na wydajność, jak Nazywam tę metodę miliony razy w ciasnej pętli.

Czy są jakieś inne funkcje biblioteczne, które mogę użyć do tego?

---

Uwaga: Nie mogę uniknąć iteracji po liście jak ja przekazaniem go do metody, która bierze iterator jako argument i nie mogę modyfikować tej klasy.

Answer 1

Wydaje się, że feature zostaną dodane do guawa Aktualny (R06), w beta:

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

Answer 2

To jest miejsce, gdzie Decorator działa bardzo dobrze: Twój dekorator zachowuje liczbę, która jest zwiększana o next() i jest używana przez kontrolkę hasNext().

Przykład (celowo niekompletna):

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

Dlaczego nie po prostu

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

Nie jestem pewien, dlaczego myśl o stworzeniu tego wykazu tymczasowego. Nie robi nic, co uważam za drogie. W rzeczywistości tworzenie tej listy jest zdecydowanie tańsze niż jej powtarzanie, co, jak zakładam, robisz.

Answer 4

Już wiesz, że to lista, więc możesz po prostu zadzwonić pod metodę List.subList(int fromIndex, int toIndex). Zgodnie ze specyfikacją, lista podrzędna jest wspierana przez oryginalną listę, więc tak naprawdę nie tworzy całkowicie rozwiniętego List, tylko jakiś obiekt proxy.

Answer 5

Ta wersja okazuje się szybciej niż którykolwiek z pozostałych przykładów:

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

Jeśli lista tymczasowy musi być tworzone tak, ArrayList jest szybszy niż zdobione list zwracanych przez innych metod bibliotecznych.

Domyślam się, że ArrayList otrzymuje specjalne traktowanie w VM.

Może byłoby to nieefektywne przez bardzo długi list, ale moje listy są krótkie (prawie zawsze mniej niż 50 elementów).

Answer 6

Jeśli chodzi o wydajność, nie należy używać iterator użyć indeksu na tablica. Zapewni to znacznie lepszą wydajność. Uzyskanie pierwszych N elementów tablicy jest banalne.

Answer 7

Metoda ArrayList.sublist(int,int) nie tworzy kopii oryginalnej listy. Zamiast tego zwraca instancję SubList, która otacza oryginalną ArrayList. Iterator zwrócony przez podlistę uzyskaną z tablicy Array również nie tworzy kopii.

Moja rada to wypróbować użycie ArrayList jako typu listy podstawowej i metody sublist. Jeśli nie jest to wystarczająco szybkie, zaimplementuj własny wariant ArrayList, który implementuje metodę limitedLengthIterator. Na przykład powinieneś być w stanie pozbyć się kodu, który sprawdza równoczesne modyfikacje.