[計算機]CodeIQのピッグデータ問題の回答

CodeIQの結城さんの「《ピッグデータ》に負けないで！」https://codeiq.jp/ace/yuki_hiroshi/q303 に応募した際の回答を貼っておきます．結果，評価5 ベスト・ピッグデータ賞（結果が正しく技術メモも十分な解答）をいただきました．成績の分布は下のとおりだそうです．

評価5: 38
評価3: 0
評価1: 15
合計: 53

このソート方法にはバケットソートという名前がついていることは知りませんでした．現在，私のところへはスカウトは来ていない．:-)

---

[技術メモ]
209679232 <--これが答え

Date: 2013/5/3

1)答えを求めるのに必要なデータ件数は 100*(2^30)件である．一件あたりのデータサイズは2byteなので，最低でもデータサイズは200Gバイトになる．

2)このデータをソートしなければいけない点を考慮すると，このデータをメモリ上はおろか，外部ファイルに持つのも簡単ではない．したがって別のアプローチを考える．

3)データの値は2byteなので，この値をキーとし，値を発生件数とするHashテーブルを作成して処理を行う．これによりソートを行う必要は無くなくなる．

4)処理を2フェーズに分け，前半のHashテーブルの作成はC（ソースコード1）で行い，結果をCSVファイルに出力する．後半の総和を求める部分はRuby（ソースコード2）で記述する．Cを採用したの高速化のため，Rubyを採用したのは，記述のしやすさが理由である．なおCの処理では，SHA1の呼び出し回数をを減らすため，2重ループにしてある．Cの処理部分は，下記の環境で142分かかった．

5)検証はサンプルデータに対して行っているが，充分という気がしていない．もう少し考える必要がありそうだ．出題者がどのように正解を検証したのか非常に興味がある．

6)問題の理解のため，最初にHaskell（ソースコード3）でプロトタイプを作成した．これはサンプルデータでは動くが，実課題のデータサイズでは遅すぎて使えない．

[使用環境]
MacOS 10.7.5
CPU 2.4Ghz Intel Core 2 Duo
メモリ 4G
gcc version 4.2.1 (Based on Apple Inc. build 5658) (LLVM build 2335.15.00)

[感想]
簡単と思い始めましたが，予想以上に手こずり，2日程ゴールデンウィークをつぶしてしまいました．面白い問題をありがとうございました．

[ソースコード1]

#include 
#include 
#include 
#include 
#define COMMON_DIGEST_FOR_OPENSSL
#include 
#define SHA1 CC_SHA1

#define COUNT 100 * pow(2,30)

#define SKIPS pow(2,24)
#define DATA_MAX pow(2,16)

int64_t data[(uint16_t)DATA_MAX];

int main(){
  printf("start\n");
  uint64_t i;
  uint32_t j;
  int k,k2,value;
  char sbuf[256];
  unsigned char digest[40];

  // init data array
  for(j = 0; j < DATA_MAX; j++){
	data[j] = 0;
  }
  printf("array init done\n");

  i = COUNT;
  printf("limit:%llu\n",i);
  for(i = 0;; i+=1){
	sprintf(sbuf,"%llu",i);
	SHA1(sbuf,strlen(sbuf),digest);
	for(k=0;k<10;k++){
	  if(COUNT <= (i*10)+k) goto done;
	  value = digest[k*2]*256 + digest[k*2+1];
	  // printf("%llu: %d\n",i*10+k,value);
	  data[value]+=1;
	}
  }
 done:
  for(j = 0; j < DATA_MAX; j++){
	if (0 < data[j]) printf("%d,%llu\n",j,data[j]);
  }
}

[ソースコード2]
#!/usr/bin/ruby

count = 100*(2**30)
skip = 2**24
sum = 0
accum_count = 0
k = 0

while l = gets
  data = l.chop.split(',')
  value = data[0].to_i
  n = data[1].to_i
  accum_count += n
 
  while k < accum_count
    sum += value
    puts k.to_s + " add:" + value.to_s
    k += skip
  end
  break if count <= k
end
puts sum

[ソースコード3]
import Data.Digest.SHA1
import Codec.Binary.UTF8.String
import Numeric
import Data.List

getdata :: Integer -> Integer
getdata index = 
  let 
    divisor = 10
    q = div index divisor
    r = mod index divisor
  in
   getdata_2 q r
   
getdata_2 :: Integer -> Integer -> Integer
getdata_2 q r =
  let str = int2hexstring (Data.Digest.SHA1.toInteger $ hash $ encode $ show q) 
      hexarray = string2hexarray str
  in
   getdata_3 hexarray r
   
getdata_3 :: [String] -> Integer -> Integer
getdata_3 s r =
  let r2 = fromIntegral(r * 2) 
      n0 = hex(s !! r2)
      n1 = hex(s !! (r2 + 1))
  in
   (n0 * 256) + n1
   
getsign :: Integer -> Int -> Integer
getsign count skips =
  let d = sort $ makedata count
  in calc_sum d skips
     
calc_sum :: [Integer] -> Int -> Integer
calc_sum d skips =
 sum $ calc_sum_filter d skips

calc_sum_filter :: [Integer] -> Int -> [Integer]
calc_sum_filter d skips =
  let x = (head d) 
  in 
   if *1 ++ str
     
genzeros:: Integer -> String
genzeros 0 = ""
genzeros n = "0" ++ (genzeros (n-1))

string2hexarray :: String -> [String]
string2hexarray (x1:x2:) = [x1:x2:]
string2hexarray (x1:x2:rest) = (x1:x2:[]):(string2hexarray rest)
                               
hex :: String -> Integer
hex s = read ("0x" ++ s) :: Integer
                            
main = do
  let 
    count = 107374182400
    -- count = 100
    skips = 16777216
    result = makedata count
  mapM_ (putStrLn . show) result

*1:length d) <= skips) then x:[] else x:calc_sum_filter (drop skips d) skips makedata :: Integer -> [Integer] makedata 1 = [ getdata 0 ] makedata n = getdata(n-1):makedata(n-1) int2hexstring :: Integer -> String int2hexstring n = let str = showHex n "" r = 40 - (Prelude.length str) in if r == 0 then str else (genzeros (fromIntegral r