Re: Getting the smallest Items of an Array

On 2012-11-29, Robert Klemme <[e-mail]> wrote:
> On Thu, Nov 29, 2012 at 4:42 PM, Regis d'Aubarede <[e-mail]> 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.

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
====

The following tests are from jruby-1.7.0

1/32768 items sort               2.700000   0.020000   2.720000 (  2.685000)
1/32768 items min_n              1.400000   0.050000   1.450000 (  1.246000)
1/131072 items sort             17.070000   0.010000  17.080000 ( 17.054000)
1/131072 items min_n             4.510000   0.010000   4.520000 (  4.418000)
10/32768 items sort              2.660000   0.000000   2.660000 (  2.655000)
10/32768 items min_n             1.170000   0.010000   1.180000 (  1.142000)
10/131072 items sort            17.060000   0.000000  17.060000 ( 17.036000)
10/131072 items min_n            4.540000   0.010000   4.550000 (  4.437000)
100/32768 items sort             2.660000   0.000000   2.660000 (  2.656000)
100/32768 items min_n            1.440000   0.010000   1.450000 (  1.405000)
100/131072 items sort           17.070000   0.000000  17.070000 ( 17.039000)
100/131072 items min_n           4.900000   0.010000   4.910000 (  4.782000)
1000/32768 items sort            2.650000   0.000000   2.650000 (  2.653000)
1000/32768 items min_n           3.850000   0.000000   3.850000 (  3.794000)
1000/131072 items sort          17.080000   0.010000  17.090000 ( 17.042000)
1000/131072 items min_n          8.550000   0.010000   8.560000 (  8.320000)


and with 1.9.3

1/32768 items sort               3.420000   0.030000   3.450000 (  3.437513)
1/32768 items min_n              2.540000   0.000000   2.540000 (  2.544122)
1/131072 items sort             15.840000   0.160000  16.000000 ( 16.007184)
1/131072 items min_n            10.050000   0.000000  10.050000 ( 10.037374)
10/32768 items sort              3.420000   0.000000   3.420000 (  3.422531)
10/32768 items min_n             2.620000   0.000000   2.620000 (  2.616946)
10/131072 items sort            15.910000   0.000000  15.910000 ( 15.913246)
10/131072 items min_n           10.250000   0.000000  10.250000 ( 10.246652)
100/32768 items sort             3.410000   0.010000   3.420000 (  3.413907)
100/32768 items min_n            3.500000   0.000000   3.500000 (  3.502954)
100/131072 items sort           15.910000   0.010000  15.920000 ( 15.923128)
100/131072 items min_n          11.340000   0.010000  11.350000 ( 11.353193)
1000/32768 items sort            3.420000   0.000000   3.420000 (  3.417772)
1000/32768 items min_n          11.060000   0.000000  11.060000 ( 11.074263)
1000/131072 items sort          15.880000   0.000000  15.880000 ( 15.882260)
1000/131072 items min_n         22.170000   0.020000  22.190000 ( 22.197999)



Best regards,
Frank