주말에 faebook 퍼즐을 풀어 봤다. 연습문제로 평가 로봇이 어떻게 동작하는지 확인 한 다음에…

한문제 한문제씩 풀고 있는 찰라… 정확한 계산값이 나왔는데도 로봇이 reject을 하는 경우가 발생했다. 문제는 바로 아래의 문제인데..

http://www.facebook.com/careers/puzzles.php?puzzle_id=17

뭐 문제를 읽어보면 알겠지만 사전 하나 주어지고, 이 사전을 가지고 최소의 edit distance를 구하는 문제였다. edit distance 구하는건 눈 감고도 하는 경지가 다다른 바.. Python으로 빨리 코딩하고 메일을 날렸으나.. 결과는 fail이였다.

facebook 평가봇의 특징은 왜 fail이 났는지 알려주지 않는다는 것인데… 허허 ㅠㅠ

그래서 관련 포럼을 찾아봤는데, 여기선 사람들이 엄청난 문자열을 가지고 test case를 만들어서 돌려보고 있었다. 그런데도 대부분 10초 이내로… 떨어지는 것을 목격하고 도전하고 싶은 마음에.. 알고리즘 튜닝 작업과 Python으로 짠 코드를 C++로 옮기기 시작했다.

여기서 제공한 테스트 문자열은.. 아래와 같다.

$ cat 187.in
orem ipsum dolor sit amet consectetur adipiscing elit nteger imperdiet elit et libero commodo et convallis est ultrices raesent faucibus ligula ullamcorper urna pellentesque faucibus liquam ultrices purus sit amet tellus malesuada malesuada hasellus varius faucibus nisl congue placerat mi suscipit vitae ivamus eu lorem mauris a elementum erat nteger a nisl sollicitudin mauris facilisis vehicula quis non erat tiam sit amet porta justo usce eget nisl ipsum am a ante neque egestas rhoncus urna orbi lectus lorem vehicula quis commodo sed scelerisque non diam enean enim quam sollicitudin vel dignissim et feugiat in risus orbi gravida urna in neque sollicitudin elementum nteger ut tortor lacus sed aliquam ipsum usce convallis purus at lobortis accumsan magna odio blandit orci sit amet semper ligula tortor sit amet nisi ellentesque luctus nisi ut placerat dictum massa libero suscipit mi id ullamcorper purus arcu at nunc t ut arcu orci

$ md5sum 187.in
c95a3a404b21207bfb80d7f4bbd545a5 187.in

$ time ./breathalyzer 187.in
187

real 0m13.414s
user 0m13.385s
sys 0m0.032s

$ cat 63.in
rem ipsum omnium vivendum eu nam vel rebum paulo ut bique epicurei mandamus nec ea odio saepe propriae at sit uod legere petentium eum ex ex soluta accommodare definitionem vim eam sensibus inimicus in el mutat inermis incorrupte ea has eu adhuc homero habemus invidunt aliquando no sea t idque insolens voluptaria eos pri ei nullam nostrud aliquando

$ md5sum 63.in
41ff40e33949652c29c2aac8ade4dad4 63.in

$ time ./breathalyzer 63.in
63

real 0m4.834s
user 0m4.808s
sys 0m0.024s

$ cat 12.in
s a service to its users acebook would like to detect when wall posts are so besotted with errors that they cannot possibly be what the user meant to express he aforementioned wall post would be carefully preserved in a jar for future reference and its author requested to perform an online breathalyzer test for sobriety ou are challenged to write a program that can take a body of text and determine how many mistakes have been made in its composition peed and efficiency are paramount as this puzzle has restrictive bounds that may be narrower than prior puzzles

$ md5sum 12.in
07413e09f167b8d9bd8d40d8c3e96e8e 12.in

$ time ./breathalyzer 12.in
12

real 0m0.873s
user 0m0.856s
sys 0m0.016s

$ cat 4.in
xthis xsentence xis xperfectly xgood

$ md5sum 4.in
df631952b1ed2bd1928588e8ce674719 4.in

$ time ./breathalyzer 4.in
4

real 0m0.883s
user 0m0.856s
sys 0m0.028s

 

4.in의 경우 내가 Python으로 제작한 코드는 1분이 넘게 나왔다. 허걱..ㅠㅠ

동일한 알고리즘으로 C++로 제작한 놈의 결과는 아래와 같다. 거의 위에서 test case를 제공한 사람의 퍼포먼스와 비슷하게 나왔다. 그렇지만 같은 퍼포먼스에 만족할 내가 아니지.. ㅋㅋ

 

chairservice-lm:facebook heewon$ time ./breathalyzer-slow 4.in
4

real    0m0.818s
user    0m0.667s
sys     0m0.029s

 

그래서 알고리즘 튜닝을 좀 해봤다. edit distance의 최소 값을 구하는데 모든 단어를 전부다 구하기 보다는 중간에 싹수가 노란 놈들을 리턴시켜 버리는 early termination 버전으로 고쳤다. 

그 결과는 아래와 같다. 거의 퍼포먼스가 2배로 향상 되었다.

chairservice-lm:facebook heewon$ time ./breathalyzer 4.in
4

real    0m0.482s
user    0m0.340s
sys     0m0.023s

 

이 알고리즘 튜닝 차이는 문자열이 길어질수록 커진다.

chairservice-lm:facebook heewon$ time ./breathalyzer-slow 63.in
63

real    0m5.021s
user    0m4.885s
sys     0m0.042s

chairservice-lm:facebook heewon$ time ./breathalyzer 63.in
63

real    0m1.970s
user    0m1.795s
sys     0m0.033s

 

그럼 가장 긴 문자열의 경우…

chairservice-lm:facebook heewon$ time ./breathalyzer 187.in
187

real    0m5.190s
user    0m4.999s
sys     0m0.041s

 

chairservice-lm:facebook heewon$ time ./breathalyzer-slow 187.in
187

real    0m13.060s
user    0m12.780s
sys     0m0.085s

 

이렇게 나올 정도면 평가 로봇이 내 프로그램이 느리다고 reject해 버리는 사건은 일어나지 않을 듯 하다.

물론 Python도 최적화 하기 나름이겠지만, 사실 Python으로 최적화 하는 방법을 모를 뿐더러, 스크립트 랭귀지는 그저 손 가는데로 코딩해서 프로토타입을 빨리 보는게 목적이라 생각하는바 최적화 하는법을 배우고 싶지도 않다. ^^;

다시 메일 올려 보자.. 이번에는 리젝되지 않길 기도하면서… ㅋ

 

ps. 그런데, 포럼 리스트를 보니 엄청나게 빠르게  계산되는 사람들도 있더라. 머리에 떠오르는 몇몇 휴리스틱 방법이 있기는 한데.. 또 적용 해봐야 겠군. ㅋ

Facebook Puzzle 풀기 by from __future__ import dream is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.