# Fast "set difference" on arrays

**URL:** <https://rubytalk.org/t/fast-set-difference-on-arrays/539>\
**Category:** ruby-talk\
**Created:** [6 July 2002 14:18 UTC](https://rubytalk.org/t/fast-set-difference-on-arrays/539 "2002-07-06T14:18:47Z")\
**Posts on this page:** 7\
**Page:** 1

<div class="post-metadata">

**Author:** ![Martin\_Pirker1](https://avatars.discourse-cdn.com/v4/letter/m/65b543/32.png) [@Martin\_Pirker1](https://rubytalk.org/u/Martin_Pirker1)\
**Post date:** [6 July 2002 14:18 UTC](https://rubytalk.org/t/fast-set-difference-on-arrays/539/1 "2002-07-06T14:18:47Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![Dave\_Thomas](https://avatars.discourse-cdn.com/v4/letter/d/439d5e/32.png) [@Dave\_Thomas](https://rubytalk.org/u/Dave_Thomas)\
**Post date:** [6 July 2002 14:43 UTC](https://rubytalk.org/t/fast-set-difference-on-arrays/539/2 "2002-07-06T14:43:34Z")

</div>

Martin Pirker [crf@sbox.tu-graz.ac.dfgdfhjhzjgfdfsddadshrhdrhdfdsasaff.at](mailto:crf@sbox.tu-graz.ac.dfgdfhjhzjgfdfsddadshrhdrhdfdsasaff.at) writes:

> 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 😉

The following runs in about .5s on my pokey old box:

s1 = {}  
File.foreach(ARGV[1]) {|line| s1[line] = 1}  
File.foreach(ARGV[0]) {|line| puts(line) unless s1[line]}

Note that it’s doing String comparisons, not integer ones, but if both  
of your files are generated the same way that won’t be a problem.

Cheers

Dave

---

<div class="post-metadata">

**Author:** ![Evan\_Martin](https://avatars.discourse-cdn.com/v4/letter/e/3be4f8/32.png) [@Evan\_Martin](https://rubytalk.org/u/Evan_Martin)\
**Post date:** [6 July 2002 17:11 UTC](https://rubytalk.org/t/fast-set-difference-on-arrays/539/3 "2002-07-06T17:11:27Z")

</div>

You could also do it without hashes (though that solution is clearly the  
simplest). This algorithm feels to me like the merge stage of a merge  
sort, sorta (if you’re not familiar with merge sort, google for it):

a1 = [1, 3, 4, 10, 13, 31, 53, 54, 55]  
a2 = [3, 10, 10, 11, 13, 54, 55]

i = 0  
a3 =   
a1.each { |a|  
i = i + 1 while a2[i] \< a

a3 \<\< a if a2[i] \> a  
}

a3.each {|a| puts a}

> **···**
>
> On Sat, Jul 06, 2002 at 11:18:47PM +0900, Martin Pirker wrote:
> 
> > 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?
> 
> –  
> Evan Martin  
> martine@cs.washington.edu  
> [http://neugierig.org](http://neugierig.org)

---

<div class="post-metadata">

**Author:** ![Ned\_Konz](https://avatars.discourse-cdn.com/v4/letter/n/ad7895/32.png) [@Ned\_Konz](https://rubytalk.org/u/Ned_Konz)\
**Post date:** [6 July 2002 17:23 UTC](https://rubytalk.org/t/fast-set-difference-on-arrays/539/4 "2002-07-06T17:23:32Z")

</div>

How fast does this go:

h2 = Hash.new(false)  
IO.readlines(ARGV[1]).each { |line| h2[line] = true }  
puts “h2 has #{h2.size} elements”

diff =   
IO.readlines(ARGV[0]).each { |line| diff \<\< line unless h2[line] }

puts “diff has #{diff.size} elements”

> **···**
>
> On Saturday 06 July 2002 07:18 am, Martin Pirker wrote:
> 
> > 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 😉
> 
> –  
> Ned Konz  
> [http://bike-nomad.com](http://bike-nomad.com)  
> GPG key ID: BEEA7EFE

---

<div class="post-metadata">

**Author:** ![Joseph\_McDonald](https://avatars.discourse-cdn.com/v4/letter/j/34f0e0/32.png) [@Joseph\_McDonald](https://rubytalk.org/u/Joseph_McDonald)\
**Post date:** [6 July 2002 15:02 UTC](https://rubytalk.org/t/fast-set-difference-on-arrays/539/5 "2002-07-06T15:02:58Z")

</div>

> > 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 😉

> The following runs in about .5s on my pokey old box:

> s1 = {}  
> File.foreach(ARGV[1]) {|line| s1[line] = 1}  
> File.foreach(ARGV[0]) {|line| puts(line) unless s1[line]}

> Note that it’s doing String comparisons, not integer ones, but if both  
> of your files are generated the same way that won’t be a problem.

Do you think Array#- should do the hash trick internally instead of a  
complete scan x\*y times ? I do.

thanks,  
-joe

---

<div class="post-metadata">

**Author:** ![ts1](https://avatars.discourse-cdn.com/v4/letter/t/a8b319/32.png) [@ts1](https://rubytalk.org/u/ts1)\
**Post date:** [6 July 2002 15:30 UTC](https://rubytalk.org/t/fast-set-difference-on-arrays/539/6 "2002-07-06T15:30:53Z")

</div>

> Do you think Array#- should do the hash trick internally instead of a  
> complete scan x\*y times ? I do.

It can't : the "hash trick" use #eql? and #hash  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Array#- use #==

pigeon% ruby -e 'a={{1=\>1}=\>1}; b = {1=\>1}; p a[b]; p (a.keys - [b])'  
nil  
  
pigeon%

Unrelated but

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

For shell tools

&nbsp;&nbsp;comm -23 file1 file2

Guy Decoux

---

<div class="post-metadata">

**Author:** ![Nobuyoshi\_Nakada](https://avatars.discourse-cdn.com/v4/letter/n/edb3f5/32.png) [@Nobuyoshi\_Nakada](https://rubytalk.org/u/Nobuyoshi_Nakada)\
**Post date:** [6 July 2002 16:15 UTC](https://rubytalk.org/t/fast-set-difference-on-arrays/539/7 "2002-07-06T16:15:28Z")

</div>

Hi,

> **···**
>
> At Sun, 7 Jul 2002 00:02:58 +0900, Joseph McDonald wrote:
> 
> > Do you think Array#- should do the hash trick internally instead of a  
> > complete scan x\*y times ? I do.
> 
> Already Array#& and #| use the trick, so it would be nice.
> 
> –  
> Nobu Nakada