Codesprint 2013 Round 1 후기 :)

  • astein
    astein

    안녕하세요. Astein입니다. 어쩌다보니 순위권에 들게 되어 Codesprint Round 1 간단 후기를 남기게 되었습니다.

    일단 skein 해시를 깨기 힘들다고 가정한다면, 아래와 같은 방법이 제일 기본적인 접근 방법이 됩니다.

    //Array1[] = S1을 prefix로 하는 스트링
    //Array2[] = S2를 prefix로 하는 스트링 
    
    int N = Array1.size(), M = Array2.size();
    
    for (int i = 0; i < N; ++i) {
      for (int j = 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로 하는 스트링 
    
    int N = Array1.size(), M = Array2.size();
    
    //hash_array1[] = Array1[]의 get_hash()값을 저장하는 배열
    //hash_array2[] = Array2[]의 get_hash()값을 저장하는 배열
    
    for (int i = 0; i < N; ++i) hash_array1[i] = get_hash(Array1[i]);
    for (int i = 0; i < M; ++i) hash_array2[i] = get_hash(Array2[i]);
    
    for (int i = 0; i < N; ++i) {
      for (int j = 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로 하는 스트링 
    
    int N = 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 (int i = 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 (int i = 0; i < M; ++i) hash_array2[i] = get_hash(Array2[i]);
    
    for (int j = 0; j < M; ++j) {
      //int prefix_s2 = hash_array2[j]의 앞 5자리
      for (int i = 0; i < hash_index1[prefix_s2].size(); ++i) {
        int index = 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을 늘려나가면 점점 답이 좋아지는 것을 확인할 수 있습니다.

    긴 글 읽어주셔서 감사합니다. :)


    10년 전
2개의 댓글이 있습니다.
  • JongMan
    JongMan

    멋있땅


    10년 전 link
  • kladess
    kladess

    헐.. 해쉬를 배열에 저장하고 했어야 했군요. 아직 초보라서 첫번째까지는 완성했었지만, 왜느리지? 왜느리지 하면서 변수들에 __inline_ 만 때려기넣기에 급급했네요. 가능하시면 최적화했던 방법도 알려주세요.


    10년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.