마지막 블록에 if 문을 삽입 정렬 코드로 작성하는 것이 합리적입니까?

나는 Cormen & Co에 의해 "Introduction to Algorithms"을 읽고 java에서 알고리즘을 구현합니다. 궁금하다 삽입 정렬 코드에 작성하는 경우 최종 - set() 메서드에서 문장? 가능하다면 코드를 더 빨리 만들고 싶습니다.마지막 블록에 if 문을 삽입 정렬 코드로 작성하는 것이 합리적입니까?

public static void insertion(List<Integer> a) { 
    List<Integer> aList = a; 
    int temp; 
    int previousIndex; 

    for (int i = 1; i < aList.size(); i++) { 
     temp = aList.get(i); 
     previousIndex = i - 1; 
     while ((previousIndex >= 0) && aList.get(previousIndex) > temp) { 
      aList.set(previousIndex + 1, a.get(previousIndex)); 
      previousIndex--; 
     } 

     //if(aList.get(previousIndex + 1) > temp){ 
      aList.set(previousIndex + 1, temp); 
     //} 

    } 
}

실례합니다 (초급 경우). 나는 아주 초보자이다.

출처

2012-08-26 Ramon Dekkers

함수의 첫 번째 줄은 less를 사용합니다. 동일한 객체를 가리 키기 만하면됩니다. 당신은 id'aList = a.clone()'또는'aList = new ArrayList ()'을하고 루프를 사용하여 요소를 복사해야합니다. – elyashiv

'Introduction to algorithms'을봤을 때'if'가 그들의 의사 코드에 없습니다. 어쨌든 필요하지 않습니다. 나는 네가 무엇을 요구하고 있는지 정말로 이해하지 못한다. – Tudor

@ Tudor, 가능한 경우 코드를 더 빨리 작성하고 싶습니다. if 문이 삽입 정렬 의사 코드에 없습니다. –

이 코드는 코드를 최적화하는 것처럼 보이며 빠르게 만듭니다. 명백한 아이디어는 데이터를 설정하지 않도록 테스트하는 것입니다. 이렇게하면 (1) 값을 읽고 테스트하는 것이 값을 설정하는 것보다 빠르며 (2) 테스트에서 값을 설정하지 않아도되는 충분한 경우가있을 때만 실행이 더 빨라집니다.

IMO (1)는 매우 모호하며 (2) 많은 시간을 절약해야하는 경우가 자주 있습니다. 그렇다고 생각하지 않습니다.

(aList.get (previousIndex + 1)> temp) 대신 (previousIndex + 1! = i) 테스트를 수행하면 더 빠른 테스트를 수행 할 수 있습니다. 복합 객체 구조를 복사하는 것과 같이 목록에 훨씬 많은 시간이 소요됩니다. 그러나 out 케이스의 경우 Integer 객체에 대해 이야기하고 있으므로 테스트를 추가하면 모든 경우에 속도가 느려집니다.

물론 모든 최적화에서 그렇듯이 실생활 측정 결과 만 효과적임을 알 수 있습니다. 그 이유는 최적화가 항상 마지막 일이며 필요한 경우에만 그렇습니다.

출처

2012-08-26 19:05:56

고마워, 프레드릭! –

마지막 블록에 if 문을 삽입 정렬 코드로 작성하는 것이 합리적입니까?

답변

관련 문제