카테고리 보관물: Java

Java

목록을 반복하는 것이 색인을 생성하는 것보다 빠른 이유는 무엇입니까? 가지 방법을 제공합니다.

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

List 인터페이스는 목록 요소에 대한 위치 (인덱싱) 액세스를위한 네 가지 방법을 제공합니다. 목록 (예 : Java 배열)은 0부터 시작합니다. 이러한 작업은 일부 구현 (예 : LinkedList 클래스)의 인덱스 값에 비례하여 시간에 따라 실행될 수 있습니다. 따라서 호출자가 구현을 알지 못하는 경우 목록의 요소를 반복하는 것이 일반적으로 목록을 통해 색인화하는 것보다 낫습니다.

이것이 정확히 무엇을 의미합니까? 나는 도출 된 결론을 이해하지 못한다.

답변

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

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

에 액세스하려면 item3직접 점프 할 수 없기 때문에 item3에 도달 할 때까지 모든 노드를 통해 머리에서 걸어야한다는 것을 분명히 알 수 있습니다.

따라서 각 요소의 값을 인쇄하려면 다음과 같이 작성하면됩니다.

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.

모든 단일 순회에서 O(N).

지금의 다른 구현하려고 List하는 ArrayList, 하나는 간단한 배열에 의해 백업됩니다. 이 경우 배열이 연속적이므로 임의의 위치로 무작위 점프를 허용하므로 위의 두 순회 모두 동일합니다.

답변

대답은 여기에 암시되어 있습니다.

이러한 작업은 일부 구현 (예 : LinkedList 클래스)의 인덱스 값에 비례하여 시간에 따라 실행될 수 있습니다.

연결 목록에는 고유 한 색인이 없습니다. 호출 .get(x)은 목록 구현이 첫 번째 항목을 찾고 .next()x-1 번 호출 해야합니다 (O (n) 또는 선형 시간 액세스의 경우). 여기서 배열 지원 목록은 backingarray[x]O (1) 또는 상수 시간 으로 인덱싱 할 수 있습니다 .

JavaDoc forLinkedList 를 보면 주석이 표시됩니다.

모든 작업은 이중 연결 목록에 대해 예상 할 수있는대로 수행됩니다. 목록으로 인덱싱하는 작업은 지정된 인덱스에 더 가까운 처음부터 끝까지 목록을 순회합니다.

반면 JavaDoc를위한ArrayList 대응을 갖는다

List 인터페이스의 크기 조정 가능 배열 구현. 모든 선택적 목록 작업을 구현하고 null을 포함한 모든 요소를 ​​허용합니다. List 인터페이스를 구현하는 것 외에도이 클래스는 목록을 저장하기 위해 내부적으로 사용되는 배열의 크기를 조작하는 메서드를 제공합니다. (이 클래스는 비 동기화된다는 점을 제외하면 Vector와 거의 동일합니다.)

는 size, isEmpty, get, set, iterator, 및 listIterator처리는, 일정한 시간에 실행됩니다. 추가 작업은 상각 된 일정 시간에 실행됩니다. 즉, n 개의 요소를 추가하려면 O (n) 시간이 필요합니다. 다른 모든 작업은 선형 시간으로 실행됩니다 (대략적으로 말하면). 상수 요소는 LinkedList구현에 비해 낮습니다 .

“Java Collections Framework에 대한 Big-O 요약”이라는 제목 의 관련 질문 에는 도움이 될 수있는 “Java Collections JDK6” 자원을 가리키는 대답이 있습니다 .

답변

받아 들여지는 대답은 가장 확실하지만 사소한 결함을 지적 할 수 있습니까? 튜더 인용 :

이제 List의 다른 구현 인 ArrayList로 이동하면 간단한 배열이 지원됩니다. 이 경우 배열이 연속적이므로 임의의 위치로 무작위 점프를 허용하기 때문에 위의 두 순회 모두 동일 합니다.

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

ArrayList를 사용하면 손으로 쓴 카운트 루프가 약 3 배 빠릅니다.

출처 : 성능을위한 설계, Google의 Android 문서

필기 루프는 인덱싱 된 반복을 참조합니다. 향상된 for 루프와 함께 사용되는 반복기 때문이라고 생각합니다. 연속 배열로 뒷받침되는 구조에서 약간의 성능 저하를 가져옵니다. 나는 또한 이것이 Vector 클래스에 대해 사실이라고 생각합니다.

내 규칙은 가능할 때마다 향상된 for 루프를 사용하고 성능에 대해 정말로 관심이 있다면 ArrayLists 또는 Vectors에만 인덱스 된 반복을 사용하는 것입니다. 대부분의 경우이를 무시할 수도 있습니다. 컴파일러가 백그라운드에서이를 최적화 할 수 있습니다.

Android 개발의 맥락에서 ArrayLists의 두 순회가 반드시 동일하지는 않다는 점을 지적하고 싶습니다 . 생각을위한 음식.

답변

와 같이 조회 오프셋이있는 목록을 반복하는 것은 화가의 알고리즘 인 Shlemieli 과 유사 합니다 .

Shlemiel은 거리 화가로 취직하여 길 중간에 점선을 그립니다. 첫날 그는 페인트 캔을 도로에 꺼내 300 야드의 도로를 완주합니다. “그건 꽤 좋다!” 그의 상사는 “당신은 빠른 일꾼입니다!”라고 말합니다. 그리고 그에게 코펙을 지불합니다.

다음날 Shlemiel은 150 야드 밖에 나가지 않습니다. “음, 어제만큼 좋지는 않지만, 당신은 여전히 ​​빠른 일꾼입니다. 150 야드는 존경 할 만합니다.”그리고 그에게 코펙을 지불합니다.

다음날 Shlemiel은 도로의 30 야드를 그립니다. “단 30!” 그의 상사를 외친다. “그건 용납 할 수없는 일입니다! 첫날에 당신은 그렇게 많은 일을 10 배나 했어요! 무슨 일 이죠?”

“나는 그것을 도울 수 없습니다”라고 Shlemiel은 말합니다. “매일 페인트 통에서 점점 멀어집니다!”

소스 .

이 작은 이야기는 내부적으로 무슨 일이 일어나고 있고 왜 그렇게 비효율적인지 이해하는 것을 더 쉽게 만들 수 있습니다.

답변

LinkedList구현 의 i 번째 요소를 찾기 위해 i 번째 까지 모든 요소를 ​​살펴 봅니다.

그래서

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

답변