플러그 인 For 순환 성능 최적화 사례

1 사례 설명
어느 날 자바 아이 에서 면접 문 제 를 보 았 습 니 다.문 제 는 다음 과 같 습 니 다.다음 코드 를 최적화 하 십시오.

for (int i = 0; i < 1000; i++)
	for (int j = 0; j < 100; j++)
		for (int k = 0; k < 10; k++)
			testFunction (i, j, k);

(주:뒤의 내용 과 일치 하기 위해 원 제 를 일부 수정 하 였 습 니 다)
2 사례 분석
제 시 된 코드 를 통 해 알 수 있 듯 이 아무리 최적화 하 더 라 도 test Function 이 실행 하 는 횟수 는 똑 같 고 이 부분 은 최적화 가능성 이 존재 하지 않 습 니 다.그러면 코드 의 최 적 화 는 순환 변수 i,j,k 의 실례 화,초기 화,비교,자체 증가 등 분야 의 소모 시간 에서 만 분석 할 수 있다.
먼저,우 리 는 먼저 원제 코드 순환 변수 가 실례 화,초기 화,비교,자체 증가 등 분야 에서 의 시간 소모 상황 을 분석한다.
변량
실례 화(횟수)
초기 화(횟수)
비교(횟수)
자가 증가(횟수)
i
1
1
1000
1000
j
1000
1000
1000 * 100
1000 * 100
k
1000 * 100
1000 * 100
1000 * 100 * 10
1000 * 100 * 10
(비고:한 번 의 시간 소모 가 서로 다른 기계 배치 에 따라 다 르 기 때문에 상기 표 와 관련 된 시간 은 처리 횟수 로 설명 합 니 다)
이 코드 의 성능 최 적 화 는 순환 변수 i,j,k 의 실례 화,초기 화,비교,증가 횟수 를 최대한 줄 이 는 동시에 다른 가능 한 연산 시간 을 도입 할 수 없다.
3 해결 과정
사례 분석 을 통 해 원제 코드 에 대해 우 리 는 두 가지 최적화 방안 을 제시 했다.
3.1 최적화 방안 1
코드 는 다음 과 같 습 니 다:

for (int i = 0; i < 10; i++)
	for (int j = 0; j < 100; j++)
		for (int k = 0; k < 1000; k++)
			testFunction (k, j, i);

이 방안 은 주로 순환 횟수 가 가장 적은 것 을 밖 에 두 고 순환 횟수 가 가장 많은 것 을 안에 넣 는 것 이다.그러면 최대한(주:3 개의 서로 다른 횟수 의 순환 변 수 는 모두 6 가지 배열 조합 상황 이 있 는데 이런 조합 이 가장 좋다)관련 순환 변수의 예화 횟수,초기 화 횟수,비교 횟수,자체 증가 횟수 를 줄 일 수 있다.방안 의 소모 상황 은 다음 과 같다.
변량
실례 화(횟수)
초기 화(횟수)
비교(횟수)
자가 증가(횟수)
i
1
1
10
10
j
10
10
10 * 100
10 * 100
k
10 * 100
10 * 100
10 * 100 * 1000
10 * 100 * 1000
3.2 최적화 방안 2
코드 는 다음 과 같 습 니 다:

int i, j, k;
for (i = 0; i < 10; i++)
	for (j = 0; j < 100; j++)
		for (k = 0; k < 1000; k++)
			testFunction (k, j, i);

이 방안 은 방안 1 을 바탕 으로 순환 변수의 실례 화 를 순환 외 에 두 면 관련 순환 변수의 실례 화 횟수 를 더욱 줄 일 수 있다.방안 의 소모 시간 은 다음 과 같다.
변량
실례 화(횟수)
초기 화(횟수)
비교(횟수)
자가 증가(횟수)
i
1
1
10
10
j
1
10
10 * 100
10 * 100
k
1
10 * 100
10 * 100 * 1000
10 * 100 * 1000
4 해결 결과
그렇다면 제 시 된 최적화 방안 은 우리 가 분석 한 것 처럼 성능 이 향상 되 었 습 니까?우 리 는 테스트 코드 를 작성 하여 검증 을 진행 하 는데,데 이 터 는 우리 의 최적화 효 과 를 더욱 설명 할 수 있다.
4.1 테스트 코드

public static void testFunction(int i, int j, int k) {
		System.out.print("");	//  ：          ，        
	}

	public static void testA() {
		long start = System.nanoTime();
		for (int i = 0; i < 1000; i++)
			for (int j = 0; j < 100; j++)
				for (int k = 0; k < 10; k++)
					testFunction(i, j, k);
		System.out.println("testA time>>" + (System.nanoTime() - start));
	}

	public static void testB() {
		long start = System.nanoTime();
		for (int i = 0; i < 10; i++)
			for (int j = 0; j < 100; j++)
				for (int k = 0; k < 1000; k++)
					testFunction(k, j, i);
		System.out.println("testB time>>" + (System.nanoTime() - start));
	}

	public static void testC() {
		long start = System.nanoTime();
		int i;
		int j;
		int k;
		for (i = 0; i < 10; i++)
			for (j = 0; j < 100; j++)
				for (k = 0; k < 1000; k++)
					testFunction(k, j, i);
		System.out.println("testC time>>" + (System.nanoTime() - start));
}

4.2 테스트 결과
1.테스트 기기 설정:Pentium(R)듀 얼 코어 CPU [email protected] 2.70GHz,2GB 메모리;
2.순환 변수 i,j,k 순환 횟수 는 각각 10,100,1000 으로 5 조 의 테스트 를 실시 하고 테스트 결 과 는 다음 과 같다.
제 1 조
제2 조
제3 조
제4 조
제 5 조
원안
171846271
173250166
173910870
173199875
173725328
방안 1
168839312
168466660
168372616
168310190
168041251
방안 2
168001838
169141906
168230655
169421766
168240748
위의 테스트 결 과 를 보면 최적화 후의 방안 은 원래 방안 보다 뚜렷 한 성능 이 우수 하여 최적화 효 과 를 거 두 었 다.그러나 최적화 방안 2 는 우리 가 예 상 했 던 것 처럼 방안 1 보다 좋 지 않다.그 중에서 2,4,5 조 의 데 이 터 는 방안 보다 더욱 나쁘다.순환 횟수 가 너무 적 고 테스트 환경 관련 요소 의 영향 을 받 아 나타 난 결과 일 수도 있다.
3.순환 변수 i,j,k 순환 횟수 를 각각 20,200,2000 으로 재 조정 하고 5 조 의 테스트 를 실시 한 결과 다음 과 같다.
제 1 조
제2 조
제3 조
제4 조
제 5 조
원안
1355397203
1358978176
1358128281
1350193682
1354786598
방안 1
1343482704
1348410388
1343978037
1347919156
1340697793
방안 2
1342427528
1343897887
1342662462
1342124048
1336266453
위의 테스트 결 과 를 보면 최적화 후의 방안 은 기본적으로 우리 의 기대 결과 에 부합된다.
총화
사례 분석 과 해결 과정 에서 세 표 의 분석 을 통 해 알 수 있 듯 이 최적화 방안 1 과 최적화 방안 2 의 성능 은 모두 원 코드 의 성능 보다 좋 고 그 중에서 최적화 방안 2 의 성능 이 가장 좋다.포 함 된 For 순환 에 서 는 순환 횟수 가 많은 순환 을 안쪽 에 두 고 순환 횟수 가 적은 순환 을 바깥쪽 에 두 면 성능 이 향상 된다.순환 변수의 실례 화 를 줄 이면 그 성능 도 향상 된다.테스트 데 이 터 를 통 해 알 수 있 듯 이 두 가지 최적화 방안 에 대해 순환 횟수 가 비교적 적은 상황 에서 그 운행 효과 의 차이 가 크 지 않다.그러나 순환 횟수 가 많은 상황 에서 그 효 과 는 비교적 뚜렷 하 다.
참고 자료
[1]
http://www.javaeye.com/topic/762312
[2]
http://www.javaeye.com/topic/632481