ichirin2501's diary

いっちりーん。

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

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