ksksts's blog: C#で実装したradix sortとArray.Sortのquick sortとの比較で実行速度で.NET FrameworkのArray.Sort メソッド (System)とかを上回るのは難しいと感じた時点で目的を実装例を示すだけに変更。Decimal型やString型に対応しようと思っていたけど、面倒くさくなったから符号なし整数型、符号付整数型、浮動小数点数型で止めとく。
stereopsis : graphics : radix tricksのコードを参考にして書いた。
おおまかな処理の流れは次の通り。
- ヒストグラムをまとめて作成（histgramming）
- ヒストグラムの値を加算（sum the histgrams）
- 要素の並べ替え（read/write histgram, copy）
インターフェースはこんな感じ。
RadixSorter.cs
public static void Sort<T>(IList<T> list, Func<T, UInt32> converter, SortOrder sortOrder)
ソートに使用するキーを指定しながらソートできるのがおもしろい。
struct Pair<TFirst, TSecond>このPair型に対して、
{
public TFirst First { get; set; }
public TSecond Second { get; set; }
}
RadixSorter.Sort(result, x => x.Second, RadixSorter.SortOrder.Ascending);とすると、次のCompareTo（Firstで比較＆Firstが等しい場合はSecondで比較）でソートした場合と同じ結果が得られる。
RadixSorter.Sort(result, x => x.First, RadixSorter.SortOrder.Ascending);
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
// 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
// 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
// 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
0 件のコメント:
コメントを投稿