From: Voroztsov Artem <artem.voroztsov@...>
Date: 2007-12-03T11:12:41+09:00
Subject: Array#flatten works quadratic time on length of resulting array. It could be linear

I encountered problem with Array#flatten slowness (it can be much
faster if no argument is given) while solving current QUIZ (see
ruby-talk mail list).

Sorry if the issue is already solved in HEAD revision. I have not checked it.
I just searched though bugs and did not find anything related to
'flatten' slowness.

My ruby version is
 ruby 1.8.6 (2007-03-13 patchlevel 0) [i386-mswin32]

The code to reveal the problem:

 #!/usr/bin/ruby

 N = 10000

 inputs = []
 inputs << '0 ' + (1..N-1).to_a.join(' - ') + ' -'
 inputs << (1..N).to_a.join(' ') + (" +" * (N-1))

 class Array
  def flatten2
    res = []
    x = self.reverse
    while !x.empty?
      a = x.pop
      if a.is_a?(Array)
        x.push(*a)
      else
        res << a
      end
    end
    res.reverse
  end
 end

 require 'benchmark'

 inputs.each do |input|
  stack = []
  input.strip.split.each do |token|
    # puts "TOKEN '#{token.inspect}'"
    case token
    when '*', '+', '/', '-'
      stack << [stack.pop, token, stack.pop].reverse!
    else
      stack << token
    end
  end

#####################

>ruby test_flatten.rb
      user     system      total        real
original flatten  5.125000   0.000000   5.125000 (  5.141000)
self-made flatten  0.032000   0.000000   0.032000 (  0.031000)
true
      user     system      total        real
original flatten  5.063000   0.000000   5.063000 (  5.079000)
self-made flatten  0.031000   0.000000   0.031000 (  0.031000)
true

######################
For N = 20000 we will get

>ruby test_flatten.rb
      user     system      total        real
original flatten 20.453000   0.000000  20.453000 ( 20.500000)
self-made flatten  0.062000   0.000000   0.062000 (  0.063000)
true
      user     system      total        real
original flatten 20.187000   0.000000  20.187000 ( 20.219000)
self-made flatten  0.063000   0.000000   0.063000 (  0.062000)
true

So, 'flatten' time  grows  quadratically while 'flatten2' time -- linearly.


See my message in QUIZ thread  http://www.ruby-forum.com/topic/133483#595902

Best regards,
Artem