1

long 型 (昇順) の並べ替えられた数のシーケンスがいくつかあり、すべての要素を同じ順序で含む 1 つのマスター シーケンスを生成したいと考えています。この問題を解決するための最も効率的な並べ替えアルゴリズムを探しています。私は C# と .Net 4.0 をターゲットにしているため、並列処理をターゲットとするアイデアも歓迎します。

次に例を示します。
s1 = 1,2,3,5,7,13
s2 = 2,3,6
s3 = 4,5,6,7,8
結果のシーケンス = 1,2,2,3,3,4 ,5,5,6,6,7,7,8,13

編集: 2 つ (またはそれ以上) の同一の値がある場合、それらの 2 つ (またはそれ以上) の順序は重要ではありません。

4

5 に答える 5

4

シーケンスをマージするだけです。それらを再度ソートする必要はありません。

于 2012-05-04T13:48:02.587 に答える
4

私が知っている K-way マージを行う .NET Framework メソッドはありません。通常、これはプライオリティ キュー (多くの場合ヒープ) で行われます。それは難しくなく、非常に効率的です。K 個の並べ替えられたリストがあり、一緒に N 個のアイテムを保持すると、複雑さは O(N log K) になります。

私の記事A Generic Binary Heap Classで単純なバイナリ ヒープ クラスを示します。大きなテキスト ファイルの並べ替えでは、複数の並べ替えられたサブファイルの作成と、ヒープを使用した K-way マージの実行について説明しています。1 時間 (おそらくそれより短い時間) の学習が与えられた場合、おそらくそれをプログラムで使用するように適応させることができます。

于 2012-05-04T14:05:15.400 に答える
2

マージソートのようにシーケンスをマージするだけです。

そして、これは並列化可能です:

  1. マージ シーケンス (1/2 の 1 と 2)、(3/4 の 3 と 4)、…</li>
  2. マージ シーケンス (1/2/3/4 の 1/2 と 3/4)、(5/6/7/8 の 5/6 と 7/8)、…</li>
  3. …</li>

マージ機能は次のとおりです。

int j = 0;
int k = 0;
for(int i = 0; i < size_merged_seq; i++)
{
  if (j < size_seq1 && seq1[j] < seq2[k])
  {
    merged_seq[i] = seq1[j];
    j++;
  }
  else
  {
    merged_seq[i] = seq2[k];
    k++;
  }
}
于 2012-05-04T13:54:41.817 に答える
2

簡単な方法は、それらを 1 つずつマージすることです。ただし、これにはO(n*k^2)時間がかかります。ここで、kはシーケンスの数で、 はnシーケンス内のアイテムの平均数です。ただし、分割統治アプローチを使用すると、この時間を O(n*k*log k) に下げることができます。アルゴリズムは次のとおりです。

  1. k シーケンスをそれぞれ 2 つの要素の k/2 グループ (k が奇数の場合は 1 つの要素の 1 つのグループ) に分割します。
  2. 各グループのシーケンスをマージします。したがって、k/2 個の新しいグループが得られます。
  3. 単一のシーケンスが得られるまで繰り返します。
于 2012-05-04T14:05:58.123 に答える
1

アップデート：

すべてのアルゴリズムでそれが判明しました...それはまだ簡単な方法で高速です：

private static List<T> MergeSorted<T>(IEnumerable<IEnumerable<T>> sortedBunches)
{
    var list = sortedBunches.SelectMany(bunch => bunch).ToList();

    list.Sort();

    return list;
}

そしてレガシー目的のために...

優先順位を付けた最終バージョンは次のとおりです。

    private static IEnumerable<T> MergeSorted<T>(IEnumerable<IEnumerable<T>> sortedInts) where T : IComparable<T>
    {
        var enumerators = new List<IEnumerator<T>>(sortedInts.Select(ints => ints.GetEnumerator()).Where(e => e.MoveNext()));

        enumerators.Sort((e1, e2) => e1.Current.CompareTo(e2.Current));

        while (enumerators.Count > 1)
        {
            yield return enumerators[0].Current;

            if (enumerators[0].MoveNext())
            {
                if (enumerators[0].Current.CompareTo(enumerators[1].Current) == 1)
                {
                    var tmp = enumerators[0];
                    enumerators[0] = enumerators[1];
                    enumerators[1] = tmp;
                }
            }
            else
            {
                enumerators.RemoveAt(0);
            }
        }

        do
        {
            yield return enumerators[0].Current;
        } while (enumerators[0].MoveNext());
    }
于 2012-05-04T14:42:06.230 に答える