2 
# sort.rb
class Array
  def insertion
    (1..self.count).each do |i|
      (i..0).each do |j|
        first = j - 1
        second = j
        if self[second] > self[first]
          swap(second, first)
        end
      end
    end
    self
  end

  def mergesort
    return self if self.size <= 1
    mid = self.size / 2
    left = self[0, mid]
    right = self[mid, self.size-mid]
    merge_array(left.mergesort, right.mergesort)
  end

  # helpers

  def merge_array(left, right)
    sorted = []
    until left.empty? or right.empty?
      if left.first <= right.first
        sorted << left.shift
      else
        sorted << right.shift
      end
    end
    sorted.concat(left).concat(right)
  end

  def swap(previous, current)
    copy = self[previous]
    self[previous] = self[current]
    self[current] = copy
  end
end

私のrspecファイル：

require './sort'

unsorted = 5000.downto(1).to_a.shuffle

describe Array, "#insertion" do
  it "sorts using insertion sort" do
    time = Time.now
    unsorted.insertion.should eq(unsorted.sort)
    puts "insertion"
    puts Time.now - time
  end
end

describe Array, "#merge" do
  it "sorts using merge sort" do
    time = Time.now
    unsorted.mergesort.should eq(unsorted.sort)
    puts "merge"
    puts Time.now - time
  end
end

挿入ソートの実行時間は平均で O(n^2) であるのに対し、マージ ソートは O(n*log(n)) であるため、挿入ソートはマージ ソートよりも遅くなるはずです。しかし、上記のテスト コードを実行すると、マージは挿入よりも 10 倍以上遅くなります。

挿入
0.001294 秒

。マージ
0.017322 秒

私の推測では、shiftやconcatのような計算コストの高い方法を使用していますが、10 倍の差があるのは大きすぎます。

マージソートを改善するにはどうすればよいですか?

4

2 に答える 2

8

ここには多くのものがあります：

  1. これは挿入ソートではなく、バブルソートです。
  2. (i..0).each範囲を逆順にすることはできないため、何もしません（あなたの仕様は合格しません）。downto代わりに使用してください。
  3. ロジック自体が間違っています。最後のインデックスが文字列の先頭にある場合、2 番目の要素が最初の要素よりも小さいときにスワップする必要があります。
  4. 仕様は同じ配列を使用しますが、挿入メソッドは配列を変更するため、マージソートに到達するまでに、すでにソートされています.
  5. これらを Array に配置する正当な理由はありません (目新しさを超えて)。一般に、モンキー パッチは悪い習慣です (理由を説明しますが、この応答の範囲を超えています)。
  6. スワップ メソッドは、複数の代入を使用して簡略化できますself[a], self[b] = self[b], self[a]。
  7. 名前first、second、previous、nextはすべて紛らわしいです。それらの名前は、それらが要素であることを暗示していますが、実際にはインデックスです。名前をindex1(おそらくfirst_index、しかし冗長になる可能性があります) のように変更します。
  8. なぜ と を切り替えるのcountですsizeか? これは紛らわしく、他の人のコードをコピーして貼り付けたように見えます (それと、関数の 1 つが配列を変更し、もう 1 つが変更しないという事実は、一般的に、マージソートは知っている人によって書かれたように見えます)。彼らがしていること、そして「挿入」ソートはそうではありません）。
  9. マージソートは、必要のない場所に大量の配列を作成するため、おそらく遅くなります (副作用はありませんが、パフォーマンスの観点からは、配列だけdupを作成してから、 start およびインデックスを終了します。
  10. テストは 1 つの配列のみをソートするため、あまり役に立ちません。配列の大部分が既にソートされているとします。その場合、バブル ソートで実行する必要があるスワップはほとんどないため、配列を何度も反復するだけで完了します。
  11. これらの呼び出しの間には環境の違い (最適化、ガベージ コレクションの状態) が発生する可能性があるため、Benchmark ライブラリを使用することをお勧めします。bmbmこれらの違いを最小限に抑える試みがあります。
  12. timer 内でテストを実行しているためunsorted.insertion.should eq(unsorted.sort)、並べ替えのタイミングだけでなく、Rubyunsorted.sortと RSpec アサーションのタイミングも合わせています。並べ替えをタイミングコードにラップして、後で結果を出力する方がよいでしょう。
于 2013-03-08T02:05:56.733 に答える
4

アイデア:

  • テストサイズを数十万に増やして、いくつかの異なる配列で平均してみてください。これは、挿入ソートが最良の場合、マージソートと比較して非常に高速になるためです。
  • サイズを知っている必要があるため、配列を動的に構築するのではなく、マージで配列を事前に割り当てます
  • 時間の一致から正しさ (... すべき) 呼び出しを取り除きます
于 2013-03-08T01:11:44.243 に答える