From: Phrogz <phrogz@...>
Date: 2007-12-12T23:40:59+09:00
Subject: Re: Find the first non-nil element in an array

On Dec 12, 7:11 am, Brian Adkins <lojicdot...@gmail.com> wrote:
> On Dec 11, 5:06 pm, Clifford Heath <n...@spam.please.net> wrote:
>
> > I can't work out why you want to build a new (compacted) array in
> > order to discard it and use the first element. Detect is much more
> > suitable:
>
> Depending on the nature of the array (in particular, the number of
> initial nils), speed might be a reason to use compact instead of
> detect. Although it seems counterintuitive, creating a new compacted
> array just to grab the first element and throw it away can be faster
> than using detect.
>
> With the compact approach, there is one call to a method that is
> compiled C code. With the detect approach, there are (possibly)
> multiple iterations of interpreted Ruby.
>
> I'd say compact is perfectly suitable for this purpose - it's more
> concise, usually faster and logical.
>
> require 'benchmark'
> include Benchmark
>
> ITER = 10000
>
> def bench size, num_nils
>   xs = Array.new(size, 'a')
>   xs.fill(nil, 0, num_nils)
>
>   bm(5) do |bench|
>     bench.report('compact') do
>       ITER.times { xs.compact[0] }
>     end
>     bench.report('detect') do
>       ITER.times { xs.detect {|e| !e.nil? } }
>     end
>   end
> end
>
> [10,100,1000].each do |size|
>   [0,1,9].each do |nils|
>     bench(size, nils)
>   end
> end

For the curious, here are the results of Brian's test on my computer
(with a small change to simplify the results and make things run long
enough to be noticeable):

Rehearsal --------------------------------------------------
compact 10 0     0.320000   0.000000   0.320000 (  0.349166)
detect  10 0     0.610000   0.010000   0.620000 (  0.604446)
compact 10 1     0.340000   0.000000   0.340000 (  0.342348)
detect  10 1     0.820000   0.000000   0.820000 (  0.827957)
compact 10 9     0.340000   0.000000   0.340000 (  0.346089)
detect  10 9     2.540000   0.020000   2.560000 (  2.554578)
compact 100 0    0.410000   0.000000   0.410000 (  0.413763)
detect  100 0    0.590000   0.010000   0.600000 (  0.605422)
compact 100 1    0.440000   0.000000   0.440000 (  0.436081)
detect  100 1    0.820000   0.000000   0.820000 (  0.828730)
compact 100 9    0.450000   0.010000   0.460000 (  0.449880)
detect  100 9    2.540000   0.010000   2.550000 (  2.559824)
compact 1000 0   2.100000   0.020000   2.120000 (  2.118428)
detect  1000 0   0.600000   0.000000   0.600000 (  0.603317)
compact 1000 1   1.900000   0.010000   1.910000 (  1.966759)
detect  1000 1   0.850000   0.010000   0.860000 (  1.014724)
compact 1000 9   2.070000   0.020000   2.090000 (  2.431632)
detect  1000 9   2.600000   0.020000   2.620000 (  3.047283)
---------------------------------------- total: 20.480000sec

                     user     system      total        real
compact 10 0     0.320000   0.000000   0.320000 (  0.323211)
detect  10 0     0.590000   0.000000   0.590000 (  0.594916)
compact 10 1     0.350000   0.000000   0.350000 (  0.343759)
detect  10 1     0.820000   0.010000   0.830000 (  0.822784)
compact 10 9     0.340000   0.000000   0.340000 (  0.344985)
detect  10 9     2.540000   0.010000   2.550000 (  2.552693)
compact 100 0    0.400000   0.010000   0.410000 (  0.409807)
detect  100 0    0.590000   0.000000   0.590000 (  0.596081)
compact 100 1    0.430000   0.000000   0.430000 (  0.437479)
detect  100 1    0.820000   0.010000   0.830000 (  0.826087)
compact 100 9    0.450000   0.000000   0.450000 (  0.451402)
detect  100 9    2.530000   0.020000   2.550000 (  2.550478)
compact 1000 0   2.110000   0.010000   2.120000 (  2.142801)
detect  1000 0   0.600000   0.010000   0.610000 (  0.597523)
compact 1000 1   1.890000   0.010000   1.900000 (  1.903376)
detect  1000 1   0.820000   0.000000   0.820000 (  0.831492)
compact 1000 9   1.950000   0.010000   1.960000 (  1.980168)
detect  1000 9   2.540000   0.000000   2.540000 (  2.537653)


Here's the actual test code I ran:
require 'benchmark'
ITER = 500_000

def bench size, num_nils, bm
  xs = Array.new(size, 'a')
  xs.fill(nil, 0, num_nils)
  bm.report("compact #{size} #{num_nils}") do
    ITER.times { xs.compact[0] }
  end
  bm.report("detect  #{size} #{num_nils}") do
    ITER.times { xs.detect {|e| !e.nil? } }
  end
end

Benchmark.bmbm do |bm|
  [10,100,1000].each do |size|
    [0,1,9].each do |nils|
      bench(size, nils, bm)
    end
  end
end