일단 skein 해시를 깨기 힘들다고 가정한다면, 아래와 같은 방법이 제일 기본적인 접근 방법이 됩니다.
//Array1[] = S1을 prefix로 하는 스트링//Array2[] = S2를 prefix로 하는 스트링 intN=Array1.size(),M=Array2.size();for(inti=0;i<N;++i){for(intj=0;j<M;++j){hash_value=get_hash(Array1[i])^get_hash(Array2[j]);score=calcScore(hash_value);}}
위의 알고리즘은 get_hash()를 2 * N * M번, calcScore()를 N * M번 수행하는 코드입니다. N과 M이 조금만 커져도 연산횟수가 급격하게 증가하는 것을 볼 수 있습니다. 메모리를 조금 더 사용하면 연산횟수를 줄일 수 있습니다.
//Array1[] = S1을 prefix로 하는 스트링//Array2[] = S2를 prefix로 하는 스트링 intN=Array1.size(),M=Array2.size();//hash_array1[] = Array1[]의 get_hash()값을 저장하는 배열//hash_array2[] = Array2[]의 get_hash()값을 저장하는 배열for(inti=0;i<N;++i)hash_array1[i]=get_hash(Array1[i]);for(inti=0;i<M;++i)hash_array2[i]=get_hash(Array2[i]);for(inti=0;i<N;++i){for(intj=0;j<M;++j){hash_value=hash_array1[i]^hash_array2[j];score=calcScore(hash_value);}}
이제 get_hash() 함수는 N + M번만 수행합니다. 하지만 calcScore()는 여전히 N * M번 수행하네요. 물론 calcScore()는 최대 비트수인 256번까지만 수행하고, 평균적으로 lg(N*M)정도의 연산만을 수행합니다. 그래도 N과 M이 1만을 넘어가면 1억번 이상의 연산을 필요로 하지요.
설명의 편의를 위하여 B = 0인 데이터를 예로 들겠습니다. 그러면 각 테스트 케이스의 점수는 hash xor을 계산했을 때, 'prefix가 0인 문자열의 길이가 L'일 때, L^2 * R이 됩니다.
hash_array1[x]가 0..으로 시작하고, hash_array2[y]가 1..로 시작한다면, 이 두 값의 xor은 1로 시작하기 때문에 점수가 0점이 됩니다. 즉 calcScore()를 수행할 필요가 없는 것이지요.
앞에서 5자리가 일치하는 경우에만 calcScore()를 계산하도록 만들면 아래와 같은 코드가 됩니다.
//Array1[] = S1을 prefix로 하는 스트링//Array2[] = S2를 prefix로 하는 스트링 intN=Array1.size(),M=Array2.size();//hash_array1[] = Array1[]의 get_hash()값을 저장하는 배열//hash_array2[] = Array2[]의 get_hash()값을 저장하는 배열//hash_index1[32][]: hash_index1[0][]에는 00000으로 시작하는 hash_array1의 index들을 저장하고, hash_index1[1][]에는 00001로 시작하는 hash_array1의 index들을 저장합니다. 같은 방법으로 모든 hash_array1을 저장할 수 있습니다.for(inti=0;i<N;++i){hash_array1[i]=get_hash(Array1[i]);//int prefix_s1 = hash_array1[i]의 앞 5자리hash_index1[prefix_s1].push_back(i);// 인덱스를 저장합니다. }for(inti=0;i<M;++i)hash_array2[i]=get_hash(Array2[i]);for(intj=0;j<M;++j){//int prefix_s2 = hash_array2[j]의 앞 5자리for(inti=0;i<hash_index1[prefix_s2].size();++i){intindex=hash_index1[prefix_s2][i];hash_value=hash_array1[index]^hash_array2[j];score=calcScore(hash_value);}}
prefix_s2 = 00010 이라고 한다면, Array1의 hash값이 00010으로 시작되는 인덱스에 대해서만 calcScore()를 수행합니다. 앞의 5자리가 같은 경우에만 비교를 하게 되므로, 평균적으로 N * M / 32 번의 calcScore()를 수행하지요. 위의 코드에서 5자리에 대해서만 체크를 했는데 자리수가 많아질수록 연산 횟수는 줄게 됩니다.
하지만 줄어드는 연산 횟수에 비례하게 메모리를 많이 사용하게 되기 때문에 저는 20자리에 대해서 체크를 하였습니다. 평균적인 calcScore()는 N * M / 100만 정도가 되고, 이 방법으로 N과 M을 30만까지 계산할 수 있었습니다.
위에서는 B = 0인 데이터를 기준으로 설명했지만, B > 0인 데이터에서는 suffix를 가지고 같은 방식으로 계산합니다. (suffix는 1로 끝나야 하기 때문에 00110으로 끝나는 스트링은 11001로 끝나는 스트링과 calcScore()를 수행하면 됩니다.)
이상 메인 알고리즘에 대한 설명이었습니다. :) 소스코드를 최적화 하면서 N과 M을 늘려나가면 점점 답이 좋아지는 것을 확인할 수 있습니다.
astein
안녕하세요. Astein입니다. 어쩌다보니 순위권에 들게 되어 Codesprint Round 1 간단 후기를 남기게 되었습니다.
일단 skein 해시를 깨기 힘들다고 가정한다면, 아래와 같은 방법이 제일 기본적인 접근 방법이 됩니다.
위의 알고리즘은 get_hash()를 2 * N * M번, calcScore()를 N * M번 수행하는 코드입니다. N과 M이 조금만 커져도 연산횟수가 급격하게 증가하는 것을 볼 수 있습니다. 메모리를 조금 더 사용하면 연산횟수를 줄일 수 있습니다.
이제 get_hash() 함수는 N + M번만 수행합니다. 하지만 calcScore()는 여전히 N * M번 수행하네요. 물론 calcScore()는 최대 비트수인 256번까지만 수행하고, 평균적으로 lg(N*M)정도의 연산만을 수행합니다. 그래도 N과 M이 1만을 넘어가면 1억번 이상의 연산을 필요로 하지요.
설명의 편의를 위하여 B = 0인 데이터를 예로 들겠습니다. 그러면 각 테스트 케이스의 점수는 hash xor을 계산했을 때, 'prefix가 0인 문자열의 길이가 L'일 때, L^2 * R이 됩니다.
hash_array1[x]가 0..으로 시작하고, hash_array2[y]가 1..로 시작한다면, 이 두 값의 xor은 1로 시작하기 때문에 점수가 0점이 됩니다. 즉 calcScore()를 수행할 필요가 없는 것이지요.
앞에서 5자리가 일치하는 경우에만 calcScore()를 계산하도록 만들면 아래와 같은 코드가 됩니다.
prefix_s2 = 00010 이라고 한다면, Array1의 hash값이 00010으로 시작되는 인덱스에 대해서만 calcScore()를 수행합니다. 앞의 5자리가 같은 경우에만 비교를 하게 되므로, 평균적으로 N * M / 32 번의 calcScore()를 수행하지요. 위의 코드에서 5자리에 대해서만 체크를 했는데 자리수가 많아질수록 연산 횟수는 줄게 됩니다.
하지만 줄어드는 연산 횟수에 비례하게 메모리를 많이 사용하게 되기 때문에 저는 20자리에 대해서 체크를 하였습니다. 평균적인 calcScore()는 N * M / 100만 정도가 되고, 이 방법으로 N과 M을 30만까지 계산할 수 있었습니다.
위에서는 B = 0인 데이터를 기준으로 설명했지만, B > 0인 데이터에서는 suffix를 가지고 같은 방식으로 계산합니다. (suffix는 1로 끝나야 하기 때문에 00110으로 끝나는 스트링은 11001로 끝나는 스트링과 calcScore()를 수행하면 됩니다.)
이상 메인 알고리즘에 대한 설명이었습니다. :) 소스코드를 최적화 하면서 N과 M을 늘려나가면 점점 답이 좋아지는 것을 확인할 수 있습니다.
긴 글 읽어주셔서 감사합니다. :)
11년 전