I have been working with ranking algorithm, wich collects the smallest
numbers chronologically. but i couldn’t make it work.
Here is the code.
module Enumerable
def min_n(n, &block)
block = Proc.new { |x,y| x <=> y} if block == nil
stable = StortedArray.new(&block)
each do |x|
stable << x if stable.size < n or block.call(x, stable[-1]) == -1
stable.pop until stable.size <=n
end
return stable
end
end
m = [1,5,2,8,7,9,10,100,50]
m.min_n(4)
I would be more than glad to get your feedback/suggestions of how to
make it work.
so what does “not work” mean? I don’t know your StortedArray class (or
rather SortedArray?), but if it works like I think it works, then your
method should indeed output the four smallest elements:
[1, 2, 5, 7]
But what’s all this effort for? Why not simply use Ruby’s built-in
methods for that?
smallest = m.sort.first 4
This might not be particularly efficient, but your method isn’t either.
If sort complexity is O(nlog(n), i thought that sorting the complete
array was less smart than my solution which should be
O(mn) / m=number of minus item selected.
but it is not true:
nlog(n) with n=100_000 >> 1_115_000
m*n with n=100_000 and m=10 >> 1_000_000
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):
On Thu, Nov 29, 2012 at 4:42 PM, Regis d’Aubarede [email protected]
wrote:
def n_min(l,n) (1…n).map {a=l.min ; l=l-[a]; a } end
array.sort[0, n]
n_min array, n
You compar ruby implementation for n_min() with c implementation for
sort…
Is that forbidden? You are making use of C implementation as well.
With that argumentation of yours you would also need to reimplement
methods you use inside n_min in Ruby (notably l.min and l-[a]). Fact
remains that your algorithm will visit most of the elements of a 2*n
times. I find that inelegant but YMMV of course.
Is that forbidden? You are making use of C implementation as well.
With that argumentation of yours you would also need to reimplement
methods you use inside n_min in Ruby (notably l.min and l-[a]). Fact
remains that your algorithm will visit most of the elements of a 2*n
times. I find that inelegant but YMMV of course.
I agree with Robert, using #sort is probably the simplest approach and
reasonably fast in most situations. This is exactly what I would do.
But I also like playing around with algorithms So if you’re really
keen on both, performance and doing as much as possible in ruby, you
can try the following implementation of “min_n”, which uses a binary
heap. It has a running-time of O(n*log m) (n=array size, m=number of
small elements) and should by quite fast if m << n. Then it also seems
to be quite competetive with the sort approach.
====
def hdown(a, i)
x, n = a[i], a.size
while true do
l = 2*i + 1
r = l + 1
break if l >= n
nxt = r >= n || a[l] >= a[r] ? l : r
break if x >= a[nxt]
a[i], i = a[nxt], nxt
end
a[i] = x
end
def hbuild(a)
(a.size/2).downto(0) do |i| hdown(a, i) end
end
def min_n(a, n)
if a.size <= n then
return a.dup
else
h = a[0,n]
hbuild(h)
n.upto(a.size-1) do |i|
if h[0] > a[i] then
h[0] = a[i]
hdown(h, 0)
end
end
return h
end
end
I agree with Robert, using #sort is probably the simplest approach and
reasonably fast in most situations. This is exactly what I would do.
But I also like playing around with algorithms
I put a few more variants which traverse the original Enumerable just
once up at github to play around with:
Kind regards
robert
This forum is not affiliated to the Ruby language, Ruby on Rails framework, nor any Ruby applications discussed here.
So if you’re really