Quando vengono applicati gli algoritmi per la manipolazione degli elenchi di accesso casuale?

Question

In RandomAccess descrizione dell'interfaccia marcatore è scritto:

* <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. 

Nel metodo synchronisedList classe collezione c'è un assegno di RandomAccess & se il successo creare l'oggetto SynchronizedRandomAccessList ma loro anche nessun dettaglio per quanto riguarda l'algoritmo.

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

Quando si fa questo algoritmo si applicano e dove (si tratta di un codice nativo)?

Answer 1

Uno degli esempi è 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); 
} 

Qui diverse implementazioni algoritmo di ricerca binaria vengono utilizzati per l'accesso casuale e liste di accesso sequenziale. Il codice è un dettaglio di implementazione, ma è ragionevole differenziare gli elenchi qui.

Come specificato nel documenation for Collections.binarySearch:

Questo metodo viene eseguito nel registro tempo (n) per una lista "accesso casuale" (che fornisce quasi costante accesso in tempo posizionale). Se l'elenco specificato non implementa l'interfaccia RandomAccess ed è di grandi dimensioni, questo metodo eseguirà una ricerca binaria basata su iteratore che esegue gli attraversamenti di collegamento O (n) e confronti di elementi O (log n).