From: "Jesús Gabriel y Galán" <jgabrielygalan@...>
Date: 2011-04-08T16:00:10+09:00
Subject: Re: Sum of arrays getting slower as size increments

On Fri, Apr 8, 2011 at 8:48 AM, Vicente Bosch Campos <vbosch@gmail.com> wrote:
> Hi,
>
> I am currently doing some code for a face detection algorithm. In order to generate the models I need to load 3 GB worth of data and do a K-means on it ( just to give some context of why I need all of the data loaded
> at the same time).
>
> At some point of the code I am retrieving a line of the file, turning the items into floats and dividing them in different set of arrays.
>
> Once a line is extracted and given the correct format I add that array to the one containing all lines
>
> all_data += line_array
>
> I have noticed that the + operation gets slower as the all_data array gets bigger but this should not be so at the end what the + operation is doing is inserting them at the back of the array and its always the same
> amount hence it should always take the same time.

The problem is that b += array is the same as b = b + array, which
creates a new array everytime, with the contents of both arrays. As b
gets bigger, creating this intermediate array gets more and more
expensive. You can use concat instead, so that you don't create
intermediate arrays, just modify b:

require 'benchmark'

TIMES = 500
Benchmark.bmbm do |x|
  x.report("+=") { b = [];  TIMES.times {b+=Array.new(10000,1)}}
  x.report("concat") { b = [];  TIMES.times {b.concat(Array.new(10000,1))}}
end



$ ruby bm_arrayconcat.rb
Rehearsal ------------------------------------------
+=      22.900000   3.500000  26.400000 ( 26.434147)
concat   1.010000   0.020000   1.030000 (  1.038697)
-------------------------------- total: 27.430000sec

             user     system      total        real
+=       5.090000   3.170000   8.260000 (  8.281054)
concat   0.520000   0.010000   0.530000 (  0.533721)

Hope this helps,

Jesus.