如何在Ruby中有效地连接多个数组？

Question

我只想在Ruby中连接多个数组,并且找不到令人满意的方法.

输入示例:

foo = [1, 2, 3]
bar = [4, 5, 6]
baz = [7, 8, 9]

预期结果:(不修改现有数组)

[1, 2, 3, 4, 5, 6, 7, 8, 9]

我的实际数组要大得多,所以我对一个有效的解决方案很感兴趣.可能还有三个以上的数组,因此首选短语法.

到目前为止我尝试过的

• foo + bar + baz是显而易见的,它简洁明了.但它被评估为(foo + bar) + baz.换句话说:它创建一个[1, 2, 3, 4, 5, 6]在整个操作后被抛弃的中间数组.如文档中所述:

  重复使用+=数组可能效率很低

• [*foo, *bar, *baz]基本上内联对大型数组效率不高的元素.它看起来更像是对我的黑客攻击.

• [foo, bar, baz].flatten(1) 看起来比上面更糟糕,表现明智.

• [].concat(foo).concat(bar).concat(baz) 是最快的,但它看起来很麻烦,需要多个方法调用.

对于这样的基本任务,不应该有简单的类方法吗？就像是:

Array.concat(foo, bar, baz)

我错过了一些明显的东西吗

Answer 1

如果您已经确定多个连接是最快的方法,则可以使用reduce更好地编写它:

[foo, bar, baz].reduce([], :concat)

Answer 2

我创建的又一标杆,比较+,concat和一个自定义的C扩展使用数组的可变数目.

结果

• C扩展总是最快,大约快2-3倍 concat
• plus 如果你连接许多数组,会变得非常慢

结论

虽然"2-3x"听起来像是一个巨大的进步,但绝对数字只有几毫秒.由于不必调整阵列大小,我期待更大的差异,但这显然不是一个重要因素.

IMO,concat是一个不错的表演者,我认为没有迫切需要C扩展.

我的测试数组包含nil值.其他元素似乎没有产生不同的结果(相对而言).

我没有包括flat_map,因为它相当于concat.

Concatenating 3 arrays of size 100 (10000 times)
                 user     system      total        real
plus         0.020000   0.000000   0.020000 (  0.027927)
concat       0.020000   0.010000   0.030000 (  0.033204)
c_extension  0.010000   0.010000   0.020000 (  0.010727)

Concatenating 10 arrays of size 100 (10000 times)
                 user     system      total        real
plus         0.110000   0.070000   0.180000 (  0.180417)
concat       0.050000   0.020000   0.070000 (  0.065299)
c_extension  0.010000   0.010000   0.020000 (  0.025475)

Concatenating 10 arrays of size 1000 (10000 times)
                 user     system      total        real
plus         0.690000   0.560000   1.250000 (  1.252319)
concat       0.180000   0.130000   0.310000 (  0.303365)
c_extension  0.120000   0.120000   0.240000 (  0.248589)

plus 从以下结果中排除

Concatenating 10 arrays of size 100000 (100 times)
                 user     system      total        real
concat       0.220000   0.340000   0.560000 (  0.568730)
c_extension  0.130000   0.150000   0.280000 (  0.281354)

Concatenating 100 arrays of size 10000 (100 times)
                 user     system      total        real
concat       0.210000   0.320000   0.530000 (  0.519030)
c_extension  0.160000   0.140000   0.300000 (  0.304751)

Concatenating 1000 arrays of size 1000 (100 times)
                 user     system      total        real
concat       0.240000   0.330000   0.570000 (  0.563511)
c_extension  0.150000   0.120000   0.270000 (  0.283546)

Concatenating 10000 arrays of size 100 (100 times)
                 user     system      total        real
concat       0.330000   0.310000   0.640000 (  0.643987)
c_extension  0.170000   0.120000   0.290000 (  0.286489)

Concatenating 100000 arrays of size 10 (100 times)
                 user     system      total        real
concat       1.300000   0.340000   1.640000 (  1.648687)
c_extension  0.310000   0.150000   0.460000 (  0.458214)

测试代码:

require 'benchmark'

values = [
  # small
  { count: 3,      size: 100,    n: 10000 },
  { count: 10,     size: 100,    n: 10000 },
  { count: 10,     size: 1000,   n: 10000 },
  # large
  { count: 10,      size: 100000, n: 100 },
  { count: 100,     size: 10000,  n: 100 },
  { count: 1000,    size: 1000,   n: 100 },
  { count: 10000,   size: 100,    n: 100 },
  { count: 100000,  size: 10,     n: 100 }
]

values.each_with_index do |h, i|
  count, size, n = h.values_at(:count, :size, :n)
  arrays = Array.new(count) { Array.new(size) }

  puts
  puts "Concatenating #{count} arrays of size #{size} (#{n} times)"
  Benchmark.bm(10) do |r|
    r.report('plus')        { n.times { arrays.reduce(:+) } } if i < 3
    r.report('concat')      { n.times { arrays.reduce([], :concat) } }
    r.report('c_extension') { n.times { Array.concat(*arrays) } }
  end
end

C扩展:(实际上是一个补丁,我把它添加到了Ruby的array.c)

VALUE
rb_ary_s_concat(int argc, VALUE *argv, VALUE klass)
{
  VALUE ary;
  long len = 0, i;
  for (i=0; i<argc; i++) {
    argv[i] = to_ary(argv[i]);
    len += RARRAY_LEN(argv[i]);
  }
  ary = rb_ary_new2(len);
  long beg = 0;
  for (i=0; i<argc; i++) {
    ary_memcpy(ary, beg, RARRAY_LEN(argv[i]), RARRAY_CONST_PTR(argv[i]));
    beg += RARRAY_LEN(argv[i]);
  }
  ARY_SET_LEN(ary, len);
  return ary;
}

您必须在Init_Arrayvia中注册此方法:

rb_define_singleton_method(rb_cArray, "concat", rb_ary_s_concat, -1);