> -----Original Message-----
> From: Robert Klemme [mailto:shortcutter / googlemail.com] 
> 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


== OUTPUT == [Dell Latitude 620 , Win XP SP2, 2 GB RAM, Intel Core2 CPU
@ 1.66 GHz, normal loading]

D:\Shourya\DEV\RUBY\MISC>ruby intersect.rb
Array | n = 10000 : 3980 intersects found in 0.000000 seconds
Set   | n = 10000 : 3980 intersects found in 0.016000 seconds
Ratio of Set/Array intersect time = Inf
Array | n = 20000 : 7956 intersects found in 0.000000 seconds
Set   | n = 20000 : 7956 intersects found in 0.032000 seconds
Ratio of Set/Array intersect time = Inf
Array | n = 40000 : 15940 intersects found in 0.016000 seconds
Set   | n = 40000 : 15940 intersects found in 0.078000 seconds
Ratio of Set/Array intersect time = 4.88
Array | n = 80000 : 31835 intersects found in 0.047000 seconds
Set   | n = 80000 : 31835 intersects found in 0.125000 seconds
Ratio of Set/Array intersect time = 2.66
Array | n = 160000 : 63959 intersects found in 0.125000 seconds
Set   | n = 160000 : 63959 intersects found in 0.281000 seconds
Ratio of Set/Array intersect time = 2.25
Array | n = 320000 : 128062 intersects found in 0.391000 seconds
Set   | n = 320000 : 128062 intersects found in 0.562000 seconds
Ratio of Set/Array intersect time = 1.44
Array | n = 640000 : 255466 intersects found in 0.672000 seconds
Set   | n = 640000 : 255466 intersects found in 1.156000 seconds
Ratio of Set/Array intersect time = 1.72
Array | n = 1280000 : 511590 intersects found in 1.905000 seconds
Set   | n = 1280000 : 511590 intersects found in 2.640000 seconds
Ratio of Set/Array intersect time = 1.39
Array | n = 2560000 : 1023031 intersects found in 4.124000 seconds
Set   | n = 2560000 : 1023031 intersects found in 5.296000 seconds
Ratio of Set/Array intersect time = 1.28
Array | n = 5120000 : 2047355 intersects found in 8.857000 seconds
Set   | n = 5120000 : 2047355 intersects found in 9.589000 seconds
Ratio of Set/Array intersect time = 1.08

--
Shourya
http://www.shouryalive.com/blog