From: Vicente Bosch Campos <vbosch@...>
Date: 2011-04-08T15:48:47+09:00
Subject: Sum of arrays getting slower as size increments

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. 

My ruby version:

MacBosch:~ vbosch$ ruby -v
ruby 1.9.2p180 (2011-02-18 revision 30909) [x86_64-darwin10.6.0]

Am I making a wrong assumption ? Is there a better performing way to do this ? 


I have coded following example to illustrate the point:

#! /usr/bin/env ruby

require 'gnuplot'
require 'benchmark'

b = Array.new  
x = Array.new
y = Array.new
  
1000.times do  
  
time=Benchmark.realtime{b+=Array.new(10000,1)}

puts "Length is #{b.length} last insertion took #{time}"

x.push(b.length)
y.push(time)

end

Gnuplot.open do |gp|
  Gnuplot::Plot.new( gp ) do |plot|

    plot.title  "Array insertion time vs Length"
    plot.ylabel "time"
    plot.xlabel "length"

    plot.data << Gnuplot::DataSet.new( [x, y] ) do |ds|
      ds.with = "lines"
      ds.notitle
    end
  end
end