两个 perm 函数都是在进入下一次递归的时候更改 src 数组的某个元素。为什么第一个耗时基本上是第二个耗时的一半呢?
def perm1(n, &block)
src = (1..n).to_a
r = []
scan = lambda do |m|
if (m == 0)
block.call(r)
else
(0..(src.size-1)).each do |i|
o = src[i]
src.delete_at(i) # 删除
r << o
scan.call(m-1)
src.insert(i, o) # 插入
r.pop
end
end
end
scan.call(n)
end
def perm2(n, &block)
src = (1..n).to_a
r = []
scan = lambda do |m|
if (m == 0)
block.call(r)
else
(0..(src.size-1)).each do |i|
o = src[i]
next unless o # 检查是否为false
src[i] = false
r << o
scan.call(m-1)
src[i] = o # 恢复为原数据
r.pop
end
end
end
scan.call(n)
end
require 'benchmark'
N = 10
Benchmark.bm do |r|
r.report do
cnt = 0
perm1(N) do |x|
#~ puts '=>' + x.inspect
cnt += 1
end
puts cnt
end
puts '---'
r.report do
cnt = 0
perm2(N) do |x|
#~ puts '=>' + x.inspect
cnt += 1
end
puts cnt
end
end