이제까지의 스토리~
6/24 - SA를 끼얹어보았다. 생각보다 점수가 잘 나온다.
1 06.24.2010 10:51:43 45.31 C++
6/25 - R/C에 비해서 K가 작을 때는 부분적으로만 테스트하는 루틴을 만들었다.
2 06.25.2010 01:06:32 46.47 C++
3 06.25.2010 06:13:02 46.95 C++
4 06.25.2010 08:16:56 47.35 C++
5 06.25.2010 10:16:57 47.81 C++
6 06.25.2010 12:18:09 48.28 C++
6/26 - 7번 서미션 49.11은 순전히 각 iteration마다 체크하던 getTime을 20회마다 체크하게 바꿔서 그렇다....
원래 K가 작을때 체크하던 루틴은 두번 돌고 그 차이값을 구하는데 그러지 말고 최종 테이블 결과는 어디에 기록하도록 바꿔서 두 배 정도 빨라진 것 같다.
7 06.25.2010 18:40:46 49.11 C++
8 06.26.2010 03:56:40 48.20 C++
9 06.26.2010 06:02:18 48.59 C++
10 06.26.2010 08:05:13 49.45 C++
11 06.26.2010 14:38:23 49.47 C++
6/27 - 이 날은 bitmap이 출동하였다. 각 위치는 5비트를 차지한다. 나중에 (16*현재값) + 주변 갯수 를 세어야 하기 때문에 5비트가 필요하다.
unsigned int 한 자리에 6개의 위치를 저장할 수 있다. 쉬프트를 적절하게 사용하여 계산하는 방법을 고안하였다.
12 06.27.2010 05:35:58 49.54 C++
13 06.27.2010 07:59:58 49.64 C++
14 06.27.2010 12:21:49 49.65 C++
6/28 - 가장 대책이 없던 날. Psyho가 50.25로 한번에 치고 올라온 날이다.
초 최적화를 위해서 __attribute__ 등을 써가며 버둥거렸다 --;
15 06.27.2010 18:25:03 49.73 C++
16 06.28.2010 01:57:28 49.80 C++
17 06.28.2010 04:53:35 49.70 C++ 18번 서밋 - 이 날은 나의 SA 인생에서 꽤 중요한 날이 아니었나 싶다. 현재 score가 흔들리는 정도와 실제로 솔루션을 채택하는 확률을 조합하여 SA를 적절하게 돌아가도록 만들었다.
기대대로 상태가 좋아져서 18번 서밋에서 0.07점 올랐지만 사실은 빙산의 일각일 뿐이었다...
18 06.28.2010 07:42:10 49.77 C++
6/29 - 전체 테이블에 대해서 계산할 때만 돌아가던 bitmap을 일부분만 계산하는 루틴에도 들어가도록 했다. 이 당시에는 전체를 계산하는 경우와 일부분만 계산하는 경우가 전체의 절반쯤 되었고, bitmap 적용 후 속도는 약 1.6~7배로 올라갔다.
속도가 2배로 오르면 점수가 0.55점 정도 오르던 시기이니 이 bitmap 사용으로는 점수가 0.2점 정도 오른 것 같다. 또한 bitmap을 5bit에서 4bit만 사용하도록 수정하면서 (주변 갯수를 일단 구하고 내 상태*8을 xor한다. 어차피 갯수가 8의 배수인 경우는 없어지는 경우이니....) 점수가 조금 더 올랐다.
그런데 22번 서밋에서 점수가 크게 흔들리는 문제가 발생하였다. 문제를 분석하던 도중, 18번 서밋에서의 SA 부분에 버그가 있음이 밝혀졌다. 솔루션을 채택하는 확률이 떨어지면 온도를 올려야 하는데, 실제로는 내리고 있었던 것이다. 따라서 중요한 시점에 온도가 확 떨어지면서 iteration 수가 확 줄어드는 문제가 있었던 것이다. 결국 score가 흔들리는 정도로 온도를 조정하는 부분이 워낙 성능이 좋았기 때문에, 솔루션을 채택하는 확률을 보는 부분이 망했어도 그 부분을 가리고 0.07점을 올릴 수 있었던 것이다.
23번 서밋에서 이것을 수정하자 점수가 급상승하면서 50.43에 진입하였다. 당시 1위인 doudouille는 50.45점, 2위였던 Psyho는 50.42점이었는데 Psyho를 밀어내고 2위로 다시 올라갔다. 로컬 테스트 결과 전체 SA 수정 부분의 효과는 0.54점이었다.
이후에는 날씨가 좋은 관계로 iteration 수가 0.5%씩 좋아지는 버젼으로 계속 제출했더니 정말 그만큼만 올랐다...
19 06.28.2010 22:55:20 49.84 C++
20 06.29.2010 01:35:49 49.79 C++
21 06.29.2010 03:54:21 50.25 C++
22 06.29.2010 06:18:33 50.06 C++
23 06.29.2010 08:32:02 50.43 C++
24 06.29.2010 10:32:36 50.44 C++
25 06.29.2010 12:33:19 50.44 C++
6/30 - 가 다시 내렸다. 0.02점 정도는 충분히 오차범위에 든다. 계속 대략 0.5~1%씩 iteration 수가 증가하는 버젼이다. (위에도 그렇지만 간혹 그렇지 않고 같은 버젼 두번 낸 경우도 있다)
26 06.30.2010 08:38:53 50.46 C++
27 06.30.2010 11:27:39 50.44 C++
7/1 - 일기 시작!
28 06.30.2010 18:09:12 50.51 C++
29 07.01.2010 03:08:34 50.57 C++
7/1 09:45
어제 밤에는 일단 conversion lookup table의 크기를 16*16에서 16*16*16으로 늘리고, 한번에 두 개의 아이템씩 보던 것을 세 개의 아이템씩 보게 했다. 대략 전체적으로 3% 정도의 iteration 증가가 있었다. 이렇게 하고 서밋하니 점수가 50.46에서 50.44로 떨어졌다. 50.48 정도를 예측했는데 오차에서 왔다갔다인것 같다.
그 뒤에는 숙원사업인 non-compressed grid를 제거하는 작업 1단계에 들어갔다. 우선 가장 쉬운 부분인 wrap-up이 안 되는 경우를 처리했다. 서버에서 iteration 횟수 +4.1%의 효과가 있었다. new method를 사용하는 경우에만 적용되기 때문에 실제로는 +3% 정도인 것 같다.
시간이 없어서 일단 자고 아침에 서밋하니 50.51점이 나온다. 어제 밤에 안 오른 점수까지 같이 오르는 것같다.
서버 데이터 셋의 stdev를 생각해보면, 여기에는 그리 어려운 데이터가 없어서, +-0.03점 정도의 stddev를 가지는 것 같다. 참고로 50.51x2 버젼의 local stdev는 0.096이고, 문제의 38번 시드를 제외하면 0.059가 된다.
점수대마다의 sensitivity는 다음과 같다.
49점 - iteration doubling : +0.60 (rough)
50점 - iteration doubling : +0.52 (rough)
50.51점 - iteration doubling : +0.46
iteration doubling 시 올라가는 점수가 점수 +1점마다 대략 -0.09점 정도 되는것 같다. 이 추세라면 50.51 + 0.46/0.09 = 55.62점이 점수의 한계치가 된다.
한편 로컬 테스트의 sum(case min)~sum(case max) 추이로 보면
46.58/48.81 -> 47.26/49.18 이 되었으므로 둘 다 linear하게 쭉 올려보면 51.47점이 된다. 로컬 테스트는 시스템 테스트보다 2.8점 정도 낮으므로 더하면 54.27점이 된다.
54~56점 사이가 최적해의 한계치인것 같다!
7/1 16:29
현재 시스템상, 1/3의 확률로는 제거를 시도해보고 2/3의 확률로는 넣기를 시도해본다. 가장 최근 업데이트를 하고 나서 제거를 시도해본 히스토리가 있으면 저장해뒀다가 꺼내쓰자.. 라는 아이디어가 있어서 구현을 해 보았는데 9초 이후의 iteration 수만 10배정도로 폭증--;; 했으나 전체 점수에는 거의 영향이 없었고 오히려 좀 나빠진 것이 중요한 iteration 수를 막 깎아먹었다. 아무래도 L2 cache로 인해서 빅장을 맞는 듯 하다.
아무튼 여기서 교훈은 9초 이후의 iteration은 지금 별 영향을 끼치지 못한다는 것이라서, 여기서 교훈을 얻어서 log(0.2/prob)의 가중치를 0.2에서 0.25로 올리고 서밋했다. 원래는 막판에 하려는 거였는데 일단 눈에 보이니 고쳐서 바로 서밋했는데 점수가 0.06점이나 오른 50.57점이 나왔다! 로컬 테스트를 돌려서 정확한 영향을 측정해야겠다.
앞으로 할 일 -
1) non-compressed grid 제거 작업 part 2 (+2% 예상)
2) non-compressed grid 제거 작업 part 3 (+1%++ 예상)
3) SSE 적용 (instruction 최적화시 +35% 예상)
4) varation이 큰 예제들 살펴보고, 해결 방안을 강구한다.
5) K=2 케이스 최적화 찾기에 대해 고민해본다.
7/1 18:44
코어 코드를 보다가 문득 모두 더하고 >> 를 하면 좋겠다고 생각했다. 고쳐보니 의외로 식이 매우 깔끔하게 나온다. 컴파일러가 처리하기 좋은 형태로... 끼얹어봤더니 얼씨구나! 서버에서 K에 따라서 무려 4~33%의 초 고효율 증가를 보인다!
+0.15점 해서 50.72점이 나올 것으로 예상했으나 실제로는 50.65점에 그쳤다. 아까 0.06점 오른게 좀 후루꾸성이 있었나보다;; 실제 로컬 테스트 결과도 neutral하게 나왔다. 그 쪽으로 자세한 영향은 막판에 체크해봐야 겠다.
K가 작을 떄는 코어코드를 별로 안 타고 주변 코드의 영향을 많이 받는 듯 하다. 관심을 좀 가져줄까? 아쉽게도 K가 작은 경우는 현재도 최적해에 거의 가깝게 나온다;; 관심을 좀 덜 받을듯 하다.
7/2 12:32
어제 밤에는 SA 스케쥴에서 up_prob를 계산하는 부분에서 prev_score=score일때 여러가지로 끼얹어보다가 잘 안됐다. 다시 원래 버젼으로 냈는데 점수가 그대로네....
오늘은 일단 SSE 끼얹어볼 예정이다.
7/3 00:26
SSE 끼얹기는 실패였다. 벡터 연산이 아닌 일반 연산을 크게 크게 하기에는 적합하지 않았던 것 같다. 게다가 쉬프트를 해야하는데 128bit를 단위로 하는 것은 매우 비효율적이었고, 서버가 32bit OS라 더욱더 퍼포먼스에 영향을 많이 받았다.
심한 고생 끝에 결국 다 짜서 서버에서 돌아가게 해 보기는 했으나 이터레이션 수 -30~+5%라는 참담한 성적을 안고 코드 삭제를 결행하였다.
앞으로 전체 shift를 하는 경우가 있으면... 서버가 64비트 OS로 변신하지 않는 이상 무조건 피해야겠다. (로컬은 64비트 OS라 그런지 -5~20% 정도의 속도 향상이 있었다. 그래도 기대 이하.)
그러나 그 와중에 aligned가 dynamic memory에서는 먹지 않는다는 것을 알고 class 밖으로 빼서 이터레이션 수 증가로 약간의 성능 향상을 꾀하였...으나 -0.12점이 되어서 50.53점이 되었다. 예제들은 다들 1~3%씩 더 돌았는데 이상한 일이다.
그 이후, 최후 루프를 한번 정도씩 더 도는 버그를 발견하였다. (신버젼/구버젼에 다른 형태로 존재하였다) - 이터레이션 수에 큰 증가가 있었으며, 대략 0~25% 정도 증가한 것 같다. 평균적으로는 약 15% 정도일까?
1시에 끼얹었는데 50.7점을 넘지 않는다면 다시 클래스 안으로 배열들 넣고 다시 실험을 해봐야겠다 -_-... (근데 그 전에 int grid[102][102]부터 어떻게 제거를 하자)
100개의 데이터로는 각 K마다 예제가 5-6개 정도밖에 나오지 않는다. 게다가 R과 C에 따라서 behavior가 크게 달라진다. 오늘 밤에는 테스트 케이스를 두 배로 늘려 테스트를 해 봐야겠다.
7/4 11:19
일단 50.79는 상당히 높은 점수인듯 하다. 사람들이 잘 못따라온다 음... 별로 한게 없어서 역전당할 가능성은 큰 편이라고 생각한다.
오늘은 위의 '앞으로 할 일'들의 1 2 4번을 처리해야 할 듯 하다. 5번은 힘든 것 같고, 3번은 적용했다가 실패한 상태이다.
일단은 1번부터 시작해야겠다.
7/4 15:17
파트 1 수정했는데 서버에서는 +6%라는 경이적인 속도 증가를 보인다. 다른 부분들도 슬슬 고쳐볼 예정...
그런데 점수는 50.71로 떨어졌다. 5일 묵은 버그 하나를 찾아서 수정해서 보냈는데도 점수는 50.71 그대로이다.
이제 파트 2를 수정해야 할 듯 하다. 그런데 파트 1보다도 난이도가 높아보인다. 어떻게 되겠지... 난이도도 높고 iteration 증가 효과도 커 보인다.
7/6 02:21
계속 거의 같은 버젼에서 로직 말고 코드만 약간씩만 고쳐서 내는데, 50.65~84에서 심하게 흔들린다.
그제 밤에는 심하게 흔들리는 시드에 대해서 100개씩 돌려봐서 나온 답의 유사도를 구했는데, 비슷한 답이 나오는 적이 없다. 아무래도 상태공간이 너무 넓은듯.
그래서 대증요법을 써서 branch의 수를 늘려주었다. 예전에 사용하던 근처로 옮기기 코드를 재발동했는데, 의외로 답이 괜찮다. 특히 문제의 38번 시드 평균이 0.30에서 0.36으로 확 뛰어버렸다.
초기버젼을 냈는데 점수가 0.03 떨어져서 50.75가 되었다. 뭐 오차범위가 워낙 넓으니 그러려니 했다.
나머지 2시간 동안은 여러가지 셋팅으로 돌려봤는데, 의외로 넓은 범위에 대해서 사용이 가능하다. old version의 전 영역에 적용하고 시간에 따라서 이 방법의 적용 범위를 넓어지도록 했더니 젤 괜찮아보인다.
좁은 범위에 적용했을 때 +0.11점 (100개중 15개에만 적용되었는데 이 점수이다!) 이 나왔고, 넓은 범위에 대해서는 적용중이다. 느낌상으로는 +0.15~16점 정도가 나올듯. 이 계산 때문에 iteration 수가 줄어드는 효과는 잘해야 -0.01점이다.
net profit은 0.14점 정도로 예상된다. 어이없이도 std는 거의 줄지 않는다. 흔들리는 범위는 50.80~97 정도가 아닐지. 적용 대상은 겨우 26개이다;;;;
내일 시도해볼 것은, 다른 경우에도 이 방법을 적용하는 것이 될 것 같지만, 전망은 그렇게 좋지 않다 (적용하려면 나머지 경우에 대해서 이터레이션 수를 절반으로 줄여야 하는데, 그럼 점수가 -0.35점 정도가 된다. 이 방법으로 점수를 올려봤자 0.25점을 넘지 않을 것으로 보이니 시도조차 하지 않는 것이 좋을 것이다.) 그냥 new method 적용 범위를 살짝 줄여주는 정도로 만족하자. 그리고 뭔가 다른 적용 방법을 찾아보자.
제출하고 나니 ecv가 50.91까지 올라왔다;;; 몇일만에 1등을 뺏긴거냐 ㅠㅠ 일단 나도 제출했으니 기대를 걸어보자. 50.87이다! ㅠㅠ 10위권과는 차이를 꽤 벌리긴 했지만 1위를 탈환하지 못한 것은 마음이 아프다. 아침에 좀 더 고민해보자.
ps) 확실히 막판인듯... 큐가 8개까지 쌓여있다.
7/6 10:05
로컬테스트는 +0.152점 ㅋ 아침에 보니 ecv가 51.25-_-... tpelkone도 50.89까지 올라왔다. 내 재제출은 50.83. 여전히 오차범위이다.
아침에 각고의 노력(ㅠㅠ) 끝에 전체 시드에 대해 적용하였다. 어느 정도의 iteration 소모는 있지만 실험 결과는 promising하다. 일단 전체 테스트를 돌려보고 있다.
1회 테스트 결과 +0.18점! 범위 평균은 대략 51.06으로 예상되었다. 서밋 결과는 51.09. 그럭저럭 예상범위이며 로컬테스트를 계속 돌려보고 있다.
branch 수가 늘어나서 saturation이 너무 느려지는 문제들이 보인다. 약간의 파라미터 조정이 도움이 될 지도 모르겠다. iteration 수에 대한 imbalance가 있어서, R/C/K에 따라서 살짝 조정해줄지도 모르겠다.
7/6 23:30
중앙에 집중해서 흔들어보는걸 좀 더 주변에 흩어져서 찾아보도록 시스템을 조정했다. 점수가 약간 오르는듯... 서밋 결과는 51.21이다.
7/7 11:47
파라미터 숫자 하나 고쳐서 마지막 서밋~ (51.21->51.11) 인데 실질적으로는 거의 같은 버젼이다.
7/8 2:00
ecv는 최근 3회 서밋이 51.25->12->17 이니 평균이 51.18 이고, 나는 같은 서밋이 51.21->11이라 51.16이다. 실제 결과는 알 수 없을듯... ploh도 막판에 치고 올라와서 3파전이 될 것 같다.
아- 열정이 느껴지는 기록이네요- 전 항상 단순한게 좋은거다..식의 접근이었는데 이런 복잡한 수식을 잘 컨트롤 하는 건 정말 쉬운 게 아닌 거 같아요. 단순히 다양하고 복잡한 수식 적용한다고 잘 나오는 게 아니라 조화롭게 잘 적용해야 할텐데, 이런 부분에서 내공이 크게 갈리고 제 입장에서는 내공이 마니 딸려서 ㅜ.ㅜ 아무튼 R3에서도 탑텐안에 드시고 비행기 타시길~ :)
일루
는 아니고 일기장...
방법 정리버젼은 http://forums.topcoder.com/?module=Thread&threadID=679983&start=0&mc=22 여기로..
이제까지의 스토리~
6/24 - SA를 끼얹어보았다. 생각보다 점수가 잘 나온다.
1 06.24.2010 10:51:43 45.31 C++
6/25 - R/C에 비해서 K가 작을 때는 부분적으로만 테스트하는 루틴을 만들었다.
2 06.25.2010 01:06:32 46.47 C++
3 06.25.2010 06:13:02 46.95 C++
4 06.25.2010 08:16:56 47.35 C++
5 06.25.2010 10:16:57 47.81 C++
6 06.25.2010 12:18:09 48.28 C++
6/26 - 7번 서미션 49.11은 순전히 각 iteration마다 체크하던 getTime을 20회마다 체크하게 바꿔서 그렇다....
원래 K가 작을때 체크하던 루틴은 두번 돌고 그 차이값을 구하는데 그러지 말고 최종 테이블 결과는 어디에 기록하도록 바꿔서 두 배 정도 빨라진 것 같다.
7 06.25.2010 18:40:46 49.11 C++
8 06.26.2010 03:56:40 48.20 C++
9 06.26.2010 06:02:18 48.59 C++
10 06.26.2010 08:05:13 49.45 C++
11 06.26.2010 14:38:23 49.47 C++
6/27 - 이 날은 bitmap이 출동하였다. 각 위치는 5비트를 차지한다. 나중에 (16*현재값) + 주변 갯수 를 세어야 하기 때문에 5비트가 필요하다.
unsigned int 한 자리에 6개의 위치를 저장할 수 있다. 쉬프트를 적절하게 사용하여 계산하는 방법을 고안하였다.
12 06.27.2010 05:35:58 49.54 C++
13 06.27.2010 07:59:58 49.64 C++
14 06.27.2010 12:21:49 49.65 C++
6/28 - 가장 대책이 없던 날. Psyho가 50.25로 한번에 치고 올라온 날이다.
초 최적화를 위해서 __attribute__ 등을 써가며 버둥거렸다 --;
15 06.27.2010 18:25:03 49.73 C++
16 06.28.2010 01:57:28 49.80 C++
17 06.28.2010 04:53:35 49.70 C++
18번 서밋 - 이 날은 나의 SA 인생에서 꽤 중요한 날이 아니었나 싶다. 현재 score가 흔들리는 정도와 실제로 솔루션을 채택하는 확률을 조합하여 SA를 적절하게 돌아가도록 만들었다.
기대대로 상태가 좋아져서 18번 서밋에서 0.07점 올랐지만 사실은 빙산의 일각일 뿐이었다...
18 06.28.2010 07:42:10 49.77 C++
6/29 - 전체 테이블에 대해서 계산할 때만 돌아가던 bitmap을 일부분만 계산하는 루틴에도 들어가도록 했다. 이 당시에는 전체를 계산하는 경우와 일부분만 계산하는 경우가 전체의 절반쯤 되었고, bitmap 적용 후 속도는 약 1.6~7배로 올라갔다.
속도가 2배로 오르면 점수가 0.55점 정도 오르던 시기이니 이 bitmap 사용으로는 점수가 0.2점 정도 오른 것 같다. 또한 bitmap을 5bit에서 4bit만 사용하도록 수정하면서 (주변 갯수를 일단 구하고 내 상태*8을 xor한다. 어차피 갯수가 8의 배수인 경우는 없어지는 경우이니....) 점수가 조금 더 올랐다.
그런데 22번 서밋에서 점수가 크게 흔들리는 문제가 발생하였다. 문제를 분석하던 도중, 18번 서밋에서의 SA 부분에 버그가 있음이 밝혀졌다. 솔루션을 채택하는 확률이 떨어지면 온도를 올려야 하는데, 실제로는 내리고 있었던 것이다. 따라서 중요한 시점에 온도가 확 떨어지면서 iteration 수가 확 줄어드는 문제가 있었던 것이다. 결국 score가 흔들리는 정도로 온도를 조정하는 부분이 워낙 성능이 좋았기 때문에, 솔루션을 채택하는 확률을 보는 부분이 망했어도 그 부분을 가리고 0.07점을 올릴 수 있었던 것이다.
23번 서밋에서 이것을 수정하자 점수가 급상승하면서 50.43에 진입하였다. 당시 1위인 doudouille는 50.45점, 2위였던 Psyho는 50.42점이었는데 Psyho를 밀어내고 2위로 다시 올라갔다. 로컬 테스트 결과 전체 SA 수정 부분의 효과는 0.54점이었다.
이후에는 날씨가 좋은 관계로 iteration 수가 0.5%씩 좋아지는 버젼으로 계속 제출했더니 정말 그만큼만 올랐다...
19 06.28.2010 22:55:20 49.84 C++
20 06.29.2010 01:35:49 49.79 C++
21 06.29.2010 03:54:21 50.25 C++
22 06.29.2010 06:18:33 50.06 C++
23 06.29.2010 08:32:02 50.43 C++
24 06.29.2010 10:32:36 50.44 C++
25 06.29.2010 12:33:19 50.44 C++
6/30 - 가 다시 내렸다. 0.02점 정도는 충분히 오차범위에 든다. 계속 대략 0.5~1%씩 iteration 수가 증가하는 버젼이다. (위에도 그렇지만 간혹 그렇지 않고 같은 버젼 두번 낸 경우도 있다)
26 06.30.2010 08:38:53 50.46 C++
27 06.30.2010 11:27:39 50.44 C++
7/1 - 일기 시작!
28 06.30.2010 18:09:12 50.51 C++
29 07.01.2010 03:08:34 50.57 C++
7/1 09:45
어제 밤에는 일단 conversion lookup table의 크기를 16*16에서 16*16*16으로 늘리고, 한번에 두 개의 아이템씩 보던 것을 세 개의 아이템씩 보게 했다. 대략 전체적으로 3% 정도의 iteration 증가가 있었다. 이렇게 하고 서밋하니 점수가 50.46에서 50.44로 떨어졌다. 50.48 정도를 예측했는데 오차에서 왔다갔다인것 같다.
그 뒤에는 숙원사업인 non-compressed grid를 제거하는 작업 1단계에 들어갔다. 우선 가장 쉬운 부분인 wrap-up이 안 되는 경우를 처리했다. 서버에서 iteration 횟수 +4.1%의 효과가 있었다. new method를 사용하는 경우에만 적용되기 때문에 실제로는 +3% 정도인 것 같다.
시간이 없어서 일단 자고 아침에 서밋하니 50.51점이 나온다. 어제 밤에 안 오른 점수까지 같이 오르는 것같다.
서버 데이터 셋의 stdev를 생각해보면, 여기에는 그리 어려운 데이터가 없어서, +-0.03점 정도의 stddev를 가지는 것 같다. 참고로 50.51x2 버젼의 local stdev는 0.096이고, 문제의 38번 시드를 제외하면 0.059가 된다.
점수대마다의 sensitivity는 다음과 같다.
49점 - iteration doubling : +0.60 (rough)
50점 - iteration doubling : +0.52 (rough)
50.51점 - iteration doubling : +0.46
iteration doubling 시 올라가는 점수가 점수 +1점마다 대략 -0.09점 정도 되는것 같다. 이 추세라면 50.51 + 0.46/0.09 = 55.62점이 점수의 한계치가 된다.
한편 로컬 테스트의 sum(case min)~sum(case max) 추이로 보면
46.58/48.81 -> 47.26/49.18 이 되었으므로 둘 다 linear하게 쭉 올려보면 51.47점이 된다. 로컬 테스트는 시스템 테스트보다 2.8점 정도 낮으므로 더하면 54.27점이 된다.
54~56점 사이가 최적해의 한계치인것 같다!
7/1 16:29
현재 시스템상, 1/3의 확률로는 제거를 시도해보고 2/3의 확률로는 넣기를 시도해본다. 가장 최근 업데이트를 하고 나서 제거를 시도해본 히스토리가 있으면 저장해뒀다가 꺼내쓰자.. 라는 아이디어가 있어서 구현을 해 보았는데 9초 이후의 iteration 수만 10배정도로 폭증--;; 했으나 전체 점수에는 거의 영향이 없었고 오히려 좀 나빠진 것이 중요한 iteration 수를 막 깎아먹었다. 아무래도 L2 cache로 인해서 빅장을 맞는 듯 하다.
아무튼 여기서 교훈은 9초 이후의 iteration은 지금 별 영향을 끼치지 못한다는 것이라서, 여기서 교훈을 얻어서 log(0.2/prob)의 가중치를 0.2에서 0.25로 올리고 서밋했다. 원래는 막판에 하려는 거였는데 일단 눈에 보이니 고쳐서 바로 서밋했는데 점수가 0.06점이나 오른 50.57점이 나왔다! 로컬 테스트를 돌려서 정확한 영향을 측정해야겠다.
앞으로 할 일 -
1) non-compressed grid 제거 작업 part 2 (+2% 예상)
2) non-compressed grid 제거 작업 part 3 (+1%++ 예상)
3) SSE 적용 (instruction 최적화시 +35% 예상)
4) varation이 큰 예제들 살펴보고, 해결 방안을 강구한다.
5) K=2 케이스 최적화 찾기에 대해 고민해본다.
7/1 18:44
코어 코드를 보다가 문득 모두 더하고 >> 를 하면 좋겠다고 생각했다. 고쳐보니 의외로 식이 매우 깔끔하게 나온다. 컴파일러가 처리하기 좋은 형태로... 끼얹어봤더니 얼씨구나! 서버에서 K에 따라서 무려 4~33%의 초 고효율 증가를 보인다!
+0.15점 해서 50.72점이 나올 것으로 예상했으나 실제로는 50.65점에 그쳤다. 아까 0.06점 오른게 좀 후루꾸성이 있었나보다;; 실제 로컬 테스트 결과도 neutral하게 나왔다. 그 쪽으로 자세한 영향은 막판에 체크해봐야 겠다.
K가 작을 떄는 코어코드를 별로 안 타고 주변 코드의 영향을 많이 받는 듯 하다. 관심을 좀 가져줄까? 아쉽게도 K가 작은 경우는 현재도 최적해에 거의 가깝게 나온다;; 관심을 좀 덜 받을듯 하다.
7/2 12:32
어제 밤에는 SA 스케쥴에서 up_prob를 계산하는 부분에서 prev_score=score일때 여러가지로 끼얹어보다가 잘 안됐다. 다시 원래 버젼으로 냈는데 점수가 그대로네....
오늘은 일단 SSE 끼얹어볼 예정이다.
7/3 00:26
SSE 끼얹기는 실패였다. 벡터 연산이 아닌 일반 연산을 크게 크게 하기에는 적합하지 않았던 것 같다. 게다가 쉬프트를 해야하는데 128bit를 단위로 하는 것은 매우 비효율적이었고, 서버가 32bit OS라 더욱더 퍼포먼스에 영향을 많이 받았다.
심한 고생 끝에 결국 다 짜서 서버에서 돌아가게 해 보기는 했으나 이터레이션 수 -30~+5%라는 참담한 성적을 안고 코드 삭제를 결행하였다.
앞으로 전체 shift를 하는 경우가 있으면... 서버가 64비트 OS로 변신하지 않는 이상 무조건 피해야겠다. (로컬은 64비트 OS라 그런지 -5~20% 정도의 속도 향상이 있었다. 그래도 기대 이하.)
그러나 그 와중에 aligned가 dynamic memory에서는 먹지 않는다는 것을 알고 class 밖으로 빼서 이터레이션 수 증가로 약간의 성능 향상을 꾀하였...으나 -0.12점이 되어서 50.53점이 되었다. 예제들은 다들 1~3%씩 더 돌았는데 이상한 일이다.
그 이후, 최후 루프를 한번 정도씩 더 도는 버그를 발견하였다. (신버젼/구버젼에 다른 형태로 존재하였다) - 이터레이션 수에 큰 증가가 있었으며, 대략 0~25% 정도 증가한 것 같다. 평균적으로는 약 15% 정도일까?
1시에 끼얹었는데 50.7점을 넘지 않는다면 다시 클래스 안으로 배열들 넣고 다시 실험을 해봐야겠다 -_-... (근데 그 전에 int grid[102][102]부터 어떻게 제거를 하자)
100개의 데이터로는 각 K마다 예제가 5-6개 정도밖에 나오지 않는다. 게다가 R과 C에 따라서 behavior가 크게 달라진다. 오늘 밤에는 테스트 케이스를 두 배로 늘려 테스트를 해 봐야겠다.
7/4 11:19
일단 50.79는 상당히 높은 점수인듯 하다. 사람들이 잘 못따라온다 음... 별로 한게 없어서 역전당할 가능성은 큰 편이라고 생각한다.
오늘은 위의 '앞으로 할 일'들의 1 2 4번을 처리해야 할 듯 하다. 5번은 힘든 것 같고, 3번은 적용했다가 실패한 상태이다.
일단은 1번부터 시작해야겠다.
7/4 15:17
파트 1 수정했는데 서버에서는 +6%라는 경이적인 속도 증가를 보인다. 다른 부분들도 슬슬 고쳐볼 예정...
그런데 점수는 50.71로 떨어졌다. 5일 묵은 버그 하나를 찾아서 수정해서 보냈는데도 점수는 50.71 그대로이다.
이제 파트 2를 수정해야 할 듯 하다. 그런데 파트 1보다도 난이도가 높아보인다. 어떻게 되겠지... 난이도도 높고 iteration 증가 효과도 커 보인다.
7/6 02:21
계속 거의 같은 버젼에서 로직 말고 코드만 약간씩만 고쳐서 내는데, 50.65~84에서 심하게 흔들린다.
그제 밤에는 심하게 흔들리는 시드에 대해서 100개씩 돌려봐서 나온 답의 유사도를 구했는데, 비슷한 답이 나오는 적이 없다. 아무래도 상태공간이 너무 넓은듯.
그래서 대증요법을 써서 branch의 수를 늘려주었다. 예전에 사용하던 근처로 옮기기 코드를 재발동했는데, 의외로 답이 괜찮다. 특히 문제의 38번 시드 평균이 0.30에서 0.36으로 확 뛰어버렸다.
초기버젼을 냈는데 점수가 0.03 떨어져서 50.75가 되었다. 뭐 오차범위가 워낙 넓으니 그러려니 했다.
나머지 2시간 동안은 여러가지 셋팅으로 돌려봤는데, 의외로 넓은 범위에 대해서 사용이 가능하다. old version의 전 영역에 적용하고 시간에 따라서 이 방법의 적용 범위를 넓어지도록 했더니 젤 괜찮아보인다.
좁은 범위에 적용했을 때 +0.11점 (100개중 15개에만 적용되었는데 이 점수이다!) 이 나왔고, 넓은 범위에 대해서는 적용중이다. 느낌상으로는 +0.15~16점 정도가 나올듯. 이 계산 때문에 iteration 수가 줄어드는 효과는 잘해야 -0.01점이다.
net profit은 0.14점 정도로 예상된다. 어이없이도 std는 거의 줄지 않는다. 흔들리는 범위는 50.80~97 정도가 아닐지. 적용 대상은 겨우 26개이다;;;;
내일 시도해볼 것은, 다른 경우에도 이 방법을 적용하는 것이 될 것 같지만, 전망은 그렇게 좋지 않다 (적용하려면 나머지 경우에 대해서 이터레이션 수를 절반으로 줄여야 하는데, 그럼 점수가 -0.35점 정도가 된다. 이 방법으로 점수를 올려봤자 0.25점을 넘지 않을 것으로 보이니 시도조차 하지 않는 것이 좋을 것이다.) 그냥 new method 적용 범위를 살짝 줄여주는 정도로 만족하자. 그리고 뭔가 다른 적용 방법을 찾아보자.
제출하고 나니 ecv가 50.91까지 올라왔다;;; 몇일만에 1등을 뺏긴거냐 ㅠㅠ 일단 나도 제출했으니 기대를 걸어보자. 50.87이다! ㅠㅠ 10위권과는 차이를 꽤 벌리긴 했지만 1위를 탈환하지 못한 것은 마음이 아프다. 아침에 좀 더 고민해보자.
ps) 확실히 막판인듯... 큐가 8개까지 쌓여있다.
7/6 10:05
로컬테스트는 +0.152점 ㅋ 아침에 보니 ecv가 51.25-_-... tpelkone도 50.89까지 올라왔다. 내 재제출은 50.83. 여전히 오차범위이다.
아침에 각고의 노력(ㅠㅠ) 끝에 전체 시드에 대해 적용하였다. 어느 정도의 iteration 소모는 있지만 실험 결과는 promising하다. 일단 전체 테스트를 돌려보고 있다.
1회 테스트 결과 +0.18점! 범위 평균은 대략 51.06으로 예상되었다. 서밋 결과는 51.09. 그럭저럭 예상범위이며 로컬테스트를 계속 돌려보고 있다.
branch 수가 늘어나서 saturation이 너무 느려지는 문제들이 보인다. 약간의 파라미터 조정이 도움이 될 지도 모르겠다. iteration 수에 대한 imbalance가 있어서, R/C/K에 따라서 살짝 조정해줄지도 모르겠다.
7/6 23:30
중앙에 집중해서 흔들어보는걸 좀 더 주변에 흩어져서 찾아보도록 시스템을 조정했다. 점수가 약간 오르는듯... 서밋 결과는 51.21이다.
7/7 11:47
파라미터 숫자 하나 고쳐서 마지막 서밋~ (51.21->51.11) 인데 실질적으로는 거의 같은 버젼이다.
7/8 2:00
ecv는 최근 3회 서밋이 51.25->12->17 이니 평균이 51.18 이고, 나는 같은 서밋이 51.21->11이라 51.16이다. 실제 결과는 알 수 없을듯... ploh도 막판에 치고 올라와서 3파전이 될 것 같다.
14년 전