-----Original Message-----

From: Robert K. [mailto:[email protected]]

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