# Comparing two arrays, too slow

**URL:** <https://www.ruby-forum.com/t/comparing-two-arrays-too-slow/192831>\
**Category:** Ruby\
**Created:** [August 6, 2010, 5:51pm UTC](https://www.ruby-forum.com/t/comparing-two-arrays-too-slow/192831 "2010-08-06T17:51:34Z")\
**Posts on this page:** 6\
**Page:** 1

<div class="post-metadata">

**Author:** ![joe\_chesak](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/j/439d5e/32.png) [@joe\_chesak](https://www.ruby-forum.com/u/joe_chesak)\
**Post date:** [August 6, 2010, 5:51pm UTC](https://www.ruby-forum.com/t/comparing-two-arrays-too-slow/192831/1 "2010-08-06T17:51:34Z")

</div>

I don’t have access to the database, but everyday I get a csv dump of  
all  
live customer listings.  
There are around 15,000 live listings.  
A record contains 3 fields: id, name, description  
Everyday some new accounts are created while others are deleted.  
Everyday I want to compare yesterday’s dump with today’s dump and print  
the full record of each terminated record and each new record.  
I am achieving this with the script below.  
That last line makes the script run very slow.

Is there a more elegant way to compare two  
arrays|hashes|sets|FasterCSVtables while carrying a few fields along for  
the  
ride?

WORKING CODE:  
require ‘rubygems’  
require ‘fastercsv’

sundays\_dump = FasterCSV.read("./sunday.csv")  
mondays\_dump = FasterCSV.read("./monday.csv")

sundays\_ids = sundays\_dump.collect {|row| row[1]}  
mondays\_ids = mondays\_dump.collect {|row| row[1]}

newaccount\_ids = mondays\_ids - sundays\_ids  
terminated\_ids = sundays\_ids - mondays\_ids

sundays\_dump.each {|row| puts ‘delete,’+row[0]+’,’+row[1] if  
terminated\_ids.include? row[1]}  
mondays\_dump.each {|row| puts ‘create,’+row[0]+’,’+row[1] if  
newaccount\_ids.include? row[1]}

TEST DATA:  
sunday.csv  
id,name,otherstuff  
1,larry,bald  
2,curly,tall  
3,moe,meanie

monday.csv  
id,name,otherstuff  
1,larry,bald  
4,shemp,greasy

OUTPUT:  
delete,2,curly  
delete,3,moe  
create,4,shemp

---

<div class="post-metadata">

**Author:** ![joe\_chesak](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/j/439d5e/32.png) [@joe\_chesak](https://www.ruby-forum.com/u/joe_chesak)\
**Post date:** [August 6, 2010, 5:58pm UTC](https://www.ruby-forum.com/t/comparing-two-arrays-too-slow/192831/2 "2010-08-06T17:58:01Z")

</div>

On Sat, 7 Aug 2010, joe chesak wrote:

> Is there a more elegant way to compare two
> 
> sundays\_ids = sundays\_dump.collect {|row| row[1]}  
> mondays\_ids = mondays\_dump.collect {|row| row[1]}
> 
> newaccount\_ids = mondays\_ids - sundays\_ids  
> terminated\_ids = sundays\_ids - mondays\_ids
> 
> sundays\_dump.each {|row| puts ‘delete,’+row[0]+’,’+row[1] if  
> terminated\_ids.include? row[1]}  
> mondays\_dump.each {|row| puts ‘create,’+row[0]+’,’+row[1] if  
> newaccount\_ids.include? row[1]}

Rather than go through both sets of data, I’d do something like this:

terminated\_ids.each do |row|  
puts “delete,#{sundays\_dump[row][0]},#{sundays\_dump[row][1]}”  
end

Same thing for the new account (substituting monday, of course)

This way you’re only outputting the changed records.

Matt

---

<div class="post-metadata">

**Author:** ![joe\_chesak](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/j/439d5e/32.png) [@joe\_chesak](https://www.ruby-forum.com/u/joe_chesak)\
**Post date:** [August 6, 2010, 7:27pm UTC](https://www.ruby-forum.com/t/comparing-two-arrays-too-slow/192831/3 "2010-08-06T19:27:36Z")

</div>

On 8/6/10, joe chesak [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) wrote:

> Is there a more elegant way to compare two
> 
> 1,larry,bald  
> 4,shemp,greasy
> 
> OUTPUT:  
> delete,2,curly  
> delete,3,moe  
> create,4,shemp

Here’s an idea… although, Matthew’s suggestion is really the better  
way to go (tho I think his code won’t quite work… you’ll have to  
save away array indexes somewhere to make that approach effective).

Anyway, it should be much faster if you use Sets instead of arrays for  
terminated\_ids and newaccount\_ids. Like this:

require ‘rubygems’  
require ‘fastercsv’  
require ‘set’

sundays\_dump = FasterCSV.read(“./sunday.csv”)  
mondays\_dump = FasterCSV.read(“./monday.csv”)

sundays\_ids = sundays\_dump.collect {|row| row[1]}  
mondays\_ids = mondays\_dump.collect {|row| row[1]}

newaccount\_ids = Set[\*mondays\_ids - sundays\_ids]  
terminated\_ids = Set[\*sundays\_ids - mondays\_ids]

sundays\_dump.each {|row| puts ‘delete,’+row[0]+‘,’+row[1] if  
terminated\_ids.include? row[1]}  
mondays\_dump.each {|row| puts ‘create,’+row[0]+‘,’+row[1] if  
newaccount\_ids.include? row[1]}

Turning sundays\_ids and mondays\_ids into Sets might also make it a tad  
bit faster yet, but I think that the above code has achieved the lions  
share of potential speedups.

---

<div class="post-metadata">

**Author:** ![joe\_chesak](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/j/439d5e/32.png) [@joe\_chesak](https://www.ruby-forum.com/u/joe_chesak)\
**Post date:** [August 6, 2010, 11:16pm UTC](https://www.ruby-forum.com/t/comparing-two-arrays-too-slow/192831/4 "2010-08-06T23:16:43Z")

</div>

Another option: sort them by id, then walk through them together. If the  
current id on both list A and list B is the same, then skip forward on  
both. If the current id on list A is less than the current id on list B,  
then it exists only in B (so report this, and skip forward on A). And  
vice versa.

The advantage of this is that it works with huge files - you can read  
them one line at a time instead of reading them all into RAM. And there  
are tools which can do an external sort efficiently, if they’re not  
already sorted that way.

To avoid coding this, just use the unix shell command ‘join’ to do the  
work for you (which you can invoke from IO.popen if you like). Just  
beware that it’s very fussy about having the files correctly sorted  
first.

$ join -t, -j1 -v1 sunday.csv monday.csv  
2,curly,tall  
3,moe,meanie  
$ join -t, -j1 -v2 sunday.csv monday.csv  
4,shemp,greasy

---

<div class="post-metadata">

**Author:** ![joe\_chesak](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/j/439d5e/32.png) [@joe\_chesak](https://www.ruby-forum.com/u/joe_chesak)\
**Post date:** [August 9, 2010, 11:19am UTC](https://www.ruby-forum.com/t/comparing-two-arrays-too-slow/192831/5 "2010-08-09T11:19:05Z")

</div>

Guys! Thanks for the great responses, and clever perspectives on this  
problem. I have tried out all of them–got 3 of 4 to work on my real  
dataset.

Caleb: I actually had tried to apply Set to this problem and failed  
because  
I thought I should be able to point it at one column of a multi-column  
csv  
file…thinking of a .csv file almost as a full-fledged database table.  
Your minor tweak on my code shows just how easy it is to choose between  
Array vs. Set.

Brian: That’s a raw and fast solution. I will keep this in mind if my  
datasets get too large.

Kirk: Thanks for coding that all the way through. Great idea to create  
an  
index file and a data file in one sweep.

Joe Chesak

---

<div class="post-metadata">

**Author:** ![joe\_chesak](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/j/439d5e/32.png) [@joe\_chesak](https://www.ruby-forum.com/u/joe_chesak)\
**Post date:** [August 6, 2010, 7:21pm UTC](https://www.ruby-forum.com/t/comparing-two-arrays-too-slow/192831/6 "2010-08-06T19:21:09Z")

</div>

On Fri, Aug 6, 2010 at 9:51 AM, joe chesak [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) wrote:

> Is there a more elegant way to compare two
> 
> sundays\_ids = sundays\_dump.collect {|row| row[1]}  
> mondays\_ids = mondays\_dump.collect {|row| row[1]}
> 
> newaccount\_ids = mondays\_ids - sundays\_ids  
> terminated\_ids = sundays\_ids - mondays\_ids
> 
> sundays\_dump.each {|row| puts ‘delete,’+row[0]+‘,’+row[1] if  
> terminated\_ids.include? row[1]}  
> mondays\_dump.each {|row| puts ‘create,’+row[0]+‘,’+row[1] if  
> newaccount\_ids.include? row[1]}

The answer to, “it’s too slow”, is often, “don’t do that, then.”

If comparing arrays is too slow, don’t compare arrays. Instead, do  
something that’s fast. Looking up data in a Hash is fast. And since  
your data appears to be keyed by unique ids (though your code is  
written with variable names assuming it is looking at ids, but with  
array lookups that look at the names, which is confusing and might be  
a bug), it is easy to stuff that data into a hash for later lookup.

* * *

require ‘rubygems’  
require ‘fastercsv’

def extract\_data(dumpfile)  
dump = FasterCSV.read(dumpfile)  
ids = []  
data = {}  
dump.each do |row|  
ids \<\< row[0]  
data[row[0]] = row  
end

```
    [ids,data]

```

end

sundays\_dump = FasterCSV.read(“./sunday.csv”)  
mondays\_dump = FasterCSV.read(“./monday.csv”)

sunday\_ids, sunday\_data = extract\_data(“./sunday.csv”)  
monday\_ids, monday\_data = extract\_data(“./monday.csv”)

newaccount\_ids = monday\_ids - sunday\_ids  
terminated\_ids = sunday\_ids - monday\_ids

terminated\_ids.each do |id|  
row = sunday\_data[id]  
puts “delete,#{id},#{row[1]}”  
end

## newaccount\_ids.each do |id| row = monday\_data[id] puts “create,#{id},#{row[1]}” end

If this were my script, I’d further clean it up so that all of your  
logic is in a simple library. Then either create a generic executable  
that takes the file names as arguments, or write your scripts with  
hard coded file names, but that just calls into your library with  
those names. It’d be much cleaner unless you are absolutely sure that  
this code will never be more than a one-off hack.

Kirk H.