ruby - 为什么这种数组构建方法这么慢？

Question

这种方法在 50 个市场和 2,500 个流（约 250,000 次迭代）中需要 7 多秒。为什么这么慢？

def matrix
  [:origin, :destination].collect do |location|
    markets.collect do |market|
      network.flows.collect { |flow| flow[location] == market ? 1 : 0 }
    end
  end.flatten
end

我知道缓慢来自于基于我运行的基准对一个市场与另一个市场进行的比较。

以下是正在比较的课程的相关部分。

module FreightFlow
  class Market
    include ActiveAttr::Model

    attribute :coordinates

    def ==(value)
      coordinates == value.coordinates
    end

  end
end

加快速度的最佳方法是什么？

score 1 · Accepted Answer

You are constructing 100 intermediate collections (2*50) comprising of a total of 250,000 (2*50*2500) elements, and then flattening it at the end. I would try constructing the whole data structure in one pass. Make sure that markets and network.flows are stored in a hash or set. Maybe something like:

def matrix
  network.flows.collect do |flow|
    (markets.has_key? flow[:origin] or 
     markets.has_key? flow[:destination]) ? 1 : 0
  end
end

score 0 · Accepted Answer

这是一件简单的事情，但它可以帮助......

在你最里面的循环中，你正在做：

network.flows.collect { |flow| flow[location] == market ? 1 : 0 }

不要使用三元语句转换为1or 0，而是使用trueandfalse布尔值：

network.flows.collect { |flow| flow[location] == market }

这在速度上差别不大，但在这么多嵌套循环的过程中，它会累加起来。

此外，它还允许您使用正在生成的矩阵来简化测试。不必比较1or 0，您可以将条件测试简化为if flow[location],if !flow[location] or unless flow[location]，再次为每个测试加快应用程序的速度。如果它们深深地嵌套在循环中，这很可能，那一点点可以再次加起来。

当速度很重要时，重要的事情是使用 Ruby 的 Benchmark 类来测试执行相同任务的各种方法。然后，而不是猜测，你知道什么是有效的。你会在 Stack Overflow 上找到很多问题，我在其中提供了一个答案，其中包含一个基准，显示各种做事方式之间的速度差异。有时差异非常大。例如：

require 'benchmark'

puts `ruby -v`

def test1()
  true
end

def test2(p1)
  true
end

def test3(p1, p2)
  true
end

N = 10_000_000
Benchmark.bm(5) do |b|
  b.report('?:') { N.times { (1 == 1) ? 1 : 0 } }
  b.report('==') { N.times { (1 == 1) } }
  b.report('if') {
    N.times {
      if (1 == 1)
        1
      else
        0
      end
    }
  }
end

Benchmark.bm(5) do |b|
  b.report('test1') { N.times { test1() } }
  b.report('test2') { N.times { test2('foo') } }
  b.report('test3') { N.times { test3('foo', 'bar') } }
  b.report('test4') { N.times { true } }
end

结果：

ruby 1.9.3p392 (2013-02-22 revision 39386) [x86_64-darwin10.8.0]
            user     system      total        real
?:      1.880000   0.000000   1.880000 (  1.878676)
==      1.780000   0.000000   1.780000 (  1.785718)
if      1.920000   0.000000   1.920000 (  1.914225)
            user     system      total        real
test1   2.760000   0.000000   2.760000 (  2.760861)
test2   4.800000   0.000000   4.800000 (  4.808184)
test3   6.920000   0.000000   6.920000 (  6.915318)
test4   1.640000   0.000000   1.640000 (  1.637506)

ruby 2.0.0p0 (2013-02-24 revision 39474) [x86_64-darwin10.8.0]
            user     system      total        real
?:      2.280000   0.000000   2.280000 (  2.285408)
==      2.090000   0.010000   2.100000 (  2.087504)
if      2.350000   0.000000   2.350000 (  2.363972)
            user     system      total        real
test1   2.900000   0.010000   2.910000 (  2.899922)
test2   7.070000   0.010000   7.080000 (  7.092513)
test3  11.010000   0.030000  11.040000 ( 11.033432)
test4   1.660000   0.000000   1.660000 (  1.667247)

有两组不同的测试。首先是看看简单的条件测试与使用的区别是什么==不使用三元组来获得布尔值有什么区别。二是测试调用方法的效果，单参数的方法，双参数的方法，对比“inline-code”，找出调用方法时setup和tear-down的成本。

现代 C 编译器在发出要编译的汇编语言之前分析代码时会做一些惊人的事情。我们可以根据大小或速度对它们进行微调。当我们追求速度时，程序会随着编译器寻找可以展开的循环并放置它可以“内联”的代码而增长，以避免 CPU 跳来跳去并丢弃缓存中的内容。

Ruby 在语言链中的位置要高得多，但一些相同的想法仍然适用。我们可以用非常 DRY 的方式编写，避免重复并使用方法和类来抽象我们的数据，但代价是降低了处理速度。答案是智能地编写代码，不要浪费 CPU 时间和展开/内联以提高速度，而在其他时间保持干燥以使代码更易于维护。

这都是一种平衡行为，有时间同时写两种方式。

score 0 · Accepted Answer

在流量中记忆市场指数比任何其他解决方案都要快得多。时间从提出问题时的约 30 秒减少到 0.6 秒。

首先，我flow_index在Network课堂上添加了一个。它存储包含市场的流量的索引。

def flow_index
  @flow_index ||= begin
    flow_index = {}
    [:origin, :destination].each do |location|
      flow_index[location] = {}
      flows.each { |flow| flow_index[location][flow[location]] = [] }
      flows.each_with_index { |flow, i| flow_index[location][flow[location]] << i }
    end
    flow_index
  end
end

然后，我重构了matrix使用流索引的方法。

def matrix
  base_row = network.flows.count.times.collect { 0 }
  [:origin, :destination].collect do |location|
    markets.collect do |market|
      row = base_row.dup
      network.flow_index[location][market].each do |i|
        row[i] = 1
      end
      row
    end
  end.flatten
end

使用base_row全 0 创建，您只需在该市场的 flow_index 位置替换为 1。

ruby - 为什么这种数组构建方法这么慢？

3 回答 3

Related

Reference