代码之家  ›  专栏  ›  技术社区  ›  Steely Wing

为什么“注入”很慢?

  •  3
  • Steely Wing  · 技术社区  · 12 年前

    这是基准

    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 更快?

    1 回复  |  直到 12 年前
        1
  •  6
  •   Sergio Tulentsev    12 年前

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

    …斯波尔斯基所类比的低效率是C风格空终止字符数组(即字符串)的重复串联的糟糕编程实践,其中每次都必须从字符串的开头重新计算目标字符串的位置,因为它不是从以前的串联中继承的。。。

    接近 map 创建了许多小字符串,所以,至少,它不会花费那么多时间来分配内存。

    使现代化

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

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

    这样做是因为 String#+ String#<< 为字符串返回一个新值。