6

これは宿題ではありません。学校に通うお金がないので、高速道路の料金所でシフトを組みながら独学しています (顧客が少ない長い夜)。

私は単純な「マージソート」を実装しようとしていました。最初に考え、実際の学習が必要な場合は頭を少し伸ばしてから、使用しているマニュアルの解決策を見てください: "2008-08-21 | アルゴリズムの設計マニュアル | スプリンガー | Steven S. Skiena | ISBN-1848000693".

配列をバッファーとして使用して「マージ」ステップを実装するソリューションを思いついたので、以下に貼り付けます。著者はキューを使用しているので、次のように思います。

  • 代わりにキューを使用する必要がありますか?
  • ある方法と他の方法の利点は何ですか? （彼はトップアルゴリズムであり、私は初心者なので、明らかに彼の方法の方が優れていますが、その長所を正確に特定することはできません。助けてください）
  • 彼の選択を支配したトレードオフ/仮定は何ですか?

これが私のコードです（完全を期すために分割機能の実装も含めていますが、mergeここではステップを確認しているだけだと思います。私の質問は具体的であるため、これはコードレビューの投稿ではないと思います1 つのメソッドだけに、および別のメソッドと比較したそのパフォーマンスについて):

package exercises;
public class MergeSort {
  private static void merge(int[] values, int leftStart, int midPoint,
      int rightEnd) {
    int intervalSize = rightEnd - leftStart;
    int[] mergeSpace = new int[intervalSize];
    int nowMerging = 0;
    int pointLeft = leftStart;
    int pointRight = midPoint;
    do {
      if (values[pointLeft] <= values[pointRight]) {
        mergeSpace[nowMerging] = values[pointLeft];
        pointLeft++;
      } else {
        mergeSpace[nowMerging] = values[pointRight];
        pointRight++;
      }
      nowMerging++;
    } while (pointLeft < midPoint && pointRight < rightEnd);
    int fillFromPoint = pointLeft < midPoint ? pointLeft : pointRight;
    System.arraycopy(values, fillFromPoint, mergeSpace, nowMerging,
        intervalSize - nowMerging);
    System.arraycopy(mergeSpace, 0, values, leftStart, intervalSize);
  }
  public static void mergeSort(int[] values) {
    mergeSort(values, 0, values.length);
  }
  private static void mergeSort(int[] values, int start, int end) {
    int intervalSize = end - start;
    if (intervalSize < 2) {
      return;
    }
    boolean isIntervalSizeEven = intervalSize % 2 == 0;
    int splittingAdjustment = isIntervalSizeEven ? 0 : 1;
    int halfSize = intervalSize / 2;
    int leftStart = start;
    int rightEnd = end;
    int midPoint = start + halfSize + splittingAdjustment;
    mergeSort(values, leftStart, midPoint);
    mergeSort(values, midPoint, rightEnd);
    merge(values, leftStart, midPoint, rightEnd);
  }
}

教科書の参照ソリューションは次のとおりです（Cにあるため、タグを追加しています）

merge(item_type s[], int low, int middle, int high)
{
  int i; /* counter */
  queue buffer1, buffer2; /* buffers to hold elements for merging */
  init_queue(&buffer1);
  init_queue(&buffer2);
  for (i=low; i<=middle; i++) enqueue(&buffer1,s[i]);
  for (i=middle+1; i<=high; i++) enqueue(&buffer2,s[i]);
  i = low;
  while (!(empty_queue(&buffer1) || empty_queue(&buffer2))) {
    if (headq(&buffer1) <= headq(&buffer2))
      s[i++] = dequeue(&buffer1);
    else
      s[i++] = dequeue(&buffer2);
  }
  while (!empty_queue(&buffer1)) s[i++] = dequeue(&buffer1);
  while (!empty_queue(&buffer2)) s[i++] = dequeue(&buffer2);
}
4

2 に答える 2

2

抽象的に言えば、キュ​​ーは、エンキュー、デキュー、ピーク、および空である操作をサポートする単なるオブジェクトです。さまざまな方法で実装できます (循環バッファーの使用、リンク リストの使用など)。

論理的に言えば、マージ アルゴリズムは、キューの観点から説明するのが最も簡単です。マージする値を保持する 2 つのキューから始めて、これらのキューに対してピーク、空、およびデキュー操作を繰り返し適用して、1 つの並べ替えられたシーケンスを再構築します。

配列を使用した実装では、キューを使用している場合と同じことを効果的に行っています。配列を使用してこれらのキューを実装することを選択しました。キューを使用するよりも「良い」または「悪い」とは限りません。キューを使用すると、マージ アルゴリズムの高レベルの操作がより明確になりますが、非効率性が生じる可能性があります (ただし、ベンチマークを実施しないと確実なことは言えません)。配列を使用すると、少し効率が良くなる可能性があります (これもテストする必要があります!) が、アルゴリズムの高レベルの操作がわかりにくくなる可能性があります。Skienna の観点からは、アルゴリズムの高レベルの詳細が明確になるため、キューを使用する方が良いかもしれません。あなたの観点からは、パフォーマンス上の懸念から配列の方が優れている可能性があります。

お役に立てれば！

于 2012-08-21T20:58:53.703 に答える
0

主にコンパイラの品質に起因するマイナーな定数要因について心配しています。あなたがそれについて心配しているように見えることを考えると、配列はあなたの友達です。以下は、整数マージソートの C# 実装です。これは、可能な限りタイトに近いと思います。[編集:バグレットを修正しました。]

実際にもっとうまくやりたい場合は、自然なマージソートのようなものが必要です。2 の累乗でマージする代わりに、入力の隣接する非減少シーケンスを単純にマージします。これは確かに 2 の累乗より悪くはありませんが、入力データにソートされたシーケンス (つまり、純粋に降順の入力シーケンス以外のもの)が含まれている場合は、明らかに高速です。それは学生のための演習として残されています。

int[] MSort(int[] src) {
    var n = src.Length;
    var from = (int[]) src.Clone();
    var to = new int[n];
    for (var span = 1; span < n; span += span) {
        var i = 0;
        for (var j = 0; j < n; j += span + span) {
            var l = j;
            var lend = Math.Min(l + span, n);
            var r = lend;
            var rend = Math.Min(r + span, n);
            while (l < lend && r < rend) to[i++] = (from[l] <= from[r] ? from[l++] : from[r++]);
            while (l < lend)             to[i++] = from[l++];
            while (r < rend)             to[i++] = from[r++];
        }
        var tmp = from; from = to; to = tmp;
    }
    return from;
}
于 2012-08-22T01:09:11.337 に答える