# Optimizing Hash deletions

**URL:** <https://www.ruby-forum.com/t/optimizing-hash-deletions/107781>\
**Category:** Ruby\
**Created:** [June 26, 2007, 4:37am UTC](https://www.ruby-forum.com/t/optimizing-hash-deletions/107781 "2007-06-26T04:37:11Z")\
**Posts on this page:** 7\
**Page:** 1

<div class="post-metadata">

**Author:** ![mschwab](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/m/59ef9b/32.png) [@mschwab](https://www.ruby-forum.com/u/mschwab)\
**Post date:** [June 26, 2007, 4:37am UTC](https://www.ruby-forum.com/t/optimizing-hash-deletions/107781/1 "2007-06-26T04:37:11Z")

</div>

I have a recursive file-compare program that I run on 2 directories that  
each contain about 10,000 files, 99% of which don’t change. I read all  
the  
filenames into hashes and then (first) delete all the matches, using  
this  
code:

def RemoveIdenticalDirs ( old\_fe\_list , new\_fe\_list )  
# this function is necessary because we have to do a  
case-insensitive  
match for directories, but not for files  
$stderr.puts “Detecting identical dirs…”  
old\_fe\_list.keys.each do | oldfile |  
new\_fe\_list.keys.each do | newfile | # can’t use .has\_key?  
because  
we have to do a case-insensitive match  
if old\_fe\_list[oldfile].is\_dir and  
new\_fe\_list[newfile].is\_dir  
and oldfile.downcase == newfile.downcase  
old\_fe\_list.delete ( oldfile )  
new\_fe\_list.delete ( newfile )  
break  
end  
end  
end  
end

def RemoveIdenticalFiles ( old\_fe\_list , new\_fe\_list , comparetype )  
$stderr.puts “Detecting identical files…”  
old\_fe\_list.keys.each do | file |  
if new\_fe\_list.has\_key? ( file )  
if !(old\_fe\_list[file].is\_dir) and  
!(new\_fe\_list[file].is\_dir)  
and FilesAreIdentical ( comparetype , old\_fe\_list[file] ,  
new\_fe\_list[file]  
)  
old\_fe\_list.delete ( file )  
new\_fe\_list.delete ( file )  
end  
end  
end  
end

Note that I’ve added an attribute to each hash called .is\_dir which just  
holds a Boolean value.

When I run the program (under WinXP using Ruby 185-21, if it matters),  
it  
takes about 5-10 seconds to execute the above 2 functions. But that’s  
not  
the worst part - it chews up memory big time. The machine I’m running it  
on  
has 768MB of RAM (with no swap file), and Windows gives me a warning  
that  
it’s out of memory as the above code runs. However, neither Windows nor  
the  
program crashes. I’m guessing that all the .delete’s are causing lots of  
memory usage and the garbage collector starts running.

So my question is - is there a less memory-intensive way of doing the  
above?  
Would setting elements to nil instead of deleting them make any  
difference?  
Or maybe copying entries to a new hash somehow?

Mike S.

---

<div class="post-metadata">

**Author:** ![mschwab](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/m/59ef9b/32.png) [@mschwab](https://www.ruby-forum.com/u/mschwab)\
**Post date:** [June 26, 2007, 5:21am UTC](https://www.ruby-forum.com/t/optimizing-hash-deletions/107781/2 "2007-06-26T05:21:13Z")

</div>

From: “Mike S.” [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid)

> old\_fe\_list.keys.each do | oldfile |  
> end  
> end  
> has 768MB of RAM (with no swap file), and Windows gives me a warning that  
> it’s out of memory as the above code runs. However, neither Windows nor the  
> program crashes. I’m guessing that all the .delete’s are causing lots of  
> memory usage and the garbage collector starts running.
> 
> So my question is - is there a less memory-intensive way of doing the above?  
> Would setting elements to nil instead of deleting them make any difference?  
> Or maybe copying entries to a new hash somehow?

You’ve got an O(n\*\*2) search in RemoveIdenticalDirs. How long  
does RemoveIdenticalDirs take to execute, as compared to  
RemoveIdenticalFiles?

Also, what does FilesAreIdentical() do ?

Regards,

Bill

---

<div class="post-metadata">

**Author:** ![mschwab](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/m/59ef9b/32.png) [@mschwab](https://www.ruby-forum.com/u/mschwab)\
**Post date:** [June 26, 2007, 4:18pm UTC](https://www.ruby-forum.com/t/optimizing-hash-deletions/107781/3 "2007-06-26T16:18:35Z")

</div>

If the files mostly never change, there may be faster ways.

If your code does the changing, then you can log whenever that gets  
done. This makes the list much shorter and no pruning is needed.

Alternatively, you could touch the files so that they all have the same  
timestamp. Then, you could just assemble the list of files that have a  
timestamp that is different and you would not need to do all that  
pruning.

---

<div class="post-metadata">

**Author:** ![mschwab](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/m/59ef9b/32.png) [@mschwab](https://www.ruby-forum.com/u/mschwab)\
**Post date:** [June 26, 2007, 3:39pm UTC](https://www.ruby-forum.com/t/optimizing-hash-deletions/107781/4 "2007-06-26T15:39:35Z")

</div>

Dear Mike,

why don’t you first create an Array of files that you want  
to delete, and do the deletion after that ?  
You can start the garbage collection by force also … maybe  
like this:

class String  
def compare\_dir(other\_dir)  
list1 = Dir.entries(self)  
list2=Dir.entries(other\_dir)  
in\_first\_but\_not\_in\_second\_dir=list1-list2  
# remove directories from the list  
in\_first\_but\_not\_in\_second\_dir.delete\_if{|x|  
FileTest::directory?(x)}  
return in\_first\_but\_not\_in\_second\_dir  
end  
end  
class Array  
def delete\_files  
self.each{|x|  
File.delete(x)  
GC.start  
}  
end  
end

I compared just the names of roughly 3500 files in two  
directories in a fraction of a second like this,  
but I haven’t tried to erase them…  
Best regards,

Axel

t=Time.now  
p “/home/axel”.compare\_dir(“/home/axel/ruby”).length  
p Time.now-t

-------- Original-Nachricht --------  
Datum: Tue, 26 Jun 2007 11:35:54 +0900  
Von: “Mike S.” [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid)  
An: removed\_email\_address@domain.invalid  
Betreff: optimizing Hash deletions

---

<div class="post-metadata">

**Author:** ![mschwab](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/m/59ef9b/32.png) [@mschwab](https://www.ruby-forum.com/u/mschwab)\
**Post date:** [June 26, 2007, 6:14pm UTC](https://www.ruby-forum.com/t/optimizing-hash-deletions/107781/5 "2007-06-26T18:14:56Z")

</div>

FilesAreIdentical() either compares the files based on size/date, or on  
contents (depending on the comparetype parameter). I’m currently running  
it  
with size/date (and it’s still slow and hogs memory).

Mike S.

---

<div class="post-metadata">

**Author:** ![mschwab](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/m/59ef9b/32.png) [@mschwab](https://www.ruby-forum.com/u/mschwab)\
**Post date:** [June 27, 2007, 1:14am UTC](https://www.ruby-forum.com/t/optimizing-hash-deletions/107781/6 "2007-06-27T01:14:49Z")

</div>

RemoveIdenticalDirs takes about 2-3 times as long to run as  
RemoveIdenticalFiles.

FilesAreIdentical compares 2 files based on size/date and returns  
true/false.

Mike S.

---

<div class="post-metadata">

**Author:** ![mschwab](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/m/59ef9b/32.png) [@mschwab](https://www.ruby-forum.com/u/mschwab)\
**Post date:** [June 27, 2007, 1:18am UTC](https://www.ruby-forum.com/t/optimizing-hash-deletions/107781/7 "2007-06-27T01:18:49Z")

</div>

The files are changed by other programs, so I can’t log those.

The speed really isn’t that much of an issue, since this program isn’t  
run  
too often. It’s mostly the memory usage (I estimate about 600MB peak  
memory  
used to compare 10,000 files).

Mike S.