float 型のフィールドを持つデータ構造があります。これらの構造体のコレクションは、float の値でソートする必要があります。これには基数ソートの実装がありますか。
そうでない場合、指数、符号、および仮数にアクセスする高速な方法はありますか。浮動小数点数を最初に仮数部、指数部、および前回の指数部でソートした場合。フロートを O(n) で並べ替えます。
質問する
3438 次
5 に答える
19
アップデート：
私はこのトピックに非常に興味を持っていたので、座って実装しました（この非常に高速でメモリを節約する実装を使用して）。また、これを読んで（celionに感謝）、フロートを仮数と指数に分割して並べ替える必要がないこともわかりました。ビットを1対1で取得し、intソートを実行する必要があります。負の値に注意する必要があります。負の値は、アルゴリズムの最後に正の値の前に逆に配置する必要があります（cpu時間を節約するために、アルゴリズムの最後の反復で1つのステップで作成しました）。
だからここに私のフロート基数ソートがあります：
public static float[] RadixSort(this float[] array)
{
// temporary array and the array of converted floats to ints
int[] t = new int[array.Length];
int[] a = new int[array.Length];
for (int i = 0; i < array.Length; i++)
a[i] = BitConverter.ToInt32(BitConverter.GetBytes(array[i]), 0);
// set the group length to 1, 2, 4, 8 or 16
// and see which one is quicker
int groupLength = 4;
int bitLength = 32;
// counting and prefix arrays
// (dimension is 2^r, the number of possible values of a r-bit number)
int[] count = new int[1 << groupLength];
int[] pref = new int[1 << groupLength];
int groups = bitLength / groupLength;
int mask = (1 << groupLength) - 1;
int negatives = 0, positives = 0;
for (int c = 0, shift = 0; c < groups; c++, shift += groupLength)
{
// reset count array
for (int j = 0; j < count.Length; j++)
count[j] = 0;
// counting elements of the c-th group
for (int i = 0; i < a.Length; i++)
{
count[(a[i] >> shift) & mask]++;
// additionally count all negative
// values in first round
if (c == 0 && a[i] < 0)
negatives++;
}
if (c == 0) positives = a.Length - negatives;
// calculating prefixes
pref[0] = 0;
for (int i = 1; i < count.Length; i++)
pref[i] = pref[i - 1] + count[i - 1];
// from a[] to t[] elements ordered by c-th group
for (int i = 0; i < a.Length; i++){
// Get the right index to sort the number in
int index = pref[(a[i] >> shift) & mask]++;
if (c == groups - 1)
{
// We're in the last (most significant) group, if the
// number is negative, order them inversely in front
// of the array, pushing positive ones back.
if (a[i] < 0)
index = positives - (index - negatives) - 1;
else
index += negatives;
}
t[index] = a[i];
}
// a[]=t[] and start again until the last group
t.CopyTo(a, 0);
}
// Convert back the ints to the float array
float[] ret = new float[a.Length];
for (int i = 0; i < a.Length; i++)
ret[i] = BitConverter.ToSingle(BitConverter.GetBytes(a[i]), 0);
return ret;
}
関数の最初と最後で配列がコピーされ、floatがビット単位でintにコピーされて戻るため、int基数ソートよりも少し遅くなります。それにもかかわらず、関数全体は再びO（n）です。いずれにせよ、あなたが提案したように3回続けてソートするよりもはるかに高速です。最適化の余地はもうあまりありませんが、誰かがそうする場合は、遠慮なく教えてください。
降順で並べ替えるには、最後にこの行を変更します。
ret[i] = BitConverter.ToSingle(BitConverter.GetBytes(a[i]), 0);
これに：
ret[a.Length - i - 1] = BitConverter.ToSingle(BitConverter.GetBytes(a[i]), 0);
測定：
フロート（NaN、+ /-Inf、最小/最大値、0）と乱数のすべての特殊なケースを含むいくつかの短いテストを設定しました。Linqとまったく同じ順序で並べ替えるか、Array.Sortfloatを並べ替えます。
NaN -> -Inf -> Min -> Negative Nums -> 0 -> Positive Nums -> Max -> +Inf
だから私は1000万の数の巨大な配列でテストを実行しました：
float[] test = new float[10000000];
Random rnd = new Random();
for (int i = 0; i < test.Length; i++)
{
byte[] buffer = new byte[4];
rnd.NextBytes(buffer);
float rndfloat = BitConverter.ToSingle(buffer, 0);
switch(i){
case 0: { test[i] = float.MaxValue; break; }
case 1: { test[i] = float.MinValue; break; }
case 2: { test[i] = float.NaN; break; }
case 3: { test[i] = float.NegativeInfinity; break; }
case 4: { test[i] = float.PositiveInfinity; break; }
case 5: { test[i] = 0f; break; }
default: { test[i] = test[i] = rndfloat; break; }
}
}
そして、さまざまな並べ替えアルゴリズムの時間を止めました：
Stopwatch sw = new Stopwatch();
sw.Start();
float[] sorted1 = test.RadixSort();
sw.Stop();
Console.WriteLine(string.Format("RadixSort: {0}", sw.Elapsed));
sw.Reset();
sw.Start();
float[] sorted2 = test.OrderBy(x => x).ToArray();
sw.Stop();
Console.WriteLine(string.Format("Linq OrderBy: {0}", sw.Elapsed));
sw.Reset();
sw.Start();
Array.Sort(test);
float[] sorted3 = test;
sw.Stop();
Console.WriteLine(string.Format("Array.Sort: {0}", sw.Elapsed));
そして、出力は次のとおりでした（更新：デバッグではなくリリースビルドで実行されるようになりました）：
RadixSort: 00:00:03.9902332
Linq OrderBy: 00:00:17.4983272
Array.Sort: 00:00:03.1536785
Linqの約4倍以上の速度です。それは悪くない。しかし、まだそれほど速くはありませんがArray.Sort、それほど悪くはありません。しかし、私はこれに本当に驚いていました。非常に小さなアレイでは、Linqよりもわずかに遅いと予想していました。しかし、それから私はたった20の要素でテストを実行しました：
RadixSort: 00:00:00.0012944
Linq OrderBy: 00:00:00.0072271
Array.Sort: 00:00:00.0002979
今回でも、私の基数ソートはLinqよりも高速ですが、配列ソートよりもはるかに低速です。:)
アップデート2：
私はさらにいくつかの測定を行い、いくつかの興味深いことを発見しました。グループの長さの定数が長いほど、反復が少なくなり、メモリ使用量が多くなります。16ビットのグループ長（2回の反復のみ）を使用する場合、小さな配列を並べ替えるときに大きなメモリオーバーヘッドが発生しますがArray.Sort、約10万要素を超える配列の場合は、それほど多くない場合でも、打ち負かすことができます。チャートの軸は両方とも対数化されています。
（出典：daubmeier.de）
于 2010-04-21T17:29:50.003 に答える
2
フロートで基数ソートを実行する方法についての良い説明があります: http://www.codercorner.com/RadixSortRevisited.htm
すべての値が正の場合は、バイナリ表現を使用して問題を解決できます。リンクは、負の値を処理する方法を説明しています。
于 2010-04-21T18:06:28.573 に答える
1
ブロックを memcpy に使用するか、 aを aにunsafeエイリアスしてビットを抽出できます。float *uint *
于 2010-04-21T18:21:34.333 に答える
0
値が近すぎず、妥当な精度要件がある場合は、小数点の前後の実際の浮動小数点数を使用して並べ替えを行うことができます。
たとえば、最初の4つの小数（0かどうかに関係なく）を使用して並べ替えを行うことができます。
于 2010-04-21T17:18:21.933 に答える