C#でのソートアルゴリズムのまとめ(sort algorithms in C#)

stereopsis : graphics : radix tricksやSTLportのソースをパクったりしたC#でのソートのまとめ。

それぞれのアルゴリズムとか関連エントリとか。

• ksksts's blog: C#で実装したradix sortとArray.Sortのquick sortとの比較
• ksksts's blog: C#で符号付整数／浮動小数点数対応の基数ソート(radix sort)
• ksksts's blog: C#でin place merge sortを書いてみたらかなり遅かった 
• ksksts's blog: バッファを使用するマージソートも書いてみた(merge sort with buffer in C#) 
• ksksts's blog: イントロソートも書いてみた(introsort in C#)

配列に対するソートとList<T>に対するソートに対するソートとの差やEnumerable.OrderBy メソッド (System.Linq)とかも含めた測定結果は次の通り。

size: 1000
Array.Sort: 1186 (1.00)
List.Sort: 1050 (0.89)
Array.OrderBy: 6592 (5.56)
List.OrderBy: 3305 (2.78)
CombSort Array: 31971 (26.94)
CombSort List: 6909 (5.82)
NumberRadixSorter.Sort Array: 4943 (4.17)
NumberRadixSorter.Sort List: 2291 (1.93)
InPlaceMergeSorter.Sort Array: 40326 (33.98)
InPlaceMergeSorter.Sort List: 12642 (10.65)
MergeSorter.Sort Array: 24463 (20.61)
MergeSorter.Sort List: 9604 (8.09)
IntroSorter.Sort Array: 22909 (19.30)
IntroSorter.Sort List: 4158 (3.50)

size: 10000
Array.Sort: 12771 (1.00)
List.Sort: 12497 (0.98)
Array.OrderBy: 41599 (3.26)
List.OrderBy: 41126 (3.22)
CombSort Array: 465802 (36.47)
CombSort List: 101879 (7.98)
NumberRadixSorter.Sort Array: 27803 (2.18)
NumberRadixSorter.Sort List: 22234 (1.74)
InPlaceMergeSorter.Sort Array: 553976 (43.38)
InPlaceMergeSorter.Sort List: 202408 (15.85)
MergeSorter.Sort Array: 224039 (17.54)
MergeSorter.Sort List: 128939 (10.10)
IntroSorter.Sort Array: 158357 (12.40)
IntroSorter.Sort List: 52881 (4.14)

size: 100000
Array.Sort: 146888 (1.00)
List.Sort: 145938 (0.99)
Array.OrderBy: 520984 (3.55)
List.OrderBy: 518649 (3.53)
CombSort Array: 6044506 (41.15)
CombSort List: 1311650 (8.93)
NumberRadixSorter.Sort Array: 279857 (1.91)
NumberRadixSorter.Sort List: 218608 (1.49)
InPlaceMergeSorter.Sort Array: 8215845 (55.93)
InPlaceMergeSorter.Sort List: 2860999 (19.48)
MergeSorter.Sort Array: 2931658 (19.96)
MergeSorter.Sort List: 1869126 (12.72)
IntroSorter.Sort Array: 1945971 (13.25)
IntroSorter.Sort List: 658093 (4.48)

size: 1000000
Array.Sort: 1666666 (1.00)
List.Sort: 1668472 (1.00)
Array.OrderBy: 6961424 (4.18)
List.OrderBy: 6901036 (4.14)
CombSort Array: 76084478 (45.65)
CombSort List: 16674472 (10.00)
NumberRadixSorter.Sort Array: 2864637 (1.72)
NumberRadixSorter.Sort List: 2245710 (1.35)
InPlaceMergeSorter.Sort Array: 110817348 (66.49)
InPlaceMergeSorter.Sort List: 38880094 (23.33)
MergeSorter.Sort Array: 35271234 (21.16)
MergeSorter.Sort List: 20756358 (12.45)
IntroSorter.Sort Array: 24093398 (14.46)
IntroSorter.Sort List: 8047601 (4.83)

ksksts / junk / source — bitbucket.org

まとめ:

• 安定でないソートならArray.Sort メソッド (System)かList(T).Sort メソッド (System.Collections.Generic) 
• 安定なソートならEnumerable.OrderBy メソッド (System.Linq) 
• STLportのソースをパクった結果としては速い順にIntroSort（STLのstd::sort）, InPlaceMergeSort（STLのstd::stable_sortのバッファを使わない版）, MergeSort（STLのstd::stable_sortのバッファを使う版）。そしてRadixSort（基数ソート）はこいつらより速い。
• 配列の添字でのランダムアクセスはList<T>のインデクサでのアクセスより遅い？（これはIList<T>を経由しているのが原因だったみたい ksksts's blog: 配列やList<T>をIList<T>型のインデクサでアクセスするとパフォーマンスが悪い(don't use IList<T>'s indexer)）

イントロソートも書いてみた(introsort in C#)

バッファを使わないマージソートとバッファを使うマージソートのついでにイントロソートもSTLportからパクってみた。

STLportの_algo.c, _heap.h, _heap.cの__introsort_loop, __unguarded_partition, __final_insertion_sort, __unguarded_linear_insert, __partial_sort, __make_heap, __adjust_heap, __push_heap_aux, __pop_heap_aux, sort_heapあたりをC#で書いただけ。
かなり手抜きだと思う。マージソートとの速度差をみたいだけだから。

結果は次の通り。
Array.Sortの十数倍の時間がかかっている。バッファを使用するマージソートよりは多少速い。
ソート対象を配列からList<T>に変更するだけで数倍良くなるはずだから後でまとめて試してみる。
今になって基数ソート(radix sort)がかなり速いということを実感。

size: 1000
IntroSorter.Sort: 20622 (18.78)
Array.Sort: 1098 (1.00)
size: 10000
IntroSorter.Sort: 139073 (10.98)
Array.Sort: 12667 (1.00)
size: 100000
IntroSorter.Sort: 1771360 (12.22)
Array.Sort: 144995 (1.00)
size: 1000000
IntroSorter.Sort: 21275858 (12.85)
Array.Sort: 1656005 (1.00)

ksksts / junk / source — bitbucket.org

バッファを使用するマージソートも書いてみた(merge sort with buffer in C#)

in-place merge sortをEQUATEC Profilerでプロファイルしてみたけど特におかしいと感じるところは見つからず、結局マージ回数が多すぎじゃないかと思う（あとお手玉Rotatenってやっぱり速いのかなと）。
in-placeじゃないアルゴリズムとの比較をするためにSTLportの_algo.cのstable_sortから__stable_sort_adaptive, __merge_sort_with_buffer, __chunk_insertion_sort, __merge_sort_loop, mergeあたりを辿って、ソート対象の要素個数分のバッファを使用するマージソートをC#で書いてみた。
結果は下記の通り。in-place merge sortよりは良い。でもまだArray.Sortの十数倍の時間がかかっている。
いろいろ小賢しいことをやっているからもっとシンプルな素直なコードを書いてみたほうがいいかもしれない。

size: 1000
InPlaceMergeSorter.Sort: 37314 (33.24)
MergeSorter.Sort: 21869 (19.48)
Array.Sort: 1122 (1.00)
size: 10000
InPlaceMergeSorter.Sort: 502465 (39.24)
MergeSorter.Sort: 198861 (15.53)
Array.Sort: 12805 (1.00)
size: 100000
InPlaceMergeSorter.Sort: 7425488 (47.00)
MergeSorter.Sort: 2556782 (16.18)
Array.Sort: 157988 (1.00)
size: 1000000
InPlaceMergeSorter.Sort: 98928451 (58.09)
MergeSorter.Sort: 31298754 (18.38)
Array.Sort: 1703143 (1.00)

ksksts / junk / source — bitbucket.org

C#でin place merge sortを書いてみたらかなり遅かった

C#で簡単に使いまわせる安定なソートを用意しておこうと思ってIn place stable Sort (merge sort)を参考に書いてみたらかなり遅かった。
In place stable Sort (merge sort)のソースの不自然さが気になったからSTLportの_algo.cとか_algobase.cとかも参考にした。
Array.Sortの数十倍時間がかかるとか、これじゃあまり使う気にならない。
何かミスっているのかもしれないし、in placeでなければもうちょっとましかもしれない。明日もう少し調べてみる。

size: 1000
merge sort: 37580 (30.34)
Array.Sort: 1238 (1.00)
size: 10000
merge sort: 506318 (41.50)
Array.Sort: 12199 (1.00)
size: 100000
merge sort: 7170923 (50.21)
Array.Sort: 142813 (1.00)
size: 1000000
merge sort: 97304833 (60.94)
Array.Sort: 1596662 (1.00)

ksksts / junk / source — bitbucket.org

C#で符号付整数／浮動小数点数対応の基数ソート(radix sort)

Radium Software Development経由でRadix Sort Revisitedを見て、さらに2006-07-23 - togeの日記経由でstereopsis : graphics : radix tricksも読んだから書いてみた。
ksksts's blog: C#で実装したradix sortとArray.Sortのquick sortとの比較で実行速度で.NET FrameworkのArray.Sort メソッド (System)とかを上回るのは難しいと感じた時点で目的を実装例を示すだけに変更。Decimal型やString型に対応しようと思っていたけど、面倒くさくなったから符号なし整数型、符号付整数型、浮動小数点数型で止めとく。

stereopsis : graphics : radix tricksのコードを参考にして書いた。
おおまかな処理の流れは次の通り。

1. ヒストグラムをまとめて作成（histgramming）
2. ヒストグラムの値を加算（sum the histgrams）
3. 要素の並べ替え（read/write histgram, copy）

インターフェースはこんな感じ。
RadixSorter.cs

public static void Sort<T>(IList<T> list, Func<T, UInt32> converter, SortOrder sortOrder)

ソートに使用するキーを指定しながらソートできるのがおもしろい。

struct Pair<TFirst, TSecond>
{
    public TFirst First { get; set; }
    public TSecond Second { get; set; }
}

このPair型に対して、

RadixSorter.Sort(result, x => x.Second, RadixSorter.SortOrder.Ascending);
RadixSorter.Sort(result, x => x.First, RadixSorter.SortOrder.Ascending);

とすると、次のCompareTo（Firstで比較＆Firstが等しい場合はSecondで比較）でソートした場合と同じ結果が得られる。

public int CompareTo(Pair<TFirst, TSecond> x)
{
    var result = First.CompareTo(x.First);
    if (result == 0)
        result = Second.CompareTo(x.Second);
    return result;
}

あとは書いてみて思ったこととか。

ヒストグラムをずらして作っておくと加算する処理が簡単になること、降順にソートする場合はヒストグラムの加算の処理で対応できること。
NumberRadixSorter.csのSort(IList list, SortOrder sortOrder)

// histgramming
            var histgramOffset = ascending ? 1 : -1;
            foreach (var x in list)
            {
                var y = x;
                for (var p = 0; p < tables.Length; p++)
                {
                    tables[p][(y + histgramOffset) & 0xFF]++;
                    y = y >> 8;
                }
            }

            // sum the histgrams
            if (ascending)
            {
                foreach (var table in tables)
                {
                    table[0] = 0;
                    for (var n = 1; n < table.Length; n++)
                        table[n] += table[n - 1];
                }
            }
            else
            {
                foreach (var table in tables)
                {
                    table[0xFF] = 0;
                    for (var n = 0xFE; n >= 0x00; n--)
                        table[n] += table[n + 1];
                }
            }

符号付整数型でも同様。ただし符号ビットを含む部分だけ工夫する。
NumberRadixSorter.csのSort(IList list, SortOrder sortOrder)

// sum the histgrams
            if (ascending)
            {
                for (var p = 0; p < tables.Length - 1; p++)
                {
                    var table = tables[p];
                    table[0] = 0;
                    for (var n = 1; n < table.Length; n++)
                        table[n] += table[n - 1];
                }
                {
                    var table = tables[tables.Length - 1];
                    table[0x80] = 0;
                    for (var n = 0x81; n <= 0xFF; n++)
                        table[n] += table[n - 1];
                    table[0x00] += table[0xFF];
                    for (var n = 0x01; n < 0x80; n++)
                        table[n] += table[n - 1];
                }
            }
            else
            {
                for (var p = 0; p < tables.Length - 1; p++)
                {
                    var table = tables[p];
                    table[0xFF] = 0;
                    for (var n = 0xFE; n >= 0x00; n--)
                        table[n] += table[n + 1];
                }
                {
                    var table = tables[tables.Length - 1];
                    table[0x7F] = 0;
                    for (var n = 0x7E; n >= 0x00; n--)
                        table[n] += table[n + 1];
                    table[0xFF] += table[0x00];
                    for (var n = 0xFE; n >= 0x80; n--)
                        table[n] += table[n + 1];
                }
            }

浮動小数点数の場合は、要素が数値でそれを変更できる場合はヒストグラムを作るときにビットをflipして、ソート後に元に戻すとかできる（stereopsis : graphics : radix tricksのコードでやっている）。
NumberRadixSorter.csのSort(IList list, SortOrder sortOrder)

// histgramming
            var histgramOffset = ascending ? 1 : -1;
            for (var n = 0; n < list.Count; n++)
            {
                var y = BitConverter.DoubleToInt64Bits(list[n]);
                y ^= -(Int64)((UInt64)y >> 63) | unchecked((Int64)0x8000000000000000);  // flip
                list[n] = BitConverter.Int64BitsToDouble(y);
                for (var p = 0; p < tables.Length; p++)
                {
                    tables[p][(y + histgramOffset) & 0xFF]++;
                    y = y >> 8;
                }
            }

// read/write histgram, copy
            IList<Double> array = new Double[list.Count];
            Action swap = () => { var temp = list; list = array; array = temp; };
            for (var p = 0; p < tables.Length - 1; p++)
            {
                var table = tables[p];
                foreach (var x in list)
                {
                    var y = BitConverter.DoubleToInt64Bits(x);
                    y = (y >> p * 8) & 0xFF;
                    array[table[y]] = x;
                    table[y]++;
                }
                swap();
            }
            {
                var p = tables.Length - 1;
                var table = tables[p];
                foreach (var x in list)
                {
                    var w = BitConverter.DoubleToInt64Bits(x);
                    var y = (w >> p * 8) & 0xFF;
                    w ^= (Int64)((UInt64)w >> 63) - 1 | unchecked((Int64)0x8000000000000000);  // flip back
                    array[table[y]] = BitConverter.Int64BitsToDouble(w);
                    table[y]++;
                }
                swap();
            }

ksksts / junk / source — bitbucket.org

C#で実装したradix sortとArray.Sortのquick sortとの比較

radix sort（基数ソート）のコードを書いてて、適当に処理速度を比較してみたら遅かったから簡単なベンチマークを書いてみた。
比較するのは次の3つ。

• radix sort（WikipediaのRadix sortとstereopsisのradix tricksを参考にして書いたコード）
• comb sort（WikipediaのComb sortを参考に書いたコード、というかほぼそのまま）
• quick sort（.NET Framework 3.5のArray.Sort）

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;

namespace SortBenchmark
{
    class Program
    {
        static void Main(string[] args)
        {
            for (var size = 1000; size <= 1000000; size *= 10)
                Run(size);
        }

        static void Run(int size)
        {
            Console.WriteLine("size: {0}", size);

            var count = 10;
            var sw = new Stopwatch();
            var radixSortTicks = 0L;
            var combSortTicks = 0L;
            var arraySortTicks = 0L;
            for (var c = 0; c < count; c++)
            {
                var random = new Random(c);
                var list = new UInt32[size];
                for (var n = 0; n < list.Length; n++)
                    list[n] = (UInt32)random.Next(Int32.MinValue, Int32.MaxValue);

                // radix sort
                var radixSortResult = (IList<UInt32>)list.Clone();
                sw.Reset();
                sw.Start();
                RadixSort(radixSortResult);
                sw.Stop();
                radixSortTicks += sw.ElapsedTicks;

                // comb sort
                var combSortResult = (IList<UInt32>)list.Clone();
                sw.Reset();
                sw.Start();
                CombSort(combSortResult);
                sw.Stop();
                combSortTicks += sw.ElapsedTicks;

                // Array.Sort
                var arraySortResult = list.ToArray();
                sw.Reset();
                sw.Start();
                Array.Sort(arraySortResult);
                sw.Stop();
                arraySortTicks += sw.ElapsedTicks;

                // correctness
                for (var n = 0; n < size; n++)
                {
                    if (radixSortResult[n] != arraySortResult[n])
                        Console.WriteLine("radixSortResult[{0}]: {1}, arraySortResult[{0}]: {2}", n, radixSortResult[n], arraySortResult[n]);
                    if (combSortResult[n] != arraySortResult[n])
                        Console.WriteLine("combSortResult[{0}]: {1}, arraySortResult[{0}]: {2}", n, combSortResult[n], arraySortResult[n]);
                }
            }

            Console.WriteLine("radix sort: {0} ({1:F})", radixSortTicks / count, radixSortTicks / (double)arraySortTicks);
            Console.WriteLine("comb sort: {0} ({1:F})", combSortTicks / count, combSortTicks / (double)arraySortTicks);
            Console.WriteLine("Array.Sort: {0} ({1:F})", arraySortTicks / count, arraySortTicks / (double)arraySortTicks);
        }


        static void RadixSort(IList<UInt32> list)
        {
            var tables = new int[sizeof(UInt32)][];
            for (var p = 0; p < tables.Length; p++)
                tables[p] = new int[0xFF + 1];

            // histgramming
            foreach (var x in list)
            {
                var y = x;
                for (var p = 0; p < tables.Length; p++)
                {
                    tables[p][(y + 1) & 0xFF]++;
                    y = y >> 8;
                }
            }

            // sum the histgrams
            foreach (var table in tables)
            {
                table[0] = 0;
                for (var n = 1; n < table.Length; n++)
                    table[n] += table[n - 1];
            }

            // read/write histgram, copy
            IList<UInt32> array = new UInt32[list.Count];
            Action swap = () => { var temp = list; list = array; array = temp; };
            for (var p = 0; p < tables.Length; p++)
            {
                var table = tables[p];
                foreach (var x in list)
                {
                    var y = (x >> p * 8) & 0xFF;
                    array[table[y]] = x;
                    table[y]++;
                }
                swap();
            }
        }

        static void CombSort(IList<UInt32> list)
        {
            const double shrinkFactor = 1.247330950103979; // 1.0 / (1.0 - 1.0 / Math.Pow(Math.E, Math.PI));
            var gap = list.Count;
            var swapped = true;
            while (gap > 1 || swapped)
            {
                if (gap > 1)
                    gap = (int)(gap / shrinkFactor);
                swapped = false;
                for (int i = 0; i + gap < list.Count; i++)
                {
                    if (list[i].CompareTo(list[i + gap]) > 0)
                    {
                        var t = list[i];
                        list[i] = list[i + gap];
                        list[i + gap] = t;
                        swapped = true;
                    }
                }
            }
        }
    }
}

ksksts / junk / source — bitbucket.org

結果は次の通り。
適当に比較したときは処理時間がArray.Sortの2倍以上で話にならないと思っていたけど、要素数が膨大になるにつれてそれなりに差が小さくなってきて少し嬉しい。
comb sortは遅いけどバブルソートの改良版と考えるとそれなりに良いような気がする。

size: 1000
radix sort: 3541 (2.88)
comb sort: 27689 (22.50)
Array.Sort: 1230 (1.00)
size: 10000
radix sort: 20451 (1.68)
comb sort: 417744 (34.33)
Array.Sort: 12167 (1.00)
size: 100000
radix sort: 207950 (1.45)
comb sort: 5288921 (36.95)
Array.Sort: 143143 (1.00)
size: 1000000
radix sort: 2081360 (1.30)
comb sort: 65056745 (40.50)
Array.Sort: 1606207 (1.00)

Abbreviation Scoring(LiquidMetal)をC#で書いてみた

steps to phantasien(2009-09-12)を読んでおもしろそうだったからC#で書いてみた。
といってもObjective-CもRubyも知らない（読めない）ので元のNSString_BLTRExtensions.mのJavaScript版であるLiquidMetalをC#で書き直しただけ。誰でもできる簡単なお仕事。

ソースコードはBitBucketのリポジトリksksts / junk / source — bitbucket.orgに。

あとサンプル（デモ）をよくわかんないけどSilverlightで書いてみた。
StringsとAbbreviationの変更に応じてインクリメンタルにスコアを再計算してResultsを更新するだけ。

 ->AbbreviationScoreSample

こんなのJavaScriptでもできるからわざわざSilverlightでする意味もないけど、C#で書いたものを簡単に動かして見せることができるのは便利かも、という感想。
ただ一般のクラスライブラリとSilverlightのクラスライブラリのプロジェクトが別っぽいのが面倒。両方で使いたい場合はどうすればいいんだろう？ソースは共通でプロジェクトを別に（2つ）作るのかな。