Dlaczego fill(),() kopię, reverse() i shuffle() z kolekcji w Javie jest realizowany w ten sposób

Question

Według javadoc ... Collections.fill() jest napisane jak poniżej:

public static <T> void fill(List<? super T> list, T obj) { 
     int size = list.size(); 

     if (size < FILL_THRESHOLD || list instanceof RandomAccess) { 
      for (int i=0; i<size; i++) 
       list.set(i, obj); 
     } else { 
      ListIterator<? super T> itr = list.listIterator(); 
      for (int i=0; i<size; i++) { 
       itr.next(); 
       itr.set(obj); 
      } 
     } 
    } 

Łatwo zrozumieć, dlaczego nie używasz listIterator dla stanu stan od RandomAccess. Ale jaki jest pożytek z powyższego?

Mam na myśli, czy jest jakaś znacząca korzyść z wydajności w porównaniu z używaniem iterator dla size>=FILL_THRESHOLD, a nie dla size < FILL_THRESHOLD?

widzę to samo podejście do Collections.copy() również:

public static <T> void copy(List<? super T> dest, List<? extends T> src) { 
     int srcSize = src.size(); 
     if (srcSize > dest.size()) 
      throw new IndexOutOfBoundsException("Source does not fit in dest"); 

     if (srcSize < COPY_THRESHOLD || 
      (src instanceof RandomAccess && dest instanceof RandomAccess)) { 
      for (int i=0; i<srcSize; i++) 
       dest.set(i, src.get(i)); 
     } else { 
      ListIterator<? super T> di=dest.listIterator(); 
     ListIterator<? extends T> si=src.listIterator(); 
      for (int i=0; i<srcSize; i++) { 
       di.next(); 
       di.set(si.next()); 
      } 
     } 
    } 

FYI:

private static final int FILL_THRESHOLD   = 25; 

private static final int COPY_THRESHOLD   = 10; 

samo podejście do poniżej:

public static void reverse(List<?> list) 
public static void shuffle(List<?> list, Random rnd) 

EDIT:

Moja dezorientacja jest size<FILL_THRESHOLD części, nie dla RandomAccess

Answer 1

to chyba dlatego, że lista rodzajowy nie ma być ArrayList. Nie ma gwarancji, że ustawienie losowego indeksu odbywa się w stałej O (1) czasu. W tym samym czasie budowanie iteratora i praca nad nim ma swój narzut.

Podsumowując, dla małych list można poświęcić fakt, że użycie iteratora dałoby mniejszą złożoność dostępu do kolejnych elementów, przez zapisanie narzutu tworzenia samego iteratora.

To dlatego, że list.set(i, obj) może być droższe niż itr.set(obj), ale w tym ostatnim masz niejawny narzut zarządzania iteratorem. Ponieważ złożoność może być liniowa O (n), używanie większej liczby list może być skutecznym problemem przy użyciu list.set(i, obj).

Answer 2

Java 1.2, która wprowadziła ramy zbierania i Java 1,3 używane proste podejście z ListIterator:

public static void fill(List list, Object o) { 
    for (ListIterator i = list.listIterator(); i.hasNext();) { 
     i.next(); 
     i.set(o); 
    } 
} 

Progi wprowadzono wraz z interfejsem RandomAccess markera w wersji 1.4 (oparte na kodzie starszych dla JDK ze strony Oracle).

Myślę, że jest to algorytm optymalizacji starszych algorytmów zbierania śmieci - te starsze algorytmy miały raczej heavy penalties for creating a new object (takie jak ListIterator). Dlatego używanie seterów dla list nie-O (1) miało sens.

Raczej ironicznie, Java 1.4.1 wprowadziła nowy garbage collector, który spowodował, że tworzenie obiektów było o wiele tańsze dla obiektów krótkotrwałych, takich jak iterator.