Kiedy są stosowane algorytmy do manipulowania listami dostępu swobodnego?

Question

W RandomAccess opisu interfejsu znacznik jest napisane:

* <p>The best algorithms for manipulating random access lists (such as 
* <tt>ArrayList</tt>) can produce quadratic behavior when applied to 
* sequential access lists (such as <tt>LinkedList</tt>). Generic list 
* algorithms are encouraged to check whether the given list is an 
* <tt>instanceof</tt> this interface before applying an algorithm that would 
* provide poor performance if it were applied to a sequential access list, 
* and to alter their behavior if necessary to guarantee acceptable 
* performance. 

W metodzie synchronisedList klasy kolekcja jest czek na RandomAccess & jeśli sukces utworzyć obiektu SynchronizedRandomAccessList ale ich też żadnych szczegółów dotyczących algorytmu.

public static <T> List<T> synchronizedList(List<T> list) { 
    return (list instanceof RandomAccess ? 
       new SynchronizedRandomAccessList<T>(list) : 
       new SynchronizedList<T>(list)); 
    } 

Kiedy stosuje się ten algorytm i gdzie (czy jest to kod natywny)?

Answer 1

Jednym z przykładów jest Collections.binarySearch:

public static <T> int binarySearch(List<? extends Comparable<? super T>> list, T key) { 
    if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD) 
     return Collections.indexedBinarySearch(list, key); 
    else 
     return Collections.iteratorBinarySearch(list, key); 
} 

Tutaj różne implementacje algorytmu wyszukiwania binarnego są używane do swobodnego dostępu i sekwencyjnych list dostępowych. Kod jest szczegółem implementacji, ale rozsądne jest tutaj rozróżnienie list.

Jak określono w documenation for Collections.binarySearch:

Ta metoda działa w log (n) dla "random access" listy (która zapewnia prawie stałą czasu pozycyjny dostępu). Jeśli podana lista nie implementuje interfejsu RandomAccess i jest duża, ta metoda wykona binarne wyszukiwanie oparte na iteratorze, które wykona O (n) przewijanie łączy i porównań elementów O (log n).