SKP Code Sprint 참가 후기
개요
웹 서핑을 하다가 우연히 SKP Code Sprint 페이지를 보게 되었다.
Python으로 지원이 가능하고, 예제 소스도 제공 되었다. 거기다가 상품이 맥북 레티나…
Skein Hash는 처음 들어본지라 참고 Link를 열어보니 NIST SHA-3 algorithm candidate라고 했다. Skein Hash 알고리즘을 분석해 본 것은 아니지만 일단 Round 3까지 올라갈 정도면 hash의 취약성에 관련된 문제는 아닐거라고 제껴 두었다.
검색해야 하는 Search Space의 크기를 계산해 보니, 예제의 첫번째의 경우만 해도 (10+26*2)^4 = 14,776,336이고, 주어진 조건처럼 M이 20까지로 가정하면 제한된 30초 내에 모든 것을 다 계산해 보는 것은 불가능할 것으로 판단된다.
그리고 Hash 특성상 계산값을 저장해 놓았다가 활용하는 방법도 비효율적이다. 결론은 누가 제한된 시간내에 빨리 계산을 할 것인가로 결론이 나지 않을까? 결론은 Thread나 Process 모델로 만들어야겠다.
외부 서버와 접속해서 분산 처리는 허용이 안 되고, Thread나 Process 형태로 만드는 것 가능하다고 한다.
문제
개요
NIST에서는 2012년 SHA-3 알고리즘으로 Keccak을 발표했다. 그러나 Keccak 대신에 Skein이 SHA-3 알고리즘으로 선택된 평행우주가 있었다. 이 평행우주에서는 BitCoin과 비슷하지만 약간 다른 ‘실타래’란 것을 전 세계인의 통화로 하고 있었다. 하나의 실타래는 길이가 M인 문자열 두개로 이루어져 있으며, 모든 실타래들은 제각기 다른 값어치를 가지고 있다. 길이 M인 두 개의 문자열 S1, S2가 있다고 할 때, 이 두 문자열을 꼬아서 만든 실타래의 값어치는 다음과 같이 계산할 수 있다.
- 값어치 =
Red(Hash(S1) ^ Hash(S2)) + Blue(Hash(S1) ^ Hash(S2)) - Red(H) = H의 prefix중에서 0만으로 이루어진 가장 긴 것의 길이를 L이라고 정의하면,
Red(H) = L^2 * R - Blue(H) = H의 suffix중에서 1만으로 이루어진 가장 긴 것의 길이를 L이라고 정의하면,
Blue(H) = L^2* B
예를 들어 S1 = “B1d”, S2 = “AI1”, R=1, B=1이라고 할 때
Hash(S1)= “01000011110010001111001000100111…1101001101101110010101111001100”Hash(S2)= “01111001100001010100101101110111…0000110010010001101010000110011”
이 두 값을 exclusive-or 한 값은 다음과 같다.
Hash(S1) ^ Hash(S2)= “00111010010011011011100101010000…1101111111111111111111111111111”
이 값의 prefix중 0으로 이루어진 가장 긴 것은 “00” 이므로, Red 값은 2^2*1=4가 되고, suffix중 1로 이루어진 가장 긴 것은 “1111111111111111111111111111” 이므로 28^2*1=784 가 되어 결국 이 실타래의 값어치는 788이 된다.
출제 문제
당신은 원래 N 개의 실타래를 갖고있었지만, 실수로 이 문자열들의 뒷부분을 잃어버렸다. 이 문자열들을 복원해서 만들 수 있는 가장 높은 값어치의 문자열을 찾는 프로그램을 작성하시오. Skein 알고리즘은 1.3 버전에 소개된 알고리즘 중에서 Skein-256을 사용한다. 또한 Python 3에서는 PySkein 라이브러리가 해당 hash 함수를 지원한다.
입출력 형식
입출력 모두 표준 입출력을 사용한다. 먼저 입력의 첫 줄에는 네 개의 정수 N, M, R, B가 공백을 사이에 두고 하나씩 주어진다.
그 다음 N 개의 줄에는 복원해야 할 문자열 2개가 공백을 사이에 두고 주어진다. 각 문자열은 대소문자 및 숫자만을 포함하고 있다.
- 1 ≤ N ≤ 30
- 1 ≤ M ≤ 20
- 0 ≤ R, B ≤ 30000
출력은 복원한 문자열 N개의 쌍을 한 줄에 한쌍씩 출력한다.
한 쌍의 문자열은 한 칸의 공백을 사이에 두고 출력되어야 하며, 각 문자열은 대소문자 및 숫자만을 포함하고 있어야 한다. 또 입력으로 주어진 문자열을 prefix로 해야 한다. 주어진 출력 형식 및 조건을 만족하지 않는 문자열을 출력하는 경우 해당 데이터에서의 점수는 0점이 된다.
입력 예제
3 3 1 1
B A
C De
FFF FF
출력 예제
아래 출력 예제의 점수는 세 쌍의 실타래의 가치 (B1d AI1 = 788, CBG DeF = 400, FFF FFF = 65536)를 합한 66724이다.
B1d AI1
CBG DeF
FFF FFF
제출 방법
주어진 입력이 주어졌을 때 출력하는 프로그램의 소스코드를 웹 사이트를 통해 제출한다. 제출된 코드는 실행 시 다음 조건을 만족해야 한다.
하나의 테스트 케이스당 30초 이내에 결과가 나와야 하며, 그 이상 시간이 걸리는 경우 해당 데이터에서의 점수는 0점이 된다.
하나의 테스트 케이스당 1GB 미만의 메모리를 사용해야 하며, 그 이상의 메모리를 사용하는 경우 해당 데이터에서의 점수는 0점이 된다. (메모리 사용량 계측은 실행환경에 따라 정확하지 않을 수 있으므로, 좀 더 적은 메모리만 사용하는 것을 권장합니다)
Java/Scala 사용시 메인 클래스 이름은 Main으로 작성해야 한다.
평가
각 테스트 케이스에서의 점수는 다음과 같다. 참가자가 제출한 답안의 점수가 Yours, 모든 제출 답안 중 해당 테스트 케이스에서 나온 가장 좋은 점수를 Best라고 할 때, 참가자의 점수는 다음과 같다.
(Yours/Best)^2 * 100
각 테스트 케이스별 점수의 총합이 해당 제출 답안의 점수가 된다. 참가자의 점수는 참가자가 낸 가장 마지막 제출 답안의 점수로 한다.
문제 풀이
Python 버전
랜덤 시도 버전
전체 Search space를 다 찾는 것이 불가능하면 굳이 순차적으로 다 찾을 필요 없이 임의로 문자열을 만들어 검사해 보는 게 좋지 않을까?
그래서 나온 첫번째 소스
str + ''.join(random.choice(seed) for _ in range(m-len(str)))
임의로 데이타를 만들어 계산 후에 가장 높은 값을 가진 String을 저장했다가 제한 시간인 30초가 되는 시점에 그 중 가장 높은 값들을 출력한다.
제출된 소스는 bot이 자동으로 테스트 셋을 계산해서 토요일 정오, 일요일 정오 두차례 순위 발표를 했다.
마감까지는 시간이 많이 남은지라 제출된 프로그램이 많지 않았다. 제출된 프로그램 중 3위였고, 432점이었다. 1위은 2000점 만점이었다. 점수 계산이 (Yours/Best)^2 * 100으로 공지가 된지라, 점수로부터 다음과 같은 사실을 알게 되었다.
- 총 테스트 세트의 갯수는 20개이다.
- 1위는 모든 test case에서 가장 높은 점수를 받았다.
- 432점은 대략적으로 모든 case에서 절반정도의 점수를 얻었다
몇가지 더 유추한 사실은 아래와 같다.
- 테스트 셋 중에서 전체를 다 search 할 만큼 적은 데이타 set도 존재할 수 있다.
- 좀 더 최적화 할 여지가 있을 수도 있다
Generator 버전
메모리 제약상(1G) 모든 케이스를 다 만들어서 저장할 수 없으니 python의 Generator를 만든 후에, CPU time이 허용하는 동안 시도를 하게 하자.
itertools.product(seed,repeat=2*M-len(a)-len(b))
각 라인 별로 Generator를 만든 후에 CPU 허용 시간 안에서 추출한 후 계산해서 제일 높은 값을 저장하기로 했다. 이 방식이 첫번째 방법에 비해 결과값이 높았다. 맥 미니에서 30초 동안 계산한 case를 출력해 보니 544,859회였다. 전체 계산해야 하는 양에 비하면 많이 부족한 수치이다.
채점을 하는 컴퓨터가 Xeon이라고 했으니 thread 모델로 만들면 좀 더 계산을 많이 하지 않을까? Python은 Global Interpreter Lock방식이라 계산 의존적인 프로그램에는 thread로 만드는 것은 성능 향상에 아무런 도움이 되지 않는다. 그래서 멀티 프로세스 모델로 바꾸었다.
로컬로 수행을 해 보니 두번째 버전에 비해서 좀 더 계산량이 늘어났다. 답안 제출 사이트에 프로그램을 제출해 봤더니 전부 0/20으로 출력이 되었다. 채점 서버가 어떻게 구성이 되었는지 모르는 상태라, 멀티 프로세스 형태의 프로그램을 허용하지 않는 것으로 결론을 냈다.
Python 최적화
Python 소스를 좀 더 최적화할 수 있는 방법이 없을까? Hash에 관한 문제라, 알고리즘 측면에서는 최적화할만한 여지가 별로 없다. 그래서 Python의 각 문장별로 속도가 오래 걸리는 부분을 프로파일링을 했다.
import cProfile
...
cProfile.run("main()")
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 29.300 29.300 <string>:1(<module>)
1 0.000 0.000 0.000 0.000 codecs.py:297(decode)
1 0.000 0.000 0.000 0.000 codecs.py:309(getstate)
1622320 3.042 0.000 7.837 0.000 codesprint.py:21(hash)
1618116 3.801 0.000 3.801 0.000 codesprint.py:24(find_consecutive_zero_one)
1618116 4.976 0.000 19.213 0.000 codesprint.py:41(compute)
1 8.483 8.483 29.300 29.300 codesprint.py:60(main)
1618116 1.487 0.000 1.487 0.000 {built-in method bin}
1 0.000 0.000 29.300 29.300 {built-in method exec}
12 0.000 0.000 0.000 0.000 {built-in method len}
4139174 0.665 0.000 0.665 0.000 {built-in method next}
4 0.000 0.000 0.000 0.000 {built-in method print}
1622320 1.349 0.000 1.349 0.000 {built-in method skein256}
1379726 0.284 0.000 0.284 0.000 {built-in method time}
1 0.000 0.000 0.000 0.000 {built-in method utf_8_decode}
6 0.000 0.000 0.000 0.000 {method 'append' of 'list' objects}
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
1622320 1.340 0.000 1.340 0.000 {method 'encode' of 'str' objects}
1622320 2.105 0.000 2.105 0.000 {method 'hexdigest' of '_skein.skein' objects}
3236230 0.655 0.000 0.655 0.000 {method 'join' of 'str' objects}
4 0.000 0.000 0.000 0.000 {method 'readline' of '_io.TextIOWrapper' objects}
4 0.000 0.000 0.000 0.000 {method 'split' of 'str' objects}
3 0.000 0.000 0.000 0.000 {method 'strip' of 'str' objects}
1618116 1.113 0.000 1.113 0.000 {method 'zfill' of 'str' objects}
우선 처음과 끝의 0, 1의 숫자를 세는 용도로 사용된 regular expression을 제거했다.
pattern = re.compile(r"^(0*).*?(1*)$")
Search 갯수가 544,859에서 1,706,294로 늘었다. 다른 Python 최적화 방법을 라인 별로 적용을 했다.
- a+b 대신에
"%s%s" % (a,b)로 수정 len(str)값을 미리 계산해 두고, 저장해 둔 값 사용- 함수의 호출 overhead 줄이기 위해 inline 화
- 각 라인별 실타래 계산 시, 첫번째 Hash를 저장해 두고 이용하기
- 수행 시간 계산 overhead를 줄이기 위해, time 계산을 100번 단위로 수행하기
문제는 Python 최적화 문제로 바뀌었다.
일요일 정오에 2차 중간 순위 발표가 났다. 10위이고, 점수는 349.46. 테스트 케이스는 20/20으로 모두만족했고, Python으로 시도할 수 있는 최적화는 다 해 본 것 같은데 여전히 순위권에서 멀다. 알고리즘은 대동소이 할 것이고, 최종 순위는 언어별 속도차와 누가 얼마나 최적화했는지에 따라서 결정될 것 같다. Script 언어 특성 상, cpu 계산이 많이 요구되는 작업은 느릴 수 밖에 없는데 Python은 순위권에 들어갈 수 없다는 생각이 들었다.
C++
포기하고 구경이나 할까 하다, C++과 Python이 얼마나 차이가 날까 궁금해졌다. Python을 C++로 포팅해 보기로 했다.
오랫만에 쓰는 C++은 익숙하지가 않았다. C++ 11은 언제 나온 Spec이며, compiler가 어디까지 지원되는지도 모르겠지만 찾아볼 여유가 없었다. 메모리 제한이 1G니, 메모리는 free할 필요가 없이 다 할당해서 써도 상관 없고, 작성해둔 Python 코드가 있으니 프로그램 포팅은 어렵지 않았다.
C++로 만든 버전과 Python의 수행 속도 비교
- C++ - 2,262,285
- Python - 438,190
Python 버전은 최적화를 했음에도 불구하고, C++이 훨씬 빠르다.
수정한 C++ 버전을 채점 서버에 제출했다. 마감 시간이 얼마 안 남은지라 응모작이 몰려 서버가 과부하 상태였다. 제출한 지 1시간 가량 지난 후 20/20으로 결과가 나왔다.
Thread 버전으로 만들어서 응모를 해 보고 싶은데, 서버 대기열이나 시간 관계 상 불가능할 것 같다1. 같은 스트링의 hash 값이 같은 것을 감안하여, A, B 중 하나가 다른 스트링의 부분 집합이면 같은 스트링을 만들어서 시도하는 룰을 더 추가했다. 혹시라도 테스트 케이스에 그런 경우가 있고, R이 0이 아니라면 다른 String에 비해 점수가 높다.
마감을 2시간이 남지 않은 상태에서 소스를 제출했다. 서버에 심사 Queue가 엄청나게 밀려 있어 마감까지 결과가 나오지 않을 수도 있을 것 같았다.
중복 제출이 많아서 선량한 제출자가 피해를 보는 경우를 방지하기 위해 채점 서버 세대 중 한대는 30분 이내에 다른 제출이 없었던 참가자의 답안을 우선적으로 채점하도록 하는 운영 지침의 변경으로 인해 50분 정도 지난 후에 20/20으로 나왔다.
후기
- Thread 버전으로 만들었으면 좀 더 점수가 높았을텐데, 서버에서 지원되지는 확인할 시간이 부족했다
- Python이 CPU를 많이 쓰는 작업에는 확실히 느리구나
- 처음부터 C++로 만들었으면 좀 더 최적화 할 수도 있었을텐데… 하지만 C++로만 응모를 하게 했으면 참여를 하지 않았을 듯
- 코딩은 역시 Python으로 하는 것이 즐겁구나
- 중간 등수 공개를 두차례만 하지 말고, 실시간으로 했으면 더 재밌었을 것 같다
- C++를 안 쓴지 오래되었는데, 그 사이 C++의 제공 라이브러리도 많이 좋아졌구나.
총점을 1점 이상 획득한 49명 중에 15위. 1위 점수가 1971점인데 획득점수는 389.68점이었다.
소스가 공개된 1-3위 C++ 소스를 보니 다음의 방법으로 최적화를 했다.
- Rotation code를 assembly 를 써서 hash 최적화
- 메모리 1G를 이용해서 hash 값을 저장하고 재활용
- 실타래 값 계산은 빠르게 하기 위해 hash의 prefix, postfix 값으로 dictionary를 만들어서 그 값에 해당하는 string에 대해서 계산
채점 서버에서 Thread나 Multi Process는 지원을 하지 않았는지 관련 기법을 쓴 코드는 보이지 않았다. Hash 값을 prefix, postfix 별로 분리해서 저장하는 방식은 참신했다.
-
나중에 facebook 후기로 확인한 바로는 -lpthread option이 지정되지 않아서 thread 버전은 compile이 안 되었다고 한다. ↩