什麼時候應用操作隨機訪問列表的算法？

在RandomAccess的標記接口說明上寫着：什麼時候應用操作隨機訪問列表的算法？

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

在集合類synchronisedList方法有用於RandomAccess的&一個檢查，如果成功創建關於算法SynchronizedRandomAccessList對象，但他們也沒有詳細說明。

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

這個算法什麼時候適用，哪裏（是一個本地代碼）？

來源

2013-03-12 Prateek

'synchronizedList'創建一個數據結構，它不是一個真正的算法... – 2013-03-12 08:40:02

@OliCharlesworth這是正確的，但看到的文檔評論，談論算法...即時詢問什麼時候和在算法應用 – Prateek 2013-03-12 08:42:13

什麼算法你指的是？ – 2013-03-12 08:43:41

其中一個例子是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); 
}

這裏不同二進制搜索算法的實現用於隨機接入和順序訪問列表。代碼是一個實現細節，但在這裏區分列表是合理的。

如documenation for Collections.binarySearch指定：

該方法運行log用於「隨機訪問」列表（n）的時間（其提供接近恆定的時間的位置訪問）。如果指定的列表沒有實現RandomAccess接口並且很大，則此方法將執行基於迭代器的二進制搜索，以執行O（n）鏈接遍歷和O（log n）元素比較。

來源

2013-03-12 08:45:41

什麼時候應用操作隨機訪問列表的算法？

回答

相關問題