为什么`注入'非常慢？

Question

这是基准

require 'benchmark'

# create random array
arr = 40000.times.map { rand(100000).to_s }

r1 = ''
r2 = ''
r3 = ''

Benchmark.bm do |x|
    x.report {
        r1 = (arr.map { |s|
            "[#{s}]"
        }).join
    }

    x.report {
        r2 = arr.inject('') { |memo, s|
            memo + "[#{s}]"
        }
    }

    x.report {
        r3 = ''
        arr.each { |s|
            r3 << "[#{s}]"
        }
    }
end

# confirm result is same
puts r1 == r2
puts r2 == r3

这是结果

       user     system      total        real
   0.047000   0.000000   0.047000 (  0.046875)
   5.031000   0.844000   5.875000 (  5.875000)
   0.031000   0.000000   0.031000 (  0.031250)
true
true

有没有办法让inject速度更快？

Answer 1

这是我的猜测:与其他两种方法不同,方法inject一直在创造越来越大的字符串.所有这些(除了最后一个)都是临时的,必须进行垃圾收集.这就浪费了内存和CPU.这也是Shlemiel the Painter算法的一个很好的例子.

...... Spolsky打算类比的低效率是C语言的空终止字符数组(即字符串)重复串联的糟糕编程实践,其中目标字符串的位置必须从头开始重新计算每次都是字符串,因为它不是从先前的串联中继承的....

方法map创建了许多小字符串,因此,至少,它不会花费太多时间来分配内存.

更新

正如Yevgeniy Anfilofyev在评论中指出的那样,你可以通过不创建任何大字符串来避免创建许多大字符串.继续追加memo.

r2 = arr.inject('') { |memo, s|
  memo << "[#{s}]"
}

这工作,因为这两个String#+和String#<<的字符串返回一个新值.