From: Vicente Bosch Campos <vbosch@...>
Date: 2011-04-08T16:06:56+09:00
Subject: Re: Sum of arrays getting slower as size increments

Thanks Jesús!!

On Apr 8, 2011, at 9:00 AM, Jesús Gabriel y Galán wrote:

> 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.
>