はひふへほ

ゲーム,雑記,美味い飯.時々アイマス.

頭が悪い人がソースコードを書いた時の話

はい.頭が悪い人です.自戒も込めて書いておく.このブログはソースコードとか書くつもりがないので,できるだけみんなに分かるように書く.

 

 

昨日の夜からこんなことやってました.具体的にはA→Bへの文字列置換を実施するような処理をするコードを書いただけ.素直に考えるとだいたいこんな感じ?

  1. 文SにAが含まれるか確認
  2. 文SにAが含まれる場合 → AをBへ置換 → 文Sを出力
  3. 文SにAが含まれない場合 → 文Sを出力

まぁ,普通に処理するなら,毎文A→Bへの置換処理を実行するだけで良いように思えるんですが,問題はA→Bをだいたい20万件ぐらい実行しなければいけないってこと.置換するペアを(A, B)とすると,こういうペアがそもそも20万件ぐらい存在しているんですよ.そしてこの処理を1000万文オーダーで実行します.上記リストの1が各文に20万回,上記リスト全体が1000万回以上実行されるってことです.

単純計算で考えると,1000万文に対して20万件の条件処理(文SにAが含まれるか確認する処理)を実行するだけで2億回も処理が走っているのでこの時点でうんざりします(実際は置換処理もあるのでもっと処理が走っていることは明白).1回処理をするのに1.0[ms]だとすると,単純計算でも2日以上,50時間以上かかります.アホくさくなってきますね.

ですが冒頭のつぶやきどおり,ざっくりした見積もり計算した際に桁を間違えて入力した結果,「なんだ5時間ちょっとで終わるやん,回したまんま寝よう(つ∀-)オヤスミー」っていって爆睡,そして今朝になって全然終わっていませんでしたという状況でした.これはひどい

 

で,結果的にどうしたかというと,(A, B)の条件の前に1つ条件を追加しました.Aに共通する部分文字列があるという制約があったので,その制約に基づいて事前に条件を追加したのです.例えば,文に「あげは」「こげは」「しげは」が含まれるか確認する前に,「げは」が存在するか確認して,その後に「あげは」「こげは」「しげは」が存在するか確認します.「げは」が存在しない時点でこの文には「あげは」も「こげは」も「しげは」も存在しないことが分かるので,これらについては確認処理をしません.もう少し一般的に書くとこんな感じ.

  1. 文SにAの部分文字列が含まれるか確認(ここがだいたい10回)
  2. 文SにAの部分文字列が含まれる場合,文SにAが含まれるか確認(ここの処理回数は1の結果に依存.最小で0,最大で20万)
  3. 文SにAが含まれる場合 → AをBへ置換 → 文Sを出力
  4. 文SにAが含まれない場合 → 文Sを出力

パット見だと処理が増えてつらい気持ちになりますが,先程説明したように毎回20万回Aが含まれるか確認する必要がなくなり,一文に対して最小で10回確認するだけで済むようになったので,むちゃくちゃ早くなりました.具体的には(実測値でだいたい)20倍早くなりました.2日以上かかるはずだった処理が2時間程度で終わったので最高という気分です.まぁ,本当にもっと早くしたいなら,そもそもPythonを使わないっていうのが1番な気もします.C++だったらもっと早いでしょうから.

 

しっかし,今回はろくに考えずに適当に実装した私が完全に悪かったし,それ以上に見積もりの計算を雑にしすぎた結果時間をだいぶ無駄にしてしまったので,本当にやってしまったなぁと思っています.そもそも遅くなるのは計算規模を考えれば想像できたはずなんですが.もう少し想像力を持ってコードを書きたいと思った今朝でした.