在 ruby 中，接收 *array 还是在方法内复制和排列更好？

Question

我正在尝试 Quicksort in Ruby. After implementing some of the inlace algorithms, I felt that using Ruby's partition 方法的一些实现，即使它不会提供就地解决方案，但它会提供一个非常好的可读解决方案。

我的第一个解决方案是这个，除了总是使用数组的最后一个元素作为基准之外，它看起来还不错。

def quick_sort3(ary)
  return ary if ary.size <= 1
  left,right = ary.partition { |v| v < ary.last }
  pivot_value = right.pop
  quick_sort3(left) + [pivot_value] +  quick_sort3(right)
end

经过一番搜索后，我发现这个 answer 有一个非常相似的解决方案，但对初始主元的选择更好，在此处使用相同的变量名和块传递给分区。

def quick_sort6(*ary)
  return ary if ary.empty?
  pivot_value = ary.delete_at(rand(ary.size))
  left,right = ary.partition { |v| v < pivot_value }
  return *quick_sort6(*left), pivot_value, *quick_sort6(*right)
end

我觉得我可以通过对 select 随机枢轴使用相同的方法来改进我的解决方案。

def quick_sort4(ary)
  return ary if ary.size <= 1
  pivot_value = ary.delete_at(rand(ary.size))
  left,right = ary.partition { |v| v < pivot_value }
  quick_sort4(left) + [pivot_value] +  quick_sort4(right)
end

此版本 quick_sort4 与链接答案 [=32=] 相比的缺点是 quick_sort4 更改了输入数组，而 quick_sort6 没有。我假设这就是 Jorg 选择接收 splat 数组 vs 数组的原因？

我的解决方法是简单地复制传入的数组，然后在复制的数组而不是原始数组上执行 delete_at。

def quick_sort5(ary_in)
  return ary_in if ary_in.size <= 1
  ary = ary_in.dup
  pivot_value = ary.delete_at(rand(ary.size))
  left,right = ary.partition { |v| v < pivot_value }
  quick_sort5(left) + [pivot_value] +  quick_sort5(right)
end

我的问题是，使用 splats 的 quick_sort6 和使用 dup 的 quick_sort5 之间有什么显着差异吗？我假设使用 splats 是为了避免更改输入数组，但是我还缺少其他东西吗？

Answer 1

在这种情况下，splat 样式的问题在于它会造成尴尬 API。

大多数时候，消费者代码会有一系列需要排序的东西：

stuff = [1, 2, 3]
sort(stuff)

splat 样式让消费者改为这样做：

stuff = [1, 2, 3]
sort(*stuff)

这两个调用可能最终会做同样的事情，但是作为用户我正在对数组进行排序，因此我希望将数组传递给方法，而不是传递每个将数组元素单独添加到方法中。

此现象的另一个标签 abstraction leakage - 您允许 sort 方法的实现定义其接口。通常在 Ruby 中，这是不受欢迎的。

Answer 2

就性能而言，quick_sort6 是您的最佳选择。使用一些随机数据：

require 'benchmark'

def quick_sort3(ary)
  return ary if ary.size <= 1
  left,right = ary.partition { |v| v < ary.last }
  pivot_value = right.pop
  quick_sort3(left) + [pivot_value] +  quick_sort3(right)
end

def quick_sort6(*ary)
  return ary if ary.empty?
  pivot_value = ary.delete_at(rand(ary.size))
  left,right = ary.partition { |v| v < pivot_value }
  return *quick_sort6(*left), pivot_value, *quick_sort6(*right)
end

def quick_sort4(ary)
  return ary if ary.size <= 1
  pivot_value = ary.delete_at(rand(ary.size))
  left,right = ary.partition { |v| v < pivot_value }
  quick_sort4(left) + [pivot_value] +  quick_sort4(right)
end

def quick_sort5(ary_in)
  return ary_in if ary_in.size <= 1
  ary = ary_in.dup
  pivot_value = ary.delete_at(rand(ary.size))
  left,right = ary.partition { |v| v < pivot_value }
  quick_sort5(left) + [pivot_value] +  quick_sort5(right)
end

random_arrays = Array.new(5000) do
  Array.new(500) { rand(1...500) }.uniq
end

Benchmark.bm do |benchmark|
  benchmark.report("quick_sort3") do
    random_arrays.each do |ra|
      quick_sort3(ra.dup)
    end
  end
  benchmark.report("quick_sort6") do
    random_arrays.each do |ra|
      quick_sort6(ra.dup)
    end
  end
  benchmark.report("quick_sort4") do
    random_arrays.each do |ra|
      quick_sort4(ra.dup)
    end
  end
  benchmark.report("quick_sort5") do
    random_arrays.each do |ra|
      quick_sort5(ra.dup)
    end
  end
end

给出结果

       user     system      total        real
quick_sort3  1.389173   0.019380   1.408553 (  1.411771)
quick_sort6  0.004399   0.000022   0.004421 (  0.004487)
quick_sort4  1.208003   0.002573   1.210576 (  1.214131)
quick_sort5  1.458327   0.000867   1.459194 (  1.459882)

在 ruby 中，接收 *array 还是在方法内复制和排列更好？

In ruby, Is it better to receive *array or to duplicate and array inside a method?

ruby

quicksort