マップエディタの開発で、超広範囲の選択範囲がある状態で、BGの設定を実行したところ、数分経っても一向に終わる気配がないという大問題に直面しました。今回はこのとてつもなく遅い処理を、コンマ数秒まで高速化するテクニックです。
- 巨大リストをY軸毎に分解する
// ------------------------------------------------------------- // BGを設定する // ------------------------------------------------------------- public bool SetBG( CodeTable codes, in List<Point> points, Rectangle rcRange, in List<Point> selects, bool isGaps) { bool isModify = false; foreach (var posLT in points) { foreach (var code in codes) { foreach (var ofst in code.Value) { var pos = posLT + (Size)ofst; if (true && rcRange.Contains(pos) && (!isGaps || Areas[pos.X, pos.Y] == 0) && (selects.Count <= 0 || selects.Contains(pos))) { Areas[pos.X, pos.Y] = code.Key; isModify = true; } } } } return isModify; }
処理速度を上げようと、大まかな範囲を rcRange で振り分けていたのですが、全画面選択状態だと、逆効果になっていました。また、全画面だとテストの時は selects が250万のオーダーになっていました。250万×250万のリスト検索です。軽いはずがありません。もとより C# の List.Contains は遅いのです。
さて、大きく構造を変える事が出来ないので、この Contains を軽くする事を考えます。まず、検索対象を250万から減らす事を考えました。そこで使ったのが Dictionary です。これは key から value を取り出すという連想配列です。このキーに Y座標を割り当てて、Yに相当する Pointを全て List<Point>として valueに格納してしまえば良いのではないかと。これで250万のリストは数千のリストに減ります。
まず、メソッドの冒頭に Dictionaryの初期化を仕込みます。
// 選択範囲リストをY座標毎に分解する Dictionary<int, List<Point>> vpos = new(); foreach (var pos in selects) { if (!vpos.ContainsKey(pos.Y)) { vpos.Add(pos.Y, new List<Point>()); } vpos[pos.Y].Add(pos); }
これで vpos には、Y座標をキーとした複数のリストが格納されました。この連想配列の初期化は 150ms 前後で終わりました。少し安堵。これが遅かったら身も蓋もなかったので…
さて、実際の判定では、キー検索と、分解したリストからの Containsに分解です。ついでに大まかな範囲は無駄になったので取り払ってしまいます。
// 配置する bool isModify = false; foreach (var posLT in points) { foreach (var code in codes) { foreach (var ofst in code.Value) { var pos = posLT + (Size)ofst; if (true && rcRange.Contains(pos) && (!isGaps || Areas[pos.X, pos.Y] == 0)) { if (true && selects.Count > 0 && (!vpos.ContainsKey(pos.Y) || !vpos[pos.Y].Contains(pos.X))) { // 選択範囲があるのに選択範囲リストに無い座標は設定しない continue; } Areas[pos.X, pos.Y] = code.Key; isModify = true; } } } } return isModify; }
selects.Count > 0 で選択範囲があるかどうかを確認、あれば続いて vpos.ContainsKey(pos.Y) で該当する Y座標の選択リストがあるかどうかを確認、あれば最後にそのリストと vpos[pos.Y].Contains(pos)として存在確認という実装です。これで数秒で処理が完了するまでに高速化しました。
※しばらくコレを飲んでいました。酸っぱ美味しいです。ただ、定期便が使えなくなったので、次に紹介するアミノ酸に乗り換えています。
- さらなる高速化を目指す
// 全範囲が選択ならリストをクリアする int stride = MainForm.map.CharaSize.Width; foreach (var key in vpos.Keys) { if (vpos[key].Count < stride) continue; vpos[key].Clear(); }
この処理は、Y毎のリストが全体の幅キャラ数と同じだったら、リストを削除するという処理です。選択されているY座標があるのに、X方向のリストがゼロなんてあり得ないですよね。そのあり得ない状態をフラグとして、Y軸から得られたリストが Count == 0 なら配置可能と無条件で判断すればよい、というアイディアです。このため、配置判定の if は以下のように変更しました。
if (false || (isGaps && Areas[pos.X, pos.Y] != 0) // 隙間埋め指定だが空いていない || (selects.Count > 0 // 選択範囲があるのに && (!vpos.ContainsKey(pos.Y) // キーがない // リストに該当の座標がない || (vpos[pos.Y].Count > 0 && !vpos[pos.Y].Contains(pos))))) { continue; } Areas[pos.X, pos.Y] = code.Key; isModify = true;
またしても見るからに高速化されました。そこで、変換処理部分の実行速度を計測してみます。
■ 以前
1,484ms
1,515ms
1,377ms
1,345ms
1,324ms
--
平均 1,409ms
■ 新型
291ms
290ms
288ms
275ms
275ms
--
平均 283.8ms
実に5倍近い高速化を達成しました。最初はいつ処理が終わるか分からない状態でしたから、この高速化の効果は本当に劇的ですね！
さて、このままだとちょっと使いづらいので共通メソッドとしてしまいます。
//--------------------------------------------------------------- // 選択範囲リストをY座標毎に分解する //--------------------------------------------------------------- public static Dictionary<int, List<Point>> GetVPosDictionary(in List<Point> selects) { // 選択範囲リストをY座標毎に分解する CodeTable vpos = new(); foreach (var pos in selects) { if (!vpos.ContainsKey(pos.Y)) { vpos.Add(pos.Y, new List<Point>()); } vpos[pos.Y].Add(pos); } // 全範囲が選択ならリストをクリアする int stride = MainForm.map.CharaSize.Width; foreach (var key in vpos.Keys) { if (vpos[key].Count < stride) continue; vpos[key].Clear(); } return vpos; } //--------------------------------------------------------------- // 選択範囲リストに座標が含まれているか //--------------------------------------------------------------- public static bool IsVPosContains(CodeTable vpos, Point pos) => // Y軸のキーがあり、範囲リストがないか、リストに座標が含まれているか vpos.ContainsKey(pos.Y) && (vpos[pos.Y].Count <= 0 || vpos[pos.Y].Contains(pos));
これで、チェック前に GetVPosDictionary を呼び出して vpos を取得して、判定したい Point を引数に IsVPosContains を呼び出すだけとなりました。この修正のおかげで、プログラムコードがすっきりしました。また、煩雑な判定部分が共通化された事でバグ防止にもなったかと思います。ご参考になれば幸いです。
※ 今はこちらを愛飲しています。20kmウォーキングの後に飲むと疲労感がまるで違います。もう丸々1年以上飲み続けていますが、とても良いですよー！
単純に HashSet に変更しただけでも同じように速いのではないかと思ってテストしました。結果、HashSet.Contains では、平均 1,081ms と、新型 vpos 方式のほうが2倍以上速いという結果になりました。ただ、特殊なことをしなくても HashSet.Contains はそれなりに速いので、Point 以外では HashSet を用いるのを検討するべきですね。
コメント