ruby - 为什么我的插入排序比合并排序快？

Question

# 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 倍以上。

insertion0.001294 seconds.merge0.017322 seconds

我的猜测是，我使用了一些计算量大的方法，例如 shift 和 concat，但相差 10 倍太过分了。

如何改进归并排序？

Answer 1

这里有很多东西:

1. 这不是插入排序，而是冒泡排序。
2. (i..0).each 什么都不做，因为范围不能以相反的顺序进行(您的规范未通过)。请改用 downto。
3. 逻辑本身就是错误的，如果你的最后一个索引在字符串的开头，那么你想在第二个元素小于第一个元素时进行交换。
4. 您的规范使用相同的数组，但插入方法会改变数组，因此当它到达合并排序时，它已经排序。
5. 没有充分的理由将它们放在 Array 上(除了它的新颖性之外)，一般来说，猴子修补是一种不好的做法(我会解释原因，但这有点超出了这个回应的范围) .
6. swap 方法可以通过多重赋值来简化 self[a], self[b] = self[b], self[a]。
7. 名称first、second、previous、next 都令人困惑。它们的名称暗示它们是元素，但实际上它们是索引，我会重命名为 index1(可能是 first_index，但可能会变得冗长)。
8. 为什么要在 count 和 size 之间切换？这很令人困惑，并且看起来像是您复制并粘贴了其他人的代码(而且其中一个函数会改变数组而另一个函数不会改变的事实，一般来说，合并排序看起来像是由知道的人编写的他们在做什么，而“插入”类型则没有)。
9. 合并排序可能比较慢，因为它在不需要的地方创建了大量数组(它没有副作用，但从性能的角度来看，最好只复制数组，然后根据开始和结束索引对其进行排序。
10. 这些测试不是很有用，因为它们只对一个数组进行排序。假设数组已经大部分排序，那么冒泡排序必须执行的交换非常少，因此它只需遍历数组多次即可完成。
11. 这些调用之间可能存在环境差异(优化、垃圾收集状态)，最好使用基准库。它有 bmbm它试图最小化这些差异。
12. 因为您在计时器 unsorted.insertion.should eq(unsorted.sort) 内运行测试，所以您不仅在为排序计时，还在为 Ruby 的 unsorted 计时.sort 以及 RSpec 断言。最好直接把排序包裹在时序代码中，然后再输出结果。