From: Martin Pirker <crf@...>
Date: 2002-07-06T23:18:47+09:00
Subject: fast "set difference" on arrays


Hi...

I have a Ruby speed problem, maybe you have some suggestions:

given: text files with values, one per line, sorted, e.g.
10100
10234
10292
......

so:
arr1 = IO.readlines(file1)
arr2 = IO.readlines(file2)

arr1 consists of ~40000 lines/elements
arr2 size is ~10000

when I want to take the "set difference", arr3 = arr1-arr2, meaning "take
all elements from arr1 which dont appear in arr2" this takes forever - I
don't even know how long because I stopped early ;)

So the built-in operator is too slow - taking advantage of my knowledge
of the sorting I handcoded a "loop { compare arr1[0] with arr2[0], either
puts or remove }"
This gets it down to 5-10s, much better, but still too slow - 1s would be
a nice target

As I'm still quite novice in Ruby (always having Hal's book on my lap ;) ..)
how would you code a speedier solution?

(as for shell tools, I first tried the grep way, but it chokes on the size
with a "reg.exp. too large")

Martin