Re: Getting the smallest Items of an Array

On Thu, Nov 29, 2012 at 12:02 PM, Regis d'Aubarede <[e-mail]> wrote:
>>> def n_min(l,n) (1..n).map {a=l.min ; l=l-[a]; a } end
> => nil
>>> n_min([1,2,-1,3,4],2)
> => [-1, 1]

Without having measured it that's quite an inefficient way to do it IMHO:
- you are creating a lot temporary arrays (two for each step)
- you are traversing most elements n times

I think, sorting once and then taking the first n elements is more efficient.

Turns out, measurements confirm this: this approach is faster only for
n=1 but then one would use Enumerable#min anyway.

require 'benchmark'

REP = 1_000

puts 'Generating data...'

data = [0, 1, 10, 17].map do |i|
    (1 << i).times.map { rand 1000000 }
  end

puts 'done'

def n_min(l,n) (1..n).map {a=l.min ; l=l-[a]; a } end

Benchmark.bm 30 do |x|
  [1, 10, 1000].each do |n|
    data.each do |array|
      x.report "#{n}/#{array.size} items sort" do
        REP.times do
          array.sort[0, n]
        end
      end

      x.report "#{n}/#{array.size} items n_min" do
        REP.times do
          n_min array, n
        end
      end
    end
  end
end

Test run (I interrupted it because it took too long):

Generating data...
done
                                     user     system      total        real
1/1 items sort                   0.000000   0.000000   0.000000 (  0.000500)
1/1 items n_min                  0.000000   0.000000   0.000000 (  0.003000)
1/2 items sort                   0.000000   0.000000   0.000000 (  0.000500)
1/2 items n_min                  0.000000   0.000000   0.000000 (  0.002001)
1/1024 items sort                0.109000   0.000000   0.109000 (  0.112014)
1/1024 items n_min               0.093000   0.000000   0.093000 (  0.094012)
1/131072 items sort             25.709000   0.141000  25.850000 ( 25.836281)
1/131072 items n_min            11.685000   0.280000  11.965000 ( 11.967520)
10/1 items sort                  0.000000   0.000000   0.000000 (  0.000500)
10/1 items n_min                 0.015000   0.000000   0.015000 (  0.014002)
10/2 items sort                  0.000000   0.000000   0.000000 (  0.000000)
10/2 items n_min                 0.016000   0.000000   0.016000 (  0.014002)
10/1024 items sort               0.094000   0.016000   0.110000 (  0.112514)
10/1024 items n_min              0.904000   0.000000   0.904000 (  0.929618)
10/131072 items sort            25.850000   0.109000  25.959000 ( 25.948795)
10/131072 items n_min          117.609000   2.137000 119.746000 (119.802713)
1000/1 items sort                0.000000   0.000000   0.000000 (  0.000500)
1000/1 items n_min               1.279000   0.000000   1.279000 (  1.279162)
1000/2 items sort                0.000000   0.000000   0.000000 (  0.001000)
1000/2 items n_min               1.279000   0.000000   1.279000 (  1.276662)
1000/1024 items sort             0.109000   0.000000   0.109000 (  0.112514)
1000/1024 items n_min           48.579000   0.000000  48.579000 ( 48.599671)
1000/131072 items sort          25.694000   0.188000  25.882000 ( 25.885787)
1000/131072 items n_min        x.rb:14:in `block in n_min': Interrupt
        from x.rb:14:in `each'
        from x.rb:14:in `map'
        from x.rb:14:in `n_min'
        from x.rb:27:in `block (5 levels) in <main>'
        from x.rb:26:in `times'
        from x.rb:26:in `block (4 levels) in <main>'
        from /usr/lib/ruby/1.9.1/benchmark.rb:280:in `measure'
        from /usr/lib/ruby/1.9.1/benchmark.rb:362:in `item'
        from x.rb:25:in `block (3 levels) in <main>'
        from x.rb:18:in `each'
        from x.rb:18:in `block (2 levels) in <main>'
        from x.rb:17:in `each'
        from x.rb:17:in `block in <main>'
        from /usr/lib/ruby/1.9.1/benchmark.rb:174:in `benchmark'
        from /usr/lib/ruby/1.9.1/benchmark.rb:205:in `bm'
        from x.rb:16:in `<main>'



Kind regards

robert

--
remember.guy do |as, often| as.you_can - without end
http://blog.rubybestpractices.com/