[Swift]Random Surfer Trick 동작 확인

이전 포스팅에서 Random Surfer Trick을 직접 구현해 보았다(https://taeminator1.tistory.com/39). 

이번 포스팅에서는 실제 출력된 결과를 바탕으로 분석을 해보려고 한다. 이후 등장하는 표의 예제 결과는 repeatNumber를 10만으로 하고(실제 예제에서는 100만으로 하였지만 백분율이어서 10을 나눠 10만으로 표기하였다), surfPossiblity를 15로 설정한 결과이다. 

repeatNumber(1000, 10000, 100000)에 따른 실행 결과(시작 인스턴스: p0, surfPossiblity: 15)

먼저 실행 횟수에 따라 결과에 차이가 있었다. 1000번을 반복할 경우, 실행할 때마다 변화율의 차이가 심했지만, 실행 횟수가 증가할수록 변화율에 큰 변화가 없었다. 변화율의 관점에서 봤을 때, 100000번 정도가 적당한 것으로 판단되어 이후 실행부터 repeatNumber를 100000으로 고정하겠다. 

시작 인스턴스(p0, p5, p15)에 따른 실행 결과(surfPossiblity: 15, repeatNumber: 100000)

다음은 시작 인스턴스에 따른 변화율 차이다. 시작 인스턴스에 따라서도 큰 변화가 없다고 판단되어 이후 실행부터 p0로 고정하겠다. 

surfPossiblity(100, 15, 10)에 따른 실행 결과(시작 인스턴스: p0, repeatNumber: 100000)

다음은 surfPossiblity에 따른 차이를 살펴보겠다.

먼저 첫 번째 표인 surfPossiblity가 100인 경우를 생각해보면, 해당 페이지의 다음 페이지를 참조하는 페이지로 선정하지 않고 100% 무작위로 선정되는 경우이다. 각 페이지 별로 실제 결과를 보면, 6250(100000 / 16) 근처인 것을 알 수 있다.

그리고 세 번째 표인 surfPossiblity가 0인 경우는, 다음 페이지가 무작위로 선정되는 것 없이 참조되는 페이지가 다음 페이지로 선정되는 경우이다. 해당 값을 정확히 산출하긴 어렵지만, 반복 수행 시에도 같은 값을 유지하는 걸 확인할 수 있었다. 

마지막으로 가운데 표인 surfPossiblity가 15인 경우를 살펴보자. 해당 경우는 예제와 동일한 조건으로 수행되었는데, 변화율의 차이가 심한 것들이 다수 있다. 차이가 약 0%부터 약 100%까지 다양하게 존재하였다. 몇 가지 항목에 대해 정리를 해보자면, 

• 참조 횟수에 대한 내림차순 정렬 시
  • 예제 결과: p14 -> p15 -> p0 -> p5, p9 -> p4 -> p6 -> p1, p2, p3, p8 -> p7, p10, p11, p12, p13
  • 실제 결과: p14 -> p9 -> p15 -> p5 -> p0 -> p8 -> p6 -> p4 -> p1 -> p2 -> p3 -> p12 -> p10 -> p13 -> p11 -> p7
• 차이에 대한 오름차순 정렬 시(절댓값)
  • p2(0) -> p1(0) -> p3(1) -> p6(5) -> p14(8) -> p5(19) -> p4(26) -> p15(32) -> p9(34) -> p8(39) -> p0(55) -> p7(80) -> p11(89) -> p13(90) -> p10(90) -> p12(91)

참조 횟수에 대한 내림차순 정렬은 어느 정도 차이가 있지만 상중하의 크게 세 부분으로 나누면, 상위 5개의 집합은 동일하고, 중위 6개의 집합도 동일하다. 나머지 하위 5개의 집합도 당연히 동일하다. 전체적으로 비슷한 양상을 보인다. 

차이에 다른 오름차순 정렬에서는 차이가 많이 심한 것도 있는데, 차이가 가장 심한 5개(p12, p10, p13, p11, p7)는 참조 횟수가 가장 적은 5개와 정확히 일치한다(밑줄). 해당 사항을 고려하면 참조 횟수가 적어, 적은 오차에도 차이(용인될 만한 차이인지는 확인이 필요하다)가 심해진 것이라고 생각할 수도 있다. 

 

몇 가지 이해할 수 없는 수치들을 아래 표에 표시해 보았다.  

예제 결과

먼저 p0에 대한 결과이다. 예제를 살펴보면, p14는 p15만을 참조하고 p15는 p0만을 참조하기 때문에 간단히 계산해 볼 수 있다(정확하진 않지만 경향은 살필 수 있을 것이다). p14의 예제 결과 15000에 0.85(무작위 참조 가능성이 15%이므로 100에서 15를 뺀 값)를 곱해 12750을 얻을 수 있는데, 이는 p15의 14000과 유사(10% 차이)하며, 같은 방식으로 14000에 0.85를 곱해 11900을 얻을 수 있는데, 이는 p0의 13000과 유사(9% 차이)하다. 

하지만 실제 결과에서는, p14의 참조 횟수 16248에 0.85를 곱해 13810.8을 얻을 수 있고, 이는 p15의 9542의 값과 약 30%나 차이가 난다. 그리고 p15의 참조 횟수 9542에 0.85를 곱해 8110.7을 얻을 수 있는데, 이 역시 p0의 5904와 약 30%가 차이 난다. 

 

두 번째로 p7에 대한 결과도 이해하기 힘들다. p7의 경우에도 예제 결과가 2000인 것에 비해, 실제 결과는 3595로 약 80% 차이가 난다. p6가 참조하는 페이지가 3개이고 그중 p7은 오직 p6에 의해서만 참조되므로 p6의 예제 결과 값 5000에 0.85 * 1 / 3(참조하는 페이지 세 개 중 하나)을 곱해주면, 약 1416.6이 나오는데 이는 p7의 2000과 약 40% 차이가 난다. 반면에 p6의 실제 결과 값 5252에 0.85 * 1 / 3을 곱해주면, 약 1488.1이 나오는데 이는 p7의 약 140%가 차이 난다. 

 

마지막으로 예제 결과와 실제 결과의 p10, p11, p12, p13의 값 차이가 심한 것이다. 예제 결과는 2000인데, 실제 결과는 약 3803이고 이는 약 90%의 차이다. 물론 앞서 말한 것처럼 횟수가 적어 오차가 심하게 난 것일 수도 있지만, 두 배 가까이 차이 나는 걸로 봐서 다른 문제가 있는 것 같다. 

 

예제와 실제 결과의 차이로 미루어 몇 가지 검토해 볼만한 사항들이 있다. 

1. 당연히 나의 알고리즘 점검이다. 존 매코믹의 "미래를 바꾼 아홉 가지 알고리즘"에서 인용한 대로 최대한 구현하려고 노력하였지만, 어딘가 실수가 있을 수도 있다. 
2. 이해하기 힘든 것 중 두 번째와 세 번째의 경우 값 자체가 작다는 공통점이 있다. 예제 결과의 경우 약 2000이고 실제 결과의 경우 3500과 3900 사이의 값이다. 이것으로 미루어 보아, 예제 결과를 도출한 알고리즘과 실제 알고리즘의 차이가 있을 가능성이 크고 그 차이는 적게 참조하는 값에 더 치명적으로 작용할 수 있다. 

재미있는 책을 읽게 되어 호기롭게 알고리즘을 구현하였지만, 결과가 꽤 달라 아쉽다. 하지만 비슷한 부분도 꽤 많았고 실제로 페이지들이 어떻게 목록화되는지 어렴풋이나마 감을 잡을 수 있어 좋은 경험이었다.