新手问题 自写全排列算法发现一个性能差异问题

cre16yu · 2020年10月02日 · 584 次阅读

两个 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
暂无回复。
需要 登录 后方可回复, 如果你还没有账号请 注册新账号