Algoritm Tutorials

Data Science Tutorials – topcoder
ここのDumitru氏のHow to Find a Solutionを読み進めて行こうと思う。

早速、BFSのSmartWordToy - SRM 233 Div1にチャレンジしたんだけど、見事にTLE
解答を見合わせるとたぶん合ってるんだけど、圧倒的に速度が足りなかった。
結局断念してredcoderの方のソースコードを拝見したところ…


あれ？基本的には変わらないような？


明らかに違うのは1度出現した文字列を配列で扱うか、mapで扱うかの違いだった。
というわけで、速度を見るために簡単なコードを書いたところびっくりするほど差が出た。

map ver

int main(){
  map<string,int> mp;
  string A,B,C,D;
  A=B=C=D="abcdefghijklmnopqrstuvwxyz";

  for(int a=0;a<26;a++)
    for(int b=0;b<26;b++)
      for(int c=0;c<26;c++)
        for(int d=0;d<26;d++){
          string s;
          s+=A[a]; s+=B[b]; s+=C[c]; s+=D[d];
          if(mp[s]==0)mp[s]++;
        }
  return 0;
}

配列ver

int h[26][26][26][26];
int main(){
  string A,B,C,D;
  A=B=C=D="abcdefghijklmnopqrstuvwxyz";

  for(int a=0;a<26;a++)
    for(int b=0;b<26;b++)
      for(int c=0;c<26;c++)
        for(int d=0;d<26;d++){
          if(h[A[a]-'a'][B[b]-'a'][C[c]-'a'][D[d]-'a']==0)
            h[A[a]-'a'][B[b]-'a'][C[c]-'a'][D[d]-'a']=1;
        }  
  return 0;
}

CPU CeleronM 1.73GHz


map ver

real    0m10.955s

user    0m10.374s

sys     0m0.061s

配列ver

real    0m0.149s

user    0m0.061s

sys     0m0.046s

（ ﾟдﾟ）ﾎﾟｶｰﾝ


いや…まぁ、mapを使用したほうが遅いのは分かってはいたけど…これほど差が出るなんて思わなかった。
扱うパターン数が決まっていて、それが収まる程度ならば配列によるハッシュを念頭に考えて使っていくほうが良さそう。


stringの部分ではどの程度速度に影響が出ているのだろうと思い、
if(mp[s]==0)mp[s]++;
の部分をコメントアウトして実行してみたところ、

real    0m5.063s

user    0m4.804s

sys     0m0.000s

あるぇー、まさかの結果ｗ
string生成にこれほどまで処理がかかるなんて…。
stringは便利だけど、安易に使っていくと速度にかなり影響が出る様子