Re: array comparison

On 31.10.2008 11:21, Sarcar, Shourya C (GE Healthcare) wrote:
>> -----Original Message-----
>> From: Robert Klemme [mailto:[e-mail]] 
>> Sent: Friday, October 31, 2008 12:04 AM
>> To: ruby-talk ML
>> Subject: Re: array comparison
>>
>> The comparison is a bit unfair since you include the build 
>> time for the structure in case of Hash but not for the Array. 
>>  You should at least also compare just the intersection time. 
>>  And while you're at it you can also add Set to the mix. :-)
> 
> 
> Interesting discussion.
> 
> I wrote a small program to compare Array intersection to Set
> intersection.
> I noticed that for smaller sets (~10 ** 3), Array is much faster that
> Set, sometimes upto 5x.
> As the set size grows, they seem to converge (~10 ** 7, 100 million)
> 
> # Program to compare timings for intersections
> require 'set'
> 
> n = 10000
> while (n <= 10 ** 7) do 
> 	c = Array.new(n) {rand n}.uniq
> 	d = Array.new(n) {rand n}.uniq
> 
> 	# Native array intersection
> 	t0 = Time.now
> 	cd = c & d
> 	t1 = Time.now
> 	printf("Array | n = %d : %d intersects found in %f
> seconds\n",n,cd.size,t1-t0)
> 	
> 	# Convert array to Set objects and perform intersection
> 	c = c.to_set
> 	d = d.to_set
> 	t2 = Time.now
> 	cd = c & d
> 	t3 = Time.now
> 	printf("Set   | n = %d : %d intersects found in %f
> seconds\n",n,cd.size,t3-t2)
> 	printf("Ratio of Set/Array intersect time =
> %.2f\n",(t3-t2)/(t1-t0))
> 
> 	n = 2 * n
> end

Some things are noteworthy about your program:

  - It has a large intersection, i.e. roughly 50% on average.  This may 
be different for other scenarios.

  - You use Fixnums which compare pretty fast, you can expect to reach 
break even earlier when using other types.

I have taken the liberty to extend your test program a bit changing 
those two parameters mentioned above and you can see significant 
differences. :-)

Kind regards

	robert