マップエディタを作成中に

    var canvasPoints = new List<Point>();
この canvasPoints リストから

    var removePoints = new List<Point>();
removePoints に該当するポイントを全て取り除きたいとします。リストにはまとめて削除できる RemoveAll というメソッドが用意されているため、これを使うと

    canvasPoints.RemoveAll(p => removePoints.Contains(p));
たったこれだけで、サクッと canvasPoints から removePoints に該当するポイントを削除する事が出来ます。…が、このメソッド、めちゃくちゃ遅いのです。canvasPoints が凡そ 100万ポイントあるとして、removePoints がせいぜい数百というオーダーであっても、これを実行すると

8,659ms
8,536ms
8,542ms
8,507ms
8,435ms
-------------
平均: 8,536ms

…遅い、遅すぎる。内部でいちいちリストを詰めている様が目に見えるようだ。こんなことせず、インデックスで処理して最後にまとめてえいやっとコピーしてくれれば十分普通に速いだろうに、なにやってくれちゃってるんでしょうか。

仕方が無いので、RemoveAll より高速に動作する removePoints に該当する処理を作ってみる事にしました。アルゴリズム的には閾値による判定とでも呼びましょうか。Point は X と Y から成っていますが、これを重なりのない1次元の数値に置き換えてしまいます。アセンブラで X と Y から VRAMアドレスを作りますが、そんな感じで X,Y ではなく一つの int を作ってしまいます。

また、処理を単純化するため、どちらのリストもソートで並び替えてしまいます。これで、例えば大きい順に検索すれば、チェックした次の値は、必ず前回よりも小さい事が保証されますので、比較範囲を縮めていく事が出来ます。全ての処理を最初にドンッ！

    // X 方向の最大幅を求める
    int min1 = canvasPoints.Min(i => i.X);
    int min2 = removePoints.Min(i => i.X);
    int max1 = canvasPoints.Max(i => i.X);
    int max2 = removePoints.Max(i => i.X);
    int stride = (max1 > max2 ? max1 : max2) - (min1 < min2 ? min1 : min2) + 1;

    // ソートする
    var before = new List<Point>(canvasPoints);
    var removes = removePoints.Distinct().ToList();
    before.Sort((a, b) => a.Y == b.Y ? a.X - b.X : a.Y - b.Y);
    removes.Sort((a, b) => a.Y == b.Y ? a.X - b.X : a.Y - b.Y);

    // 閾値との違いを削除対象として判定する
    canvasPoints.Clear();
    int idxRemove = removes.Count - 1;
    int numCheck = removes[idxRemove].X + removes[idxRemove].Y * stride;
    for (int idx = before.Count - 1; idx >= 0; --idx)
    {
        var num = before[idx].X + before[idx].Y * stride;
        while (num < numCheck && idxRemove > 0)
        {
            numCheck = removes[--idxRemove].X + removes[idxRemove].Y * stride;
        }
        if (num != numCheck) canvasPoints.Add(before[idx]);
    }
では、各所でどのような処理をしているかの説明をします。まずは検索範囲の最大横幅を求めます。これは X + Y * stride の stride を求めないと、違う座標なのに同じ値が出来てしまう可能性があるためです。

    // X 方向の最大幅を求める
    int min1 = canvasPoints.Min(i => i.X);
    int min2 = removePoints.Min(i => i.X);
    int max1 = canvasPoints.Max(i => i.X);
    int max2 = removePoints.Max(i => i.X);
    int stride = (max1 > max2 ? max1 : max2) - (min1 < min2 ? min1 : min2) + 1;
続いて、リストを小さい順に並べます。並び替えの過程で途中削除をしたくなかったので、現在のリストは before にコピーして、元々のリスト canvasPoints は clear してしまいます。これは追加加算は速いだろうという目算です。

    // ソートする
    var before = new List<Point>(canvasPoints);
    var removes = removePoints.Distinct().ToList();
    before.Sort((a, b) => a.Y == b.Y ? a.X - b.X : a.Y - b.Y);
    removes.Sort((a, b) => a.Y == b.Y ? a.X - b.X : a.Y - b.Y);
最後に判定です。調べられるリスト before も、調べるリスト removes も、どちらも最後から 0 に向かって調べていきます。そして比較する場合は Point のままではなく、Point の X,Y を X + Y * stride した一意の値で比較するのですが、その前処理として、調べる数が最初から大きかった場合は、値が以下になるまで小さくしてしまいます。その結果が一意の数が不一致なら、その Point は有効として残す事にしました。

    // 閾値との違いを削除対象として判定する
    canvasPoints.Clear();
    int idxRemove = removes.Count - 1;
    int numCheck = removes[idxRemove].X + removes[idxRemove].Y * stride;
    for (int idx = before.Count - 1; idx >= 0; --idx)
    {
        var num = before[idx].X + before[idx].Y * stride;
        while (num < numCheck && idxRemove > 0)
        {
            numCheck = removes[--idxRemove].X + removes[idxRemove].Y * stride;
        }
        if (num != numCheck) canvasPoints.Add(before[idx]);
    }
このアルゴリズムでもう一度同じ条件で実行してみますと…

449ms
443ms
438ms
425ms
431ms
-------------
平均: 437ms

なんと以前の処理時間から、凡そ20倍速の向上を達成しました！何かの参考になれば幸いです。
タグ ：
C#
高速化
アルゴリズム