3

オブジェクトのシーケンスがあり、それぞれに 0 から ushort.MaxValue (0-65535) までのシーケンス番号があります。シーケンスには最大で約 10,000 個のアイテムがあるため、重複があってはならず、アイテムはロード方法によってほとんどソートされています。データに順番にアクセスするだけでよいので、リストに入れる必要はありません。また、かなり頻繁に行われるものであるため、Big-O が高すぎることはありません。

このリストをソートする最良の方法は何ですか?

シーケンスの例は次のようになります (この例では、シーケンス番号が 1 バイトで、255 でラップすると仮定しています)。

240 241 242 243 244 250 251 245 246 248 247 249 252 253 0 1 2 254 255 3 4 5 6

正しい順序は次のようになります

240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 0 1 2 3 4 5 6

ushort.MaxValue サイズの配列を作成し、位置をインクリメントするなど、いくつかの異なるアプローチがありますが、それは非常に非効率的な方法のように思えます。また、受信したデータが順番にジャンプすると、いくつかの問題が発生します。ただし、パフォーマンスは O(1) です。

もう 1 つの方法は、アイテムを通常どおりに並べてから、分割 (6-240) を見つけて、最初のアイテムを最後に移動することです。しかし、それが良い考えかどうかはわかりません。

私の 3 番目のアイデアは、間違ったシーケンス番号が見つかるまでシーケンスをループし、正しい番号が見つかるまで先を見て、正しい位置に移動することです。ただし、早い段階で間違ったシーケンス番号がある場合、これは潜在的に非常に遅くなる可能性があります。

4

2 に答える 2

1

これはあなたが探しているものですか？

var groups = ints.GroupBy(x => x < 255 / 2)
     .OrderByDescending(list => list.ElementAt(0))
     .Select(x => x.OrderBy(u => u))
     .SelectMany(i => i).ToList();

例 : 

int[] ints = new int[] { 88, 89, 90, 91, 92, 0, 1, 2, 3, 92, 93, 94, 95, 96, 97, 4, 5, 6, 7, 8, 99, 100, 9, 10, 11, 12, 13 };

外：

88 89 90 91 92 92 93 94 95 96 97 99 100 0 1 2 3 4 5 6 7 8 9 10 11 12 13

于 2013-06-12T09:42:59.800 に答える