On Thu, Nov 29, 2012 at 12:02 PM, Regis d'Aubarede <[email protected]> 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/
-- You received this message because you are subscribed to the Google Groups
ruby-talk-google group. To post to this group, send email to
[email protected]. To unsubscribe from this group, send email
to [email protected]. For more options, visit this
group at https://groups.google.com/d/forum/ruby-talk-google?hl=en
