랜덤 액세스 목록을 조작하는 알고리즘은 언제 적용됩니까? 가능해, RandomAccess 마커 인터페이스 설명에서

Question

은이 기록됩니다 성공 알고리즘에 관한 SynchronizedRandomAccessList 개체하지만, 자신도 어떤 세부 사항을 작성하는 경우

컬렉션 클래스의 synchronisedList 방법에

* <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 &에 대한 검사가있다.

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

이 알고리즘은 언제 적용되며 어디에서 (네이티브 코드입니까?)? 예제

Answer 1

하나 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에서 규정

:

이 방법은 로그 (거의 일정한 시간 위치에 대한 액세스를 제공)는 "랜덤 액세스"목록 (N) 시간을 실행. 지정된 목록이 RandomAccess 인터페이스를 구현하지 않고 크기가 크면이 메서드는 O (n) 링크 통과 및 O (log n) 요소 비교를 수행하는 반복기 기반 이진 검색을 수행합니다.