목록을 반복하는 것이 목록을 통해 인덱싱하는 것보다 더 빠른 이유는 무엇입니까?

목록을 반복하는 것이 목록을 통해 인덱싱하는 것보다 더 빠른 이유는 무엇입니까?

ADT 목록에 대한 Java 문서를 읽으면 다음과 같이 표시됩니다.

List 인터페이스는 목록 요소에 대한 위치(인덱스화) 액세스를 위한 4가지 방법을 제공합니다.리스트(Java 어레이 등)는 제로 베이스입니다.이러한 조작은 일부 구현(LinkedList 클래스 등)에서는 인덱스 값에 비례하여 시간 내에 실행될 수 있습니다.따라서, 리스트내의 요소를 반복하는 것은, 통상, 발신자가 실장을 인식하고 있지 않은 경우, 그것을 개입시켜 인덱스를 작성하는 것보다 바람직합니다.

이게 정확히 무슨 뜻이죠?나는 도출된 결론을 이해할 수 없다.

링크 목록에서 각 요소에는 다음 요소에 대한 포인터가 있습니다.

head -> item1 -> item2 -> item3 -> etc.

액세스 하려면item3직접 점프할 수 없기 때문에 항목 3에 도달할 때까지 모든 노드를 헤드에서 통과해야 한다는 것을 명확하게 알 수 있습니다.

따라서 각 요소의 값을 인쇄하려면 다음과 같이 입력합니다.

for(int i = 0; i < 4; i++) {
    System.out.println(list.get(i));
}

다음과 같은 일이 발생합니다.

head -> print head
head -> item1 -> print item1
head -> item1 -> item2 -> print item2
head -> item1 -> item2 -> item3 print item3

인덱싱할 때마다 목록 시작 부분부터 다시 시작되어 모든 항목을 검토하기 때문에 이 작업은 매우 비효율적입니다.이는 복잡성이 효과적으로O(N^2)록을을넘넘!

대신 이렇게 하면:

for(String s: list) {
    System.out.println(s);
}

그러면 다음과 같은 일이 발생합니다.

head -> print head -> item1 -> print item1 -> item2 -> print item2 etc.

1회 즉 1회 통과, 즉 통과는 1회입니다.O(N).

그럼 이제 다른 요?List, 「」입니다.ArrayList심플한 어레이로 백업되어 있습니다.이 경우 어레이는 연속적이기 때문에 임의의 위치로 랜덤으로 점프할 수 있기 때문에 위의 두 트래버설은 동일합니다.

답은 다음과 같습니다.

이러한 조작은 일부 구현(LinkedList 클래스 등)에서는 인덱스 값에 비례하여 시간 내에 실행될 수 있습니다.

즉, 호출하는 인덱스는 없습니다. 호출.get(x)는 첫 하여 콜하기 합니다..next()타임액세스의 ), 는 x-1로 할 수 있습니다.backingarray[x]O(1)는, O(1)를 사용하고 있습니다.

JavaDoc for 를 참조하면, 코멘트가 표시됩니다.

모든 작업은 이중 링크 목록에서 예상한 대로 수행됩니다.목록에 인덱싱된 작업은 시작 또는 끝 중 지정된 인덱스에 가까운 목록을 통과합니다.

반면 for JavaDoc에는 대응하는 기능이 있습니다.

List 인터페이스의 크기 조정 가능한 어레이 구현.모든 옵션의 리스트 조작을 실장해, 늘을 포함한 모든 요소를 허가합니다.이 클래스에서는 목록 인터페이스 구현과 더불어 목록을 저장하기 위해 내부적으로 사용되는 배열 크기를 조작하는 메서드를 제공합니다.(이 클래스는 비동기화라는 점을 제외하고 벡터와 거의 동일합니다).

size,isEmpty,get,set,iterator , , , , 입니다.listIterator작업은 일정한 시간에 실행됩니다.추가 작업은 상각된 상수 시간으로 실행됩니다. 즉, n개의 요소를 추가하려면 O(n) 시간이 필요합니다.다른 모든 작업은 선형 시간으로 실행됩니다(대략).는 상수에 .LinkedList★★★★★★ 。

"Java Collections Framework에 대한 Big-O 요약"이라는 제목의 관련 질문에는 이 리소스인 "Java Collections JDK6"에 대한 답변이 있습니다.

예: " " " )을 반복합니다.i는 화가 Shlemiel의 알고리즘과 유사합니다.

Shlemiel은 도로 한가운데 점선을 그리는 길거리 화가로서 직업을 얻는다.첫날 그는 페인트를 한 캔 들고 거리로 나와 300야드의 도로를 완성했다."괜찮아!"라고 그의 상사가 말하고, "당신은 빨리 일해요!"라고 말하며 그에게 코페크를 지불합니다.

다음날 Shlemiel은 150야드만 간다."그건 어제만큼은 아니지만, 그래도 일을 빨리 하시는군요.150야드가 적당해"라고 말하며 코펙을 지급한다.

다음날 Shlemiel은 30야드의 도로를 그린다."30명밖에 안 돼!" 그의 상사가 소리친다."그건 용납할 수 없어요!첫날에 당신은 그 열 배나 많은 일을 했구나!무슨 일이야?"

"어쩔 수 없어요." Shlemiel이 말해요."매일 페인트통에서 점점 멀어지고 있어요!"

출처.

이 작은 이야기는 내부에서 무슨 일이 일어나고 있고 왜 그것이 그렇게 비효율적인지를 이해하기 쉽게 할 것이다.

인정된 답변은 매우 정확하지만, 사소한 결함을 지적해도 될까요?튜더 인용:

다음으로 리스트의 다른 실장 Array List로 넘어가겠습니다.이 실장은 단순한 어레이에 의해 백업되고 있습니다.이 경우 어레이는 연속적이기 때문에 임의의 위치로 랜덤으로 점프할 수 있기 때문에 위의 두 트래버설은 동일합니다.

이것은 완전히 사실이 아니다.사실은 말이다

ArrayList를 사용하면 수기 카운트 루프가 약 3배 빨라집니다.

출처: 성능을 위한 디자인, Google의 Android 문서

수기 루프는 인덱스된 반복을 의미합니다.루프에 확장 기능을 사용하는 반복기 때문일 수 있습니다.연속 배열에 의해 백업되는 구조에서 패널티로 마이너 퍼포먼스가 발생합니다.벡터 클래스에도 해당될 수 있습니다.

가능한 한 확장 루프를 사용하여 성능을 중시하는 경우에는 ArrayLists 또는 Vectors 중 하나에 대해서만 인덱스된 반복을 사용하는 것이 규칙입니다.대부분의 경우, 컴파일러가 백그라운드에서 최적화하고 있을 가능성이 있기 때문에 무시해도 됩니다.

Android에서의 개발의 맥락에서 ArrayLists의 양쪽 트래버스가 반드시 동등하다고는 할 수 없다는 것을 지적하고 싶습니다.생각할 거리야.

의 i번째 요소를 찾으려면LinkedList구현은 i번째까지 모든 요소를 통과합니다.

그렇게

for(int i = 0; i < list.length ; i++ ) {
    Object something = list.get(i); //Slow for LinkedList
}

언급URL : https://stackoverflow.com/questions/10486507/why-would-iterating-over-a-list-be-faster-than-indexing-through-it