Wann werden Algorithmen zum Manipulieren von Direktzugriffslisten angewendet?

Question

In Random Marker Schnittstellenbeschreibung steht geschrieben:

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

In synchronisedList Methodensammlung Klasse gibt es einen Scheck für Random & wenn Erfolg hinsichtlich Algorithmus SynchronizedRandomAccessList Objekt, sondern sie auch keine Details erstellen.

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

Wann gilt dieser Algorithmus und wo (ist es ein nativer Code)?

Answer 1

Eines der Beispiele ist 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); 
} 

Hier werden verschiedene binäre Suchalgorithmus Implementierungen werden für wahlfreien Zugriff und sequenziellem Zugriff Listen verwendet. Code ist ein Implementierungsdetail, aber es ist sinnvoll, hier Listen zu unterscheiden.

Wie in documenation for Collections.binarySearch angegeben:

Dieses Verfahren läuft in log (n) Zeit für eine "random access" Liste (die nahezu konstante Zeitpositions Zugang bereitstellt). Wenn die angegebene Liste der Random Schnittstelle nicht implementiert und groß ist, wird diese Methode einen Iterator-basierte binäre Suche tun, die O (n) Link Querungen und O (log n) Element Vergleiche durchführt.