Rasgele erişim listelerini işlemek için algoritmalar ne zaman uygulanır? RandomAccess işaretleyici arabirimi açıklamasında

Question

yazılıdır: başarı algoritması ile ilgili SynchronizedRandomAccessList nesneyi ama onların da hiçbir ayrıntı oluşturursanız

toplama sınıfı synchronisedList yönteminde

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

RandomAccess & bir çek var.

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

Bu algoritma ne zaman uygulanır ve nerede (yerel bir koddur)? örneklerin

Answer 1

bir Collections.binarySearch olup:

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

Aşağıda, farklı ikili arama algoritması uygulamaları rastgele erişim ve sıralı erişim listeleri için kullanılır. Kod bir uygulama detayıdır, ancak listeleri burada ayırt etmek mantıklıdır.

documenation for Collections.binarySearch belirtildiği gibi

:

Bu yöntem günlüğüne (sabite yakın zamanlı konumsal erişim sağlar), bir "rastgele erişim" listesinde (n) olarak çalışır. Belirtilen liste RandomAccess arabirimini uygulamıyorsa ve büyükse, bu yöntem O (n) bağlantı geçişlerini ve O (log n) öğesi karşılaştırmasını gerçekleştiren yineleyici tabanlı bir ikili arama yapar.