a day in the pit my view from inside

27Jul/115

Two variations on Ruby array#flatten

Implement Ruby's flatten method for an Array (without taking any peaks at the source!). Probably not the hardest thing you'll ever have to do, but there are many ways to do it... Jon and I each take a blind stab at it. Here's our effort:

Mike's variation

def mikes_flatten arr, level = nil
  result = []
  arr.each do |elem|
    recursive_flatten(result, elem,level,0)
  end
  result
end
 
def recursive_flatten(result, elem,level,current_level)
  if elem.is_a?(Array)
    elem.each do |el|
      if level.nil? || current_level < level
        recursive_flatten(result, el,level,current_level+1)
      else
        result << el
      end
    end
  else
    result << elem
  end
  result
end

Jon's variation

def flatten values, level=-1
  flat = []
  values.each do |value|
    if level != 0 && value.kind_of?(Array)
      flat.concat(flatten(value, level-1))
    else
      flat << value
    end
  end
  flat
end

Perf different can be seen by Jon's benchmark code (flatten.rb):

#!/usr/bin/ruby
require 'benchmark'
 
# Insert flatten methods here
 
def random_value
  if rand(3) < 1
    (rand(5)+1).times.map { |i| random_value }
  else
    rand(10000)
  end
end
 
VALUE = 100.times.map { |i| random_value}
ITERATIONS = 1000
 
Benchmark.bm do |b|
  puts "Iterations: #{ITERATIONS}"
  b.report("Mikes version") do
    ITERATIONS.times { |i| mikes_flatten(VALUE)}
  end
  b.report("Jons version") do
    ITERATIONS.times { |i| flatten(VALUE)}
  end
end

Jon's is pretty succinct. When I first went about writing things out I was going for the "get it to work." Either way, I don't see a huge performance difference... They toggle back and forth by about a half a second.

[13:57:11 miker@laughwhat-lm ~/Downloads] $ ruby flatten.rb
      user     system      total        real
Iterations: 10000
Mikes version  2.920000   0.010000   2.930000 (  2.933274)
Jons version  2.990000   0.000000   2.990000 (  3.017929)
 
[13:57:25 miker@laughwhat-lm ~/Downloads] $ ruby flatten.rb
      user     system      total        real
Iterations: 10000
Mikes version  3.010000   0.010000   3.020000 (  3.030987)
Jons version  2.980000   0.010000   2.990000 (  2.999335)
 
[13:57:34 miker@laughwhat-lm ~/Downloads] $ ruby flatten.rb
      user     system      total        real
Iterations: 100000
Mikes version 26.860000   0.050000  26.910000 ( 26.973855)
Jons version 24.050000   0.050000  24.100000 ( 24.126557)
 
[13:58:34 miker@laughwhat-lm ~/Downloads] $ ruby flatten.rb
      user     system      total        real
Iterations: 100000
Mikes version 24.120000   0.050000  24.170000 ( 24.201227)
Jons version 25.080000   0.050000  25.130000 ( 25.196811)

Write your own and submit as a comment. Let's see some other ways to do this :)

Filed under: Benchmark, Code, Ruby Leave a comment
Comments (5) Trackbacks (0)
  1. Colin Kelley
    August 2nd, 2011 - 06:49

    Here’s my nomination:

    def flatten(array, result = [])
    array.each do |el|
    case el
    when Array
    flatten el, result
    else
    result << el
    end
    end

    result
    end

    How does it do on your benchmark?

  2. Mike
    August 2nd, 2011 - 08:07

    Darn, wish there were syntax highlighting in the comments. Anyways, the flatten method takes a level. Our two methods different from Ruby’s version only in that we pass explicitly the array container. Add a level option, and I’ll benchmark and add to the post :)

  3. Colin Kelley
    August 3rd, 2011 - 06:04

    Ah, I didn’t realize that level was in the standard flatten contract.

    Here’s my version with that added:

    http://www.pastie.org/2312779

  4. Mike
    August 3rd, 2011 - 18:01

    Some basic benchmarks —

    [10:49:47 miker@laughwhat-lm ~/projects] $ ruby bencher.rb
    user system total real
    Iterations: 1000
    Mikes version 16.460000 0.030000 16.490000 ( 16.493502)
    Jons version 18.760000 0.040000 18.800000 ( 18.818719)
    Colins version 10.060000 0.010000 10.070000 ( 10.085247)
    Ruby’s version 2.990000 0.010000 3.000000 ( 2.991843)

    [10:50:59 miker@laughwhat-lm ~/projects] $ ruby bencher.rb
    user system total real
    Iterations: 5000
    Mikes version 7.000000 0.010000 7.010000 ( 7.017397)
    Jons version 6.410000 0.110000 6.520000 ( 6.527380)
    Colins version 4.190000 0.000000 4.190000 ( 4.195313)
    Ruby’s version 1.290000 0.000000 1.290000 ( 1.290924)

    Ruby, you win.

  5. Colin Kelley
    August 4th, 2011 - 04:54

    One thing that bothered me about my implementation (all of ours really) is that they aren’t OO. My version keeps passing a third argument to accumulate the result, while self isn’t used. Shouldn’t the result just be self? Well, I could have have extended Array with my recursive method, but I ruled that out because it’s just bad design to extend general classes with non-general needs. It’s never harmless since you’re causing namespace pollution and in duck typing that can screw you.

    Then it hit me. Check this one out! I think it performs best of all. (And no fair counting Ruby’s C implementation.)

    http://www.pastie.org/2318024


Leave a comment


 

No trackbacks yet.

» «

Ephekt/Mike Rose/Smasher5

Twitter: smasher5

Sections

Archives