2006年3月18日の日記

System.Collections.Generic.SortedListって遅い！！
なんちゅう遅さだ！！
O(n)で要素を追加できるからx個のデータの中からn個をを追加するならO(xn)ですむはずなのにものすごく遅い！！
他のSortedDictionaryも同様。
私が欲しかったのは要素の追加が(logn)程度で行える、整列された、値の重複を許さない、値のコレクションだったのですが、どうにもなさそうだったので普通の配列で頑張ってみることにしました。

string[] outArray = new string[1];
int count = 0;
bool found;
foreach (string data in inArray)
{
    found = false;
    foreach (string item in outArray)
    {
        if (item == data)
        {
            found = true;
            break;
        }
    }
    if (!found)
    {
        if (count >= outArray.Length) Array.Resize(ref outArray, count * 2);
        outArray[count] = data;
        count++;
    }
}
Array.Resize(ref outArray, count);
Array.Sort(outArray);

これ、O(n²)の処理なんですがもう感動的な早さです。
本当はゲームのキャラデータの一部から抜き出しているのでinArrayの要素をそのまま使っているのではなく、Sorted～にそのままデータを渡すことができないため一つ一つSorted～クラスにデータを渡していたせいで遅くなったものと考えています。
このアルゴリズムでは最初に値の重複を許さない要素の配列を作って後から整列しています。
最後のソートは元々高速なので実質配列の生成に最も時間がかかっています。
ちなみに、配列を延ばすのにも時間がかかるはずですが、配列の長さの初期値を増やしたところで大して高速化しなかったのでとりあえず最小の1にしています。