> -----Original Message-----
> From: Robert Klemme [mailto:shortcutter / googlemail.com]=20
> Sent: Friday, October 31, 2008 12:04 AM
> To: ruby-talk ML
> Subject: Re: array comparison
>=20
> The comparison is a bit unfair since you include the build=20
> time for the structure in case of Hash but not for the Array.=20
>  You should at least also compare just the intersection time.=20
>  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 =3D 10000
while (n <=3D 10 ** 7) do=20
	c =3D Array.new(n) {rand n}.uniq
	d =3D Array.new(n) {rand n}.uniq

	# Native array intersection
	t0 =3D Time.now
	cd =3D c & d
	t1 =3D Time.now
	printf("Array | n =3D %d : %d intersects found in %f
seconds\n",n,cd.size,t1-t0)
=09
	# Convert array to Set objects and perform intersection
	c =3D c.to_set
	d =3D d.to_set
	t2 =3D Time.now
	cd =3D c & d
	t3 =3D Time.now
	printf("Set   | n =3D %d : %d intersects found in %f
seconds\n",n,cd.size,t3-t2)
	printf("Ratio of Set/Array intersect time =3D
%.2f\n",(t3-t2)/(t1-t0))

	n =3D 2 * n
end


=3D=3D OUTPUT =3D=3D [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 =3D 10000 : 3980 intersects found in 0.000000 seconds
Set   | n =3D 10000 : 3980 intersects found in 0.016000 seconds
Ratio of Set/Array intersect time =3D Inf
Array | n =3D 20000 : 7956 intersects found in 0.000000 seconds
Set   | n =3D 20000 : 7956 intersects found in 0.032000 seconds
Ratio of Set/Array intersect time =3D Inf
Array | n =3D 40000 : 15940 intersects found in 0.016000 seconds
Set   | n =3D 40000 : 15940 intersects found in 0.078000 seconds
Ratio of Set/Array intersect time =3D 4.88
Array | n =3D 80000 : 31835 intersects found in 0.047000 seconds
Set   | n =3D 80000 : 31835 intersects found in 0.125000 seconds
Ratio of Set/Array intersect time =3D 2.66
Array | n =3D 160000 : 63959 intersects found in 0.125000 seconds
Set   | n =3D 160000 : 63959 intersects found in 0.281000 seconds
Ratio of Set/Array intersect time =3D 2.25
Array | n =3D 320000 : 128062 intersects found in 0.391000 seconds
Set   | n =3D 320000 : 128062 intersects found in 0.562000 seconds
Ratio of Set/Array intersect time =3D 1.44
Array | n =3D 640000 : 255466 intersects found in 0.672000 seconds
Set   | n =3D 640000 : 255466 intersects found in 1.156000 seconds
Ratio of Set/Array intersect time =3D 1.72
Array | n =3D 1280000 : 511590 intersects found in 1.905000 seconds
Set   | n =3D 1280000 : 511590 intersects found in 2.640000 seconds
Ratio of Set/Array intersect time =3D 1.39
Array | n =3D 2560000 : 1023031 intersects found in 4.124000 seconds
Set   | n =3D 2560000 : 1023031 intersects found in 5.296000 seconds
Ratio of Set/Array intersect time =3D 1.28
Array | n =3D 5120000 : 2047355 intersects found in 8.857000 seconds
Set   | n =3D 5120000 : 2047355 intersects found in 9.589000 seconds
Ratio of Set/Array intersect time =3D 1.08

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