From: Voroztsov Artem <artem.voroztsov@...>
Date: 2007-12-03T10:33:44+09:00
Subject: Re: [QUIZ] Postfix to Infix (#148)

2007/12/3, Voroztsov Artem <artem.voroztsov@gmail.com>:

> 2. We discovered problem with Array#flatten. Is it a known issue?
>     (I use ruby 1.8.6 (2007-03-13 patchlevel 0) [i386-mswin32])
>
> For  N = 10000, 20000 and  input =  '0 ' + (1..N-1).to_a.join(' - ') + ' -'
>
>   require 'benchmark'
>   puts Benchmark.measure {
>     stack.flatten
>   }
> return the following results:
>
> N    time
> 5000  1.265000
> 10000  5.141000
> 20000  20.484000
>
> So, it's quadratic.
> While final solution works less than 1 second (0.079 seconds).
> What's the problem with flatten?
>
>


So, here is the code just about 'flatten', not the QUIZ issue.
I write self-made 'flatten' and it works much faster for the
given case and many other cases we get in the quiz problem.

I use ruby 1.8.6 (2007-03-13 patchlevel 0) [i386-mswin32]

Can anybody check it for ruby 1.9.1?

#!/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

  res1 = res2 = nil

  Benchmark.bm {|b|
    b.report('original flatten') {
      res1 = stack.flatten
    }
    b.report('self-made flatten') {
      res2 = stack.flatten2
    }
  }
  puts res1 == res2
end


I have the following output:

>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