C#のfor(each)ループの速度が遅い？

Question

こんにちは。

現在約1200回のforループ、その中のforで約160000回のforループで処理をするプログラムを書いたのですが、終了までにかなり時間がかかります。

string tempString = "";

foreach (string[] x in senNihyaku)
{
    foreach (string[] y in juRokuan)
    {
        cat = // y[1]は住所なので、それを渡すと〇〇県と〇〇市にわけられた配列を返す関数呼び出し
        if (x.Contains(cat[1])){ tempString += y[2]}
    }
}

上記のような感じです。
都道府県市区町村を分ける関数に関しては、事前に〇〇県〇〇市のような文字列が入っている配列を用意しておき、それをループで回して、引数で渡された住所と照らしあわせて、見つかった場合はその文字列を返すというような関数です。

160000回のループは約２分３０秒かかります。
なので約５０時間もかかってしまう計算になります。

C#のループというのは、こレくらいの速度が普通なんでしょうか？

Answer 1

こんにちは。

恐らくfor文の処理が遅いのではなく、ループの中身の処理に時間がかかっているということではないでしょうか？
150秒/160,000回=1mSec弱ですので、処理の内容によっては十分にありえる数字と思います。
文字列分解、文字列検索、文字列追加はそれぞれそこそこ重めの処理です。

試しにループの中に何もしない関数を１つ呼び出すだけにして時間を測ってみてはどうでしょうか？
やったことはないですが、160,000回のループに1秒も掛からないのではないかと思います。

---

【追加】
そのようなケースで速いアルゴリズムを考えるのがプログラマの醍醐味かも。
例えば、16万個の住所を単純にソートしておいて、渡された住所に最も近いものを2分探索等で検索し、最も近いもの２つについて分解と厳密なマッチを行うことで、かなり高速化できるだろうと思います。

住所表記に揺れ（例えば、間にスペースが入っていたり、県名があったりなかったり、同じ市なのに旧名と新名が入り混じっているなど）があるとうまく行かないので、事前に正規化しておくこと等が必要になります。

Comments

[kurosuke___]

迅速な回答有り難うございます。

都道府県市町村区を分離する関数の速度を測ったところ、約0.001秒かかってました。ループ一回分にかかる時間の９９％はこの処理みたいですね。
主にSubstringをつかって分離していますが、これが遅いんでしょうか・・・

[kurosuke___]

なるほど・・・２分探索というものの存在自体知りませんでした。
ちらっと調べてみましたが、とても難しそう？なので、勉強しながら、Chironianさんのおっしゃっている方法を実装してみたいと思います。ありがとうございました。

[Chironian]

あ、「都道府県」、「市」、「町」、「村」、「区」に分解しているのですか？
更に表記の揺れ等も吸収しているような処理でしたら、1mSecもありえそうな気がします。

どうしても分解が必要でしたら、メモリを多く使いますが、16万件のデータを事前に分解しておいて検索すれば５０時間の処理に対して大凡99%の高速化が可能ですね。

1件当たり100バイトとしても16万件で16MBytesですから、今のPCなら使っても問題ないと思いますよ。

[kurosuke___]

まず渡された住所の中に、containsで〇〇県〇〇市という文字列データが2600件ほど入っているデータとforeachで照らしあわせて、見つかった場合はその〇〇県〇〇市という文字列を都道府県名　と　市町村区名に分解して、配列にして返してます。
分解には主に、http://dobon.net/vb/dotnet/vb2cs/mid.htmlで紹介されている関数を使っています。都道府県名で４文字なのはすべて「県」なので、４文字目に県があった場合と３文字目だった場合&「県」がなかった場合の処理で分けています。

さいしょからデータにしておく、ですか。そうですね、毎回処理をするよりはそちらのほうが良さそうです。〇〇県〇〇市のデータはもうあるので、それを分離したデータも作っておこうと思います。

[thinca]

アルゴリズムの改善の方が効果は高いと思いますが、提示されているコードの範囲でできそうな最適化に、文字列の構築に StringBuilder を使う方法があります。
https://msdn.microsoft.com/ja-jp/library/system.text.stringbuilder(v=vs.110).aspx
文字列を毎回 += で構築するのは重いのでそういった際に使用します。参考にどうぞ。

[kurosuke___]

thincaさん、ありがとうございます！
とても参考になります！