음.. 제가 MM 에디토리얼을 쓰는 날도 오는군요. >_<
마침 Provisional ranking이 19위로 바로 직전 SRM과 똑같습니다 (최종 결과에서는 20위나 21위가 될 수도 있겠지만요)
1 12.02.2007 05:23:53 34.84 C++
문제를 보고 이번엔 꼭 해야지! 라는 생각을 하고 #icpc 채널에서도 마침 열풍이더군요... 허나 오겜 하느라 처음에 너무 늦게 시작했습니다 -_-;
우선은 로컬에서 테스트하기 위해서 scoring function을 짜고 랜덤하게 순열을 만들어서 그 중 제일 좋은걸 리턴하게 해 보았습니다.. 만 5~6점대에서 놀더군요. +6 sigma가 넘는데도 저 정도 점수라니 앞으로 갈 길이 멀구나 하고 느꼈습니다.
아무튼 처음 방법은 a b를 스와핑해서 결과가 좋아지면 그대로 가고 아니면 가만히 있습니다. w2[i][j] = w[j][i] 로 놓아서 memory locality를 이용하기 시작했습니다. 시간제한도 안걸고 횟수제한을 걸었는데 20억/크기-크기*크기 로 걸었습니다.
2 12.02.2007 09:25:00 39.07 C++
아직까지도 전체 코드를 한 화면에서 볼 수 있습니다. 이번에는 SA를 한 번 적용해보았습니다. 상수를 대강 맞추어 보니 생각보다 결과가 많이 잘 나오더군요! 순위가 18위던가 19위던가 했는데 이 때부터 20위권과의 사투가 시작되었습니다...
3 12.02.2007 23:12:30 39.29 C++
코드가 점점 더러워집니다 -_-; SA는 28초까지만 돌리고 나머지 1초는 6개 범위 안에서의 순열을 만들어서 좋은걸로 옮겨타는 데 사용했습니다. SA와 마지막 로컬 서치의 방법이 달라서 점수 개선이 있었습니다.
int t1 = rand()%sz;
int t2 = rand()%sz;
if (t1==t2) continue;
if (t1>t2) swap(t1, t2);
이런 부분에서의 사소한 옵티마이즈에도 신경을 썼습니다. (원래는 t1>=t2면 continue)
4 12.03.2007 10:31:40 39.63 C++
코드가 여러 버젼이 존재하면서 혼란이 찾아옵니다. 6개 안에서 체크했던 순열이 5개까지만 체크한 것으로 바뀐 것은 일부러 그런 게 아니라 5개짜리를 고쳐서 6개짜리로 만들었던 건데 옛날 버젼을 수정하고 있어서 그렇습니다. 덕분에 t1>=t2 continue도 다시 부활해버렸고...
이제 플러스 요인입니다만 이번에 고친건 정말 별 거 없습니다. w2[i][j] = w[j][i] 이던 것을 w2[i][j] = w[j][i] - w[i][j] 로 고치고 덕분에 SA 부분에서의 계산을 절반으로 줄였습니다. 따라서 iteration이 두 배 돌아서 점수가 좋아졌습니다. 다만 마지막 로컬 서치는 옛날버젼으로 돌아가면서 약 0.02점 정도 감소했던 것으로 추정... 됩니다.
5 12.04.2007 12:49:42 40.04 C++
즐거운 옵티마이즈 시간입니다. 일단 순열 체크를 다시 6개로 만들었습니다. 쓸데없이 남아있던 테스트 코드를 제거했고, SA 부분에서의 for-loop를 다시 개선해서 루프 하나로 몰아버렸습니다.
이번엔 SA의 cooling speed를 두 배 느리게 해봤습니다. n이 클 때는 iteration 수가 모자랐는지 (n이 1000이면 가능한 조합이 500만인데 iteration 수가 1000만 단위니까 모자라는게 맞죠...) 성능이 꽤나 많이 개선되더군요.
6 12.04.2007 23:22:02 40.24 C++
이번엔 w2 배열과 기타 상수들을 double에서 float으로 고쳐보았습니다. 상당한 성능 개선이 이루어지면서 전체 점수도 상승했습니다.
정말 이거밖에 안했는데 0.20점이나 상승을????
(아래로...)
네 아쉽지만 사실입니다 ㅡㅜ n이 클 때 iteration 수는 여전히 부족하다는 것이고, 따라서 아직 올라갈 수 있는 점수가 꽤 있다는 것을 뜻하겠죠.
이제 12시간밖에 안 남았고 일도 해야 하고 회의도 있고 보고서도 써야 하는데 큰일입니다...
7 12.05.2007 05:08:21 40.46 C++
처음에 로컬 서치를 넣어보았습니다. 3 4 5 6 7 -> 4 5 6 7 3 또는 그 반대로 회전하는 것을 체크합니다. 특징이라면 한 열에서 가장 점수 상승이 많은 놈을 찾아서 그 놈까지의 영역에서 회전합니다.
로컬 서치가 끝나면 SA를 돕니다. 여러 가지 방법으로 테스트를 했으나 cooling speed가 너무 느리면 안되는 것 같고 5% 정도만 더 느리게 했습니다. 그래도 그 동안 iteration 수를 많이 늘려놨으니 그 혜택을 보게 해야겠죠...
SA에서 50%의 확률로 회전하는 것도 체크하는 부분을 넣어봤었는데 결과가 꽤 안좋아져서 포기했습니다.
SA가 끝나고 마지막에 로컬 서치를 다시 합니다. 7개 안에서의 순열 체크 -> 회전+역회전을 반복해서 체크 순서로 부분 최대치를 찾게 됩니다...
그러고보니 그 동안 어디선가 vector을 float*으로 고친게 있긴 한데 실제 iteration 횟수 증가에는 거의 영향이 없었습니다.
8 12.05.2007 11:43:54 40.57* C++
최적화를 위해 아주 여러가지 노력을 했는데 그 중에 실제로 쓰인건 한 두가지 방법 밖에 없군요...
우선 작은 n의 경우에는 5.5초 단위로 5번 테스트해서 그 중 최적해를 찾으려고 해 봤습니다. 중간 n에 대해서는 13초 단위로 2번... 그런데 해 보니 1번 하는 것보다 결과가 안 좋더군요 -_-; 결국 포기.. 역시 이 SA는 saturated 되려면 시간을 100배는 줘야 할 듯 싶습니다.
그리고 초반 로컬 서치 부분을 다시 뺐습니다 -_-; 오히려 SA에 악영향을 주는듯 하더군요....
이제 완전 땜빵 옵티마이즈인데.. 시간이 15초가 지나면 t1 t2가 100 이상이면 바꿀 때의 점수 변화를 계산하다가 누적 합이 -20 이하가 되면 걍 리젝합니다. 리젝을 안해야 하는데 해야 하는 경우도 분명히 있고 한 테스트 케이스에 대해서 7-8번 정도 있는 듯 하더군요. 허나 15초 이후에서의 속도 향상 효과가 워낙 커서 전체적으로는 플러스가 되었습니다.
그리고 막판 로컬 서치 부분을 원래는 단계별로 했엇는데, 순열 바꾸기와 회전하기 부분을 동시에 진행하도록 하였더니 결과가 더 좋아졌습니다. SA를 하다가 중간에서 끝내니 로컬 서치의 중요성이 커지겠죠...
로컬 서치 성능이 좋아져서 SA cooling speed를 24% 정도 늦추고 뒷부분은 로컬 서치에 맡겼습니다.. 약간의 성능 개선이 있는 듯 했습니다.
또한 아주 사소한 것이지만 드디어 남아 있던 t1>=t2 continue 부분을 발견하고 swap으로 바꿨습니다.. 훗훗...
마지막 버젼의 테스트 결과를 공개합니다~
Prev:48.132276 New:48.209138(+ 0.076862) (148800000) 100 48.209138 28.070(s)
Prev:40.876546 New:41.111633(+ 0.235087) (141750000) 110 41.111633 28.040(s)
Prev:43.896616 New:44.059986(+ 0.163369) (136000000) 120 44.059986 28.050(s)
Prev:45.458021 New:45.600415(+ 0.142394) (130640000) 130 45.600415 28.070(s)
Prev:44.362574 New:44.429486(+ 0.066912) (125790000) 140 44.429486 28.020(s)
Prev:43.705877 New:43.750428(+ 0.044551) (121600000) 150 43.750428 28.040(s)
Prev:43.510349 New:43.540487(+ 0.030138) (118620000) 160 43.540487 28.050(s)
Prev:42.419198 New:42.642906(+ 0.223708) (114750000) 170 42.642906 28.060(s)
Prev:44.653993 New:44.748421(+ 0.094428) (112640000) 180 44.748421 28.050(s)
Prev:45.251756 New:45.319823(+ 0.068067) (109050000) 190 45.319823 28.060(s)
Prev:38.850791 New:38.965777(+ 0.114986) (106200000) 200 38.965777 28.030(s)
Prev:45.290428 New:45.382358(+ 0.091929) (103880000) 210 45.382358 28.030(s)
Prev:38.453924 New:38.917689(+ 0.463765) (48240000) 900 38.917689 28.290(s)
Prev:37.877129 New:38.392063(+ 0.514933) (47400000) 910 38.392063 28.450(s)
Prev:38.417613 New:38.911523(+ 0.493910) (46320000) 920 38.911523 28.470(s)
Prev:38.299634 New:38.727688(+ 0.428055) (44880000) 930 38.727688 28.630(s)
Prev:38.480978 New:39.123879(+ 0.642902) (43830000) 940 39.123879 28.630(s)
Prev:38.659337 New:39.091170(+ 0.431832) (42210000) 950 39.091170 28.530(s)
Prev:38.830573 New:39.353513(+ 0.522940) (40710000) 960 39.353513 28.700(s)
Prev:39.514903 New:39.995497(+ 0.480594) (39210000) 970 39.995497 28.400(s)
Prev:38.694605 New:39.180868(+ 0.486263) (38400000) 980 39.180868 28.740(s)
Prev:38.565807 New:39.015791(+ 0.449983) (36870000) 990 39.015791 28.560(s)
Prev:38.126030 New:38.597478(+ 0.471449) (35880000) 1000 38.597478 28.430(s)
Total trial 11, total score 429.307159, ave 39.027924
Prev는 SA 결과 점수, New는 로컬 서치 적용 후 점수, 괄호 안의 천만단위 억단위 숫자는 iteration 수입니다.
실행시간 제한을 두 배로(60초) 늘리자 900~1000 점수가 평균 0.19점 정도 오르더군요. 100~200은 이 효과가 별로.. 라고 보면 경험적으로 전체 점수는 0.11점 정도 상승하는 것 같습니다. 탑코더 머신이 로컬보다 45% 정도 느린 것을 봐서 그 정도의 점수를 손해본 듯도 하네요. 혹시 제한을 32배 늘리면 점수가 1점 오르지 않을까요 ^^
시간이 좀 더 있었더라면 점수가 더 오르지 않았을까 싶은 아쉬움은 있습니다만 이 MM에 들인 시간은 충분하다고 생각합니다. 최상위 랭커들보다는 제가 시간을 더 많이 쓴 듯 합니다만... 처음 결과를 봤을 때는 제가 이런 점수가 나오리라고는 생각도 못했네요 -_-; 다들 MM 하다가 막혔다고 실망하지 마시고 열심히 노력해 보시면 좋을듯 합니다 ^^
포럼 글도 꼭 보세요. http://forums.topcoder.com/?module=Thread&threadID=595557&start=0&mc=42 를 보면 재미있는 접근법이 많이 있습니다.
그럼 다음에도 에디토리얼을 쓰기 희망하며 이만 마치겠습니다...