# Optimization question

**URL:** <https://rubytalk.org/t/optimization-question/4813>\
**Category:** ruby-talk\
**Created:** [19 February 2003 22:53 UTC](https://rubytalk.org/t/optimization-question/4813 "2003-02-19T22:53:14Z")\
**Posts on this page:** 20\
**Page:** 1

<div class="post-metadata">

**Author:** ![Travis](https://avatars.discourse-cdn.com/v4/letter/t/bbce88/32.png) [@Travis](https://rubytalk.org/u/Travis)\
**Post date:** [19 February 2003 22:53 UTC](https://rubytalk.org/t/optimization-question/4813/1 "2003-02-19T22:53:14Z")

</div>

Hello - A friend and I have been working on a Ruby implementation of a  
bayesian spam filter as described in Paul Graham’s, Plan For Spam.  
It’s fully functional, but I’ve been trying to squeeze more performance out  
of it as it’s quite slow ATM(15 minutes to run across 20 megs of email).  
By using profile and rbprof, I’ve determined that our tokenizer method is  
the main source of slowness. After some careful benchmarking, I’ve found this  
to be the problem.

# This is ran about a million times

h = Hash.new(0)  
data.scan(iptok).each do |tok|  
h[tok] += 1  
end

At first, I though I could do something like this:

# This is ran about a million times

h = Hash.new(0)  
data.scan(iptok).each do |tok|  
h[tok].succ  
end

But I realized that it doesn’t modify the final value; however, I did notice  
that it ran twice as fast than the former example. So, my question is, does the  
assignment in the first example really have that much overhead? If so, is there  
any way to do the first example using Inline::C or something similar?

Thanks in advance,  
Travis

---

<div class="post-metadata">

**Author:** ![Brian\_Candler](https://avatars.discourse-cdn.com/v4/letter/b/5f9b8f/32.png) [@Brian\_Candler](https://rubytalk.org/u/Brian_Candler)\
**Post date:** [19 February 2003 23:16 UTC](https://rubytalk.org/t/optimization-question/4813/2 "2003-02-19T23:16:51Z")

</div>

> # This is ran about a million times  
> h = Hash.new(0)  
> data.scan(iptok).each do |tok|  
> &nbsp;&nbsp;h[tok] += 1  
> end
> 
> At first, I though I could do something like this:
> 
> # This is ran about a million times  
> h = Hash.new(0)  
> data.scan(iptok).each do |tok|  
> &nbsp;&nbsp;h[tok].succ  
> end
> 
> But I realized that it doesn't modify the final value; however, I did notice  
> that it ran twice as fast than the former example.

Unfortunately it doesn't actually put anything into the hash either, so it's  
not a fair comparison. Have you tried:

&nbsp;&nbsp;&nbsp;h[tok] = 1

and see how that performs? Also

&nbsp;&nbsp;&nbsp;h[tok] = h[tok]

The first case will show time for inserting elements into hash, and the  
second case both retrieving and inserting elements (they will be inserted  
with value 'nil'). I suspect that the '+1' isn't actually going to be the  
main source of the problem.

> is there  
> any way to do the first example using Inline::C or something similar?

See 'extending Ruby' in the Pickaxe.

Regards,

Brian.

> **···**
>
> On Thu, Feb 20, 2003 at 07:53:14AM +0900, Travis Whitton wrote:

---

<div class="post-metadata">

**Author:** ![Daniel\_Carrera](https://avatars.discourse-cdn.com/v4/letter/d/c67d28/32.png) [@Daniel\_Carrera](https://rubytalk.org/u/Daniel_Carrera)\
**Post date:** [20 February 2003 00:32 UTC](https://rubytalk.org/t/optimization-question/4813/3 "2003-02-20T00:32:24Z")

</div>

1. Are the tokens strings?
2. Are you running Linux?

You might be able to use glib hashes to do this in C and then translate  
those to Ruby hashes. Just a thought. I’m putting together some code to  
see if I can figure it out.

> **···**
>
> On Thu, Feb 20, 2003 at 07:53:14AM +0900, Travis Whitton wrote:
> 
> > # This is ran about a million times
> > 
> > h = Hash.new(0)  
> > data.scan(iptok).each do |tok|  
> > h[tok] += 1  
> > end
> 
> –  
> Daniel Carrera  
> Graduate Teaching Assistant. Math Dept.  
> University of Maryland. (301) 405-5137

---

<div class="post-metadata">

**Author:** ![Daniel\_Carrera](https://avatars.discourse-cdn.com/v4/letter/d/c67d28/32.png) [@Daniel\_Carrera](https://rubytalk.org/u/Daniel_Carrera)\
**Post date:** [20 February 2003 01:59 UTC](https://rubytalk.org/t/optimization-question/4813/4 "2003-02-20T01:59:48Z")

</div>

I wrote a C version of your code which uses glib. I’m attaching it as  
Filter.c, as well as the extconf.rb. If you have glib, you can just do:

ruby extconf.rb  
make

This creates Filter.so. There seems to be a performance improvement, but  
it’s not as large as I might have hoped. Here are 3 tests:

\<----- t1.rb ---- Your original code -------------------\>  
5\_000.times do  
h = Hash.new(0)  
%w{a b c a g d e f a g h g i j e e k l m g d d a b c}.each do |tok|  
h[tok] += 1  
end  
end  
\<----- t2.rb ---- Replaced Array#each by a for loop. —\>  
5\_000.times do  
h = Hash.new(0)  
for tok in %w{a b c a g d e f a g h g i j e e k l m g d d a b c}  
h[tok] += 1  
end  
end  
\<----- t3.rb ---- Uses the C version. -------------------\>  
require “Filter”

5\_000.times do  
h = Filter.process %w{a b c a g d e f a g h g i j e e k l m g d d a b c}  
end  
\<-----------------------------\>  
And here are some results:

dcarrera $ time ruby t1.rb

real 0m3.205s  
user 0m3.130s  
sys 0m0.010s  
dcarrera $ time ruby t2.rb

real 0m3.006s  
user 0m2.860s  
sys 0m0.030s  
dcarrera $ time ruby t3.rb

real 0m1.677s  
user 0m1.490s  
sys 0m0.090s

Who knows, this might behave better with your data.

> **···**
>
> On Thu, Feb 20, 2003 at 07:53:14AM +0900, Travis Whitton wrote:
> 
> > Hello - A friend and I have been working on a Ruby implementation of a  
> > bayesian spam filter as described in Paul Graham’s, Plan For Spam.  
> > It’s fully functional, but I’ve been trying to squeeze more performance out  
> > of it as it’s quite slow ATM(15 minutes to run across 20 megs of email).  
> > By using profile and rbprof, I’ve determined that our tokenizer method is  
> > the main source of slowness. After some careful benchmarking, I’ve found this  
> > to be the problem.
> > 
> > # This is ran about a million times
> > 
> > h = Hash.new(0)  
> > data.scan(iptok).each do |tok|  
> > h[tok] += 1  
> > end
> > 
> > At first, I though I could do something like this:
> > 
> > # This is ran about a million times
> > 
> > h = Hash.new(0)  
> > data.scan(iptok).each do |tok|  
> > h[tok].succ  
> > end
> > 
> > But I realized that it doesn’t modify the final value; however, I did notice  
> > that it ran twice as fast than the former example. So, my question is, does the  
> > assignment in the first example really have that much overhead? If so, is there  
> > any way to do the first example using Inline::C or something similar?
> > 
> > Thanks in advance,  
> > Travis
> 
> –  
> Daniel Carrera  
> Graduate Teaching Assistant. Math Dept.  
> University of Maryland. (301) 405-5137

---

<div class="post-metadata">

**Author:** ![Bulat\_Ziganshin](https://avatars.discourse-cdn.com/v4/letter/b/ba8739/32.png) [@Bulat\_Ziganshin](https://rubytalk.org/u/Bulat_Ziganshin)\
**Post date:** [20 February 2003 05:58 UTC](https://rubytalk.org/t/optimization-question/4813/5 "2003-02-20T05:58:08Z")

</div>

Hello Travis,

Thursday, February 20, 2003, 1:53:14 AM, you wrote:

> # This is ran about a million times
> 
> h = Hash.new(0)  
> data.scan(iptok).each do |tok|  
> h[tok] += 1  
> end

are you heard about “sort|uniq” idiom? you can use  
such code:

sorted\_tokens = data.scan(iptok).sort

#The following code pushes in arr pairs of token, count  
arr =   
prev\_token = nil  
count = 0  
sorted\_tokens.each do |tok|  
if tok == prev\_token  
count += 1  
else  
arr \<\< prev\_token \<\< count  
prev\_token = tok  
count = 1  
end  
end  
if count \> 0  
arr \<\< prev\_token \<\< count  
end

h = Hash[\*arr]

> **···**
>
> –  
> Best regards,  
> Bulat [mailto:bulatz@integ.ru](mailto:bulatz@integ.ru)

---

<div class="post-metadata">

**Author:** ![Eric\_Hodel1](https://avatars.discourse-cdn.com/v4/letter/e/a9adbd/32.png) [@Eric\_Hodel1](https://rubytalk.org/u/Eric_Hodel1)\
**Post date:** [20 February 2003 01:22 UTC](https://rubytalk.org/t/optimization-question/4813/6 "2003-02-20T01:22:56Z")

</div>

(I’m making a big assumption here, so if I’m wrong, please kindly  
disregard)

Since I’ve lost the original email, I’ll just say that I there’s a  
more efficient way to do what you’re doing. Keep a real database of  
tokens, and use mail to update it, rather than re-tokenizing the whole  
email set.

See: [http://glueless.net/bayes/](http://glueless.net/bayes/) (not by me)

My .rbayes-corpus.db is 10MB, and I started using it in Sept.

> **···**
>
> Daniel Carrera (dcarrera@math.umd.edu) wrote:
> 
> > On Thu, Feb 20, 2003 at 07:53:14AM +0900, Travis Whitton wrote:
> > 
> > > # This is ran about a million times
> > > 
> > > h = Hash.new(0)  
> > > data.scan(iptok).each do |tok|  
> > > h[tok] += 1  
> > > end
> > 
> > 1. Are the tokens strings?
> > 2. Are you running Linux?
> > 
> > You might be able to use glib hashes to do this in C and then translate  
> > those to Ruby hashes. Just a thought. I’m putting together some code to  
> > see if I can figure it out.
> 
> –  
> Eric Hodel - [drbrain@segment7.net](mailto:drbrain@segment7.net) - [http://segment7.net](http://segment7.net)  
> All messages signed with fingerprint:  
> FEC2 57F1 D465 EB15 5D6E 7C11 332A 551C 796C 9F04

---

<div class="post-metadata">

**Author:** ![Daniel\_Carrera](https://avatars.discourse-cdn.com/v4/letter/d/c67d28/32.png) [@Daniel\_Carrera](https://rubytalk.org/u/Daniel_Carrera)\
**Post date:** [20 February 2003 02:05 UTC](https://rubytalk.org/t/optimization-question/4813/7 "2003-02-20T02:05:25Z")

</div>

Sorry, forgot to attach the files.

[Filter.c](https://rubytalk.org/uploads/short-url/wb7PrYPD5nrKzw1uYwzEBcAo4uW.c) (1.21 KB)

[extconf.rb](https://rubytalk.org/uploads/short-url/9S35pRIDTtz63GyF4zFKSPWMa06.rb) (139 Bytes)

> **···**
>
> On Thu, Feb 20, 2003 at 10:59:48AM +0900, Daniel Carrera wrote:
> 
> > I wrote a C version of your code which uses glib. I’m attaching it as  
> > Filter.c, as well as the extconf.rb. If you have glib, you can just do:
> > 
> > ruby extconf.rb  
> > make
> > 
> > This creates Filter.so. There seems to be a performance improvement, but  
> > it’s not as large as I might have hoped. Here are 3 tests:
> > 
> > \<----- t1.rb ---- Your original code -------------------\>  
> > 5\_000.times do  
> > h = Hash.new(0)  
> > %w{a b c a g d e f a g h g i j e e k l m g d d a b c}.each do |tok|  
> > h[tok] += 1  
> > end  
> > end  
> > \<----- t2.rb ---- Replaced Array#each by a for loop. —\>  
> > 5\_000.times do  
> > h = Hash.new(0)  
> > for tok in %w{a b c a g d e f a g h g i j e e k l m g d d a b c}  
> > h[tok] += 1  
> > end  
> > end  
> > \<----- t3.rb ---- Uses the C version. -------------------\>  
> > require “Filter”
> > 
> > 5\_000.times do  
> > h = Filter.process %w{a b c a g d e f a g h g i j e e k l m g d d a b c}  
> > end  
> > \<-----------------------------\>  
> > And here are some results:
> > 
> > dcarrera $ time ruby t1.rb
> > 
> > real 0m3.205s  
> > user 0m3.130s  
> > sys 0m0.010s  
> > dcarrera $ time ruby t2.rb
> > 
> > real 0m3.006s  
> > user 0m2.860s  
> > sys 0m0.030s  
> > dcarrera $ time ruby t3.rb
> > 
> > real 0m1.677s  
> > user 0m1.490s  
> > sys 0m0.090s
> > 
> > Who knows, this might behave better with your data.
> > 
> > On Thu, Feb 20, 2003 at 07:53:14AM +0900, Travis Whitton wrote:
> > 
> > > Hello - A friend and I have been working on a Ruby implementation of a  
> > > bayesian spam filter as described in Paul Graham’s, Plan For Spam.  
> > > It’s fully functional, but I’ve been trying to squeeze more performance out  
> > > of it as it’s quite slow ATM(15 minutes to run across 20 megs of email).  
> > > By using profile and rbprof, I’ve determined that our tokenizer method is  
> > > the main source of slowness. After some careful benchmarking, I’ve found this  
> > > to be the problem.
> > > 
> > > # This is ran about a million times
> > > 
> > > h = Hash.new(0)  
> > > data.scan(iptok).each do |tok|  
> > > h[tok] += 1  
> > > end
> > > 
> > > At first, I though I could do something like this:
> > > 
> > > # This is ran about a million times
> > > 
> > > h = Hash.new(0)  
> > > data.scan(iptok).each do |tok|  
> > > h[tok].succ  
> > > end
> > > 
> > > But I realized that it doesn’t modify the final value; however, I did notice  
> > > that it ran twice as fast than the former example. So, my question is, does the  
> > > assignment in the first example really have that much overhead? If so, is there  
> > > any way to do the first example using Inline::C or something similar?
> > > 
> > > Thanks in advance,  
> > > Travis
> > 
> > –  
> > Daniel Carrera  
> > Graduate Teaching Assistant. Math Dept.  
> > University of Maryland. (301) 405-5137
> 
> –  
> Daniel Carrera  
> Graduate Teaching Assistant. Math Dept.  
> University of Maryland. (301) 405-5137

---

<div class="post-metadata">

**Author:** ![Travis](https://avatars.discourse-cdn.com/v4/letter/t/bbce88/32.png) [@Travis](https://rubytalk.org/u/Travis)\
**Post date:** [20 February 2003 05:14 UTC](https://rubytalk.org/t/optimization-question/4813/8 "2003-02-20T05:14:09Z")

</div>

> 1. Are the tokens strings?

Yes, my program goes through two files. One consists of only non-spam  
messages, and the other is only spam messages. It goes through each file  
line by line and divides each line into tokens of interesting data. Here are  
the relevant portions of my tokenizer method.

def tokenizer(fh)  
hash = Hash.new(0)  
ipaddr = ‘[0-9]+.[0-9]+.[0-9]+.[0-9]+’  
token = “[A-Za-z$][A-Za-z0-9$'.-]+[A-Za-z0-9$]”  
iptok = Regexp.compile(“#{token}|#{ipaddr}”)

fh.each do |data|  
data.chomp!  
# do a number of string substitutions which use negligible amounts of time  
data.scan(iptok).each do |tok|  
hash[tok] = hash[tok].succ  
end  
end  
hash  
end

The messages are standard unix messages(mbox format?) like so:  
  
From MAILER-DAEMON Mon Sep 23 22:32:37 2002

> **···**
>
> Date: 23 Sep 2002 22:32:37 -0400  
> From: Mail System Internal Data [MAILER-DAEMON@grub.ath.cx](mailto:MAILER-DAEMON@grub.ath.cx)  
> Subject: DON’T DELETE THIS MESSAGE – FOLDER INTERNAL DATA  
> Message-ID: [1032834757@grub.atlantic.net](mailto:1032834757@grub.atlantic.net)  
> X-IMAP: 1032834509 0000000272  
> Status: RO
> 
> This text is part of the internal format of your mail folder, and is not  
> a real message. It is created automatically by the mail system software.  
> If deleted, important folder data will be lost, and it will be re-created  
> with the data reset to initial values.
> 
> > 1. Are you running Linux?
> 
> Yes, and I only intend for this program to run under unix based systems.
> 
> > You might be able to use glib hashes to do this in C and then translate  
> > those to Ruby hashes. Just a thought. I’m putting together some code to  
> > see if I can figure it out.
> 
> Thanks very much for your help. I sincerely appreciate it! As a side note,  
> the program is already on the RAA:
> 
> [http://raa.ruby-lang.org/list.rhtml?name=bsproc](http://raa.ruby-lang.org/list.rhtml?name=bsproc)
> 
> So, you can grok through the code if you would like to; however, it’s not  
> exactly the same as the development version. As a second side not, although  
> it is slow to create the probability database, the program is _extremely_  
> good at filtering spam. A very small minority of spam messages make their way  
> into my inbox, and it feels damned good to have written my own spam filter.  
> Also, I’ve tried strscan in place of scan, and the speedup wasn’t significant.  
> As it turns out, most of the calculation time is spend doing hash lookups. I’ve  
> considered RJudy, but apparently, it’s hashes are slower than Ruby native  
> hashes… go figure.
> 
> Thanks much,  
> Travis

---

<div class="post-metadata">

**Author:** ![Daniel\_Carrera](https://avatars.discourse-cdn.com/v4/letter/d/c67d28/32.png) [@Daniel\_Carrera](https://rubytalk.org/u/Daniel_Carrera)\
**Post date:** [20 February 2003 06:13 UTC](https://rubytalk.org/t/optimization-question/4813/9 "2003-02-20T06:13:16Z")

</div>

I think that sorting is about as expensive as hashing.  
Here is a quick benchmark for 5,000 iterations:

$ time ruby original\_code.rb

real 0m3.888s  
user 0m3.520s  
sys 0m0.020s

$ time ruby your\_code.rb

real 0m3.453s  
user 0m3.140s  
sys 0m0.040s

I still think that using C is a good idea.

> **···**
>
> On Thu, Feb 20, 2003 at 02:58:08PM +0900, Bulat Ziganshin wrote:
> 
> > Hello Travis,
> > 
> > Thursday, February 20, 2003, 1:53:14 AM, you wrote:
> > 
> > > # This is ran about a million times
> > > 
> > > h = Hash.new(0)  
> > > data.scan(iptok).each do |tok|  
> > > h[tok] += 1  
> > > end
> > 
> > are you heard about “sort|uniq” idiom?
> 
> –  
> Daniel Carrera  
> Graduate Teaching Assistant. Math Dept.  
> University of Maryland. (301) 405-5137

---

<div class="post-metadata">

**Author:** ![MoonWolf](https://avatars.discourse-cdn.com/v4/letter/m/b9bd4f/32.png) [@MoonWolf](https://rubytalk.org/u/MoonWolf)\
**Post date:** [21 February 2003 08:41 UTC](https://rubytalk.org/t/optimization-question/4813/10 "2003-02-21T08:41:39Z")

</div>

I wrote faster extension ‘hashsucc.so’.  
glib is not needed.

Install:  
 ruby extconf.rb make  
% make install

Usage:  
h = Hash.new(0)  
h.succ! key #=\> equivalent h[key]+=1  
h.succ! %w(foo bar baz) #=\> equivalent  
# %w(foo bar baz).each do |key|  
# h[key]+=1  
# end

\<----- b\_orig.rb ---- original code -------------------\>  
50\_000.times do  
h = Hash.new(0)  
for tok in %w{a b c a g d e f a g h g i j e e k l m g d d a b c}  
h[tok] += 1  
end  
end  
\<----- b\_filter.rb ---- Filter.so -------------------\>  
require “Filter”

50\_000.times do  
h = Filter.process %w{a b c a g d e f a g h g i j e e k l m g d d a b c}  
end  
\<----- b\_hashsucc.rb ---- hashsucc.so -------------------\>  
require “hashsucc”

50\_000.times do  
Hash.new.succ! %w{a b c a g d e f a g h g i j e e k l m g d d a b c}  
end  
\<-----------------------------\>

Results:  
 time ruby b\_orig.rb ruby b\_orig.rb 12.46s user 0.01s system 100% cpu 12.467 total time ruby b\_filter.rb  
ruby b\_filter.rb 8.29s user 0.12s system 100% cpu 8.402 total  
$ time ruby b\_hashsucc.rb  
ruby b\_hashsucc.rb 5.00s user 0.01s system 100% cpu 5.004 total

[extconf.rb](https://rubytalk.org/uploads/short-url/wp6yc6d0NYYFs9R5flQ11qSl7dz.rb) (71 Bytes)

[hashsucc.c](https://rubytalk.org/uploads/short-url/qbC0VqPoLJfn9HXa9YQP4MRnDtI.c) (878 Bytes)

> **···**
>
> –  
> MoonWolf [moonwolf@moonwolf.com](mailto:moonwolf@moonwolf.com)

---

<div class="post-metadata">

**Author:** ![Travis](https://avatars.discourse-cdn.com/v4/letter/t/bbce88/32.png) [@Travis](https://rubytalk.org/u/Travis)\
**Post date:** [20 February 2003 05:34 UTC](https://rubytalk.org/t/optimization-question/4813/11 "2003-02-20T05:34:17Z")

</div>

> Since I’ve lost the original email, I’ll just say that I there’s a  
> more efficient way to do what you’re doing. Keep a real database of  
> tokens, and use mail to update it, rather than re-tokenizing the whole  
> email set.

This is a good idea, and it looks like an interesting project. Does it allow  
you to create a database file from already existing corpus files, or does it  
require you to start from scratch? I’ve spent a good amount of time building  
up the 2000 some-odd messages I’m currently using to gather my statistics,  
and I’d hate to have two huge corpus files wasted. Also, the main reason I  
started this project was to learn, so I’d still like to find a fast way to  
update a hash key without having to access it twice.

Thanks,  
Travis

---

<div class="post-metadata">

**Author:** ![Bulat\_Ziganshin](https://avatars.discourse-cdn.com/v4/letter/b/ba8739/32.png) [@Bulat\_Ziganshin](https://rubytalk.org/u/Bulat_Ziganshin)\
**Post date:** [20 February 2003 06:57 UTC](https://rubytalk.org/t/optimization-question/4813/12 "2003-02-20T06:57:03Z")

</div>

Hello Daniel,

Thursday, February 20, 2003, 9:13:16 AM, you wrote:

> I think that sorting is about as expensive as hashing.  
> Here is a quick benchmark for 5,000 iterations:

i think that really expensive is interpreting the code.  
if you think about C code, you can try to squeeze second  
block in my program into Array#uniqc method. imvho,  
it is the simplest way to speed up your program - just  
because other variants will require much more efforts  
to code

> **···**
>
> –  
> Best regards,  
> Bulat [mailto:bulatz@integ.ru](mailto:bulatz@integ.ru)

---

<div class="post-metadata">

**Author:** ![Bulat\_Ziganshin](https://avatars.discourse-cdn.com/v4/letter/b/ba8739/32.png) [@Bulat\_Ziganshin](https://rubytalk.org/u/Bulat_Ziganshin)\
**Post date:** [20 February 2003 07:04 UTC](https://rubytalk.org/t/optimization-question/4813/13 "2003-02-20T07:04:03Z")

</div>

Hello Daniel,

Thursday, February 20, 2003, 9:13:16 AM, you wrote:

> > > # This is ran about a million times
> > > 
> > > h = Hash.new(0)  
> > > data.scan(iptok).each do |tok|  
> > > h[tok] += 1  
> > > end
> > 
> > are you heard about “sort|uniq” idiom?

> I still think that using C is a good idea.

sorry, i don’t seen that your are not Travis 🙂

i think that better way to speed up this code is:

h = data.scan(iptok).sort.uniqc.to\_hash

where  
Array#to\_hash - reverse operaqion to Hash#to\_a  
Array#uniqc - gets sorted array of items and returns array of pairs [item, count]

and these two methods must be included in Ruby itself, because they support  
very widespread programming idioms

> **···**
>
> –  
> Best regards,  
> Bulat [mailto:bulatz@integ.ru](mailto:bulatz@integ.ru)

---

<div class="post-metadata">

**Author:** ![Robert](https://avatars.discourse-cdn.com/v4/letter/r/e95f7d/32.png) [@Robert](https://rubytalk.org/u/Robert)\
**Post date:** [20 February 2003 09:37 UTC](https://rubytalk.org/t/optimization-question/4813/14 "2003-02-20T09:37:56Z")

</div>

“Travis Whitton” [whitton@atlantic.net](mailto:whitton@atlantic.net) schrieb im Newsbeitrag  
[news:BhZ4a.10243$Mr5.3967@fe06.atl2.webusenet.com](mailto:news:BhZ4a.10243$Mr5.3967@fe06.atl2.webusenet.com)…

> > 1. Are the tokens strings?
> 
> Yes, my program goes through two files. One consists of only non-spam  
> messages, and the other is only spam messages. It goes through each file  
> line by line and divides each line into tokens of interesting data. Here  
> are  
> the relevant portions of my tokenizer method.
> 
> def tokenizer(fh)  
> hash = Hash.new(0)  
> ipaddr = ‘[0-9]+.[0-9]+.[0-9]+.[0-9]+’

Maybe you can improve performance by changing this to:

ipaddr = ‘[0-9]{1,3}.[0-9]{1,3}.[0-9]{1,3}.[0-9]{1,3}’

or

ipaddr = ‘[0-9]{1,3}(.[0-9]{1,3}){3}’

This should make the regexp fail faster for longer sequences of digits.  
Just a guess, but maybe worth trying.

Regards

```
robert

```

> token = “[A-Za-z$][A-Za-z0-9$'.-]+[A-Za-z0-9$]”  
> iptok = Regexp.compile(“#{token}|#{ipaddr}”)
> 
> fh.each do |data|  
> data.chomp!  
> # do a number of string substitutions which use negligible amounts of  
> time  
> data.scan(iptok).each do |tok|  
> hash[tok] = hash[tok].succ  
> end  
> end  
> hash  
> end
> 
> The messages are standard unix messages(mbox format?) like so:  
>   
> From MAILER-DAEMON Mon Sep 23 22:32:37 2002  
> Date: 23 Sep 2002 22:32:37 -0400  
> From: Mail System Internal Data [MAILER-DAEMON@grub.ath.cx](mailto:MAILER-DAEMON@grub.ath.cx)  
> Subject: DON’T DELETE THIS MESSAGE – FOLDER INTERNAL DATA  
> Message-ID: [1032834757@grub.atlantic.net](mailto:1032834757@grub.atlantic.net)  
> X-IMAP: 1032834509 0000000272  
> Status: RO
> 
> This text is part of the internal format of your mail folder, and is not  
> a real message. It is created automatically by the mail system software.  
> If deleted, important folder data will be lost, and it will be re-created  
> with the data reset to initial values.
> 
> > 1. Are you running Linux?
> 
> Yes, and I only intend for this program to run under unix based systems.
> 
> > You might be able to use glib hashes to do this in C and then translate  
> > those to Ruby hashes. Just a thought. I’m putting together some code  
> > to  
> > see if I can figure it out.
> 
> Thanks very much for your help. I sincerely appreciate it! As a side  
> note,  
> the program is already on the RAA:
> 
> [http://raa.ruby-lang.org/list.rhtml?name=bsproc](http://raa.ruby-lang.org/list.rhtml?name=bsproc)
> 
> So, you can grok through the code if you would like to; however, it’s not  
> exactly the same as the development version. As a second side not,  
> although  
> it is slow to create the probability database, the program is _extremely_  
> good at filtering spam. A very small minority of spam messages make their  
> way  
> into my inbox, and it feels damned good to have written my own spam  
> filter.  
> Also, I’ve tried strscan in place of scan, and the speedup wasn’t  
> significant.  
> As it turns out, most of the calculation time is spend doing hash  
> lookups. I’ve

> **···**
>
> > considered RJudy, but apparently, it’s hashes are slower than Ruby native  
> > hashes… go figure.
> > 
> > Thanks much,  
> > Travis

---

<div class="post-metadata">

**Author:** ![Michael\_Campbell1](https://avatars.discourse-cdn.com/v4/letter/m/e274bd/32.png) [@Michael\_Campbell1](https://rubytalk.org/u/Michael_Campbell1)\
**Post date:** [20 February 2003 13:24 UTC](https://rubytalk.org/t/optimization-question/4813/15 "2003-02-20T13:24:06Z")

</div>

> Yes, my program goes through two files. …

You might want to take a look at a perl implementation called POPfile. It’s  
more of a classical bayes implementation without the “tweaks” and such that Paul  
Graham has introduced. Too, it allows arbitrary buckets, not just “spam/not  
spam”.

It’s on sourceforge, so you can get the source.

Just a thought to give you some ideas on further enhancements and/or maybe how  
they solved the same problems you’re having. (I run it, BTW, and am getting  
about a 98% success rate with my mail, being filtered into 5 different buckets,  
1 of them being a “spam” catchall.)

---

<div class="post-metadata">

**Author:** ![Daniel\_Carrera](https://avatars.discourse-cdn.com/v4/letter/d/c67d28/32.png) [@Daniel\_Carrera](https://rubytalk.org/u/Daniel_Carrera)\
**Post date:** [21 February 2003 13:54 UTC](https://rubytalk.org/t/optimization-question/4813/16 "2003-02-21T13:54:00Z")

</div>

Good stuff.  
I’ll take a look at it after class.

> **···**
>
> On Fri, Feb 21, 2003 at 05:41:39PM +0900, MoonWolf wrote:
> 
> > Results:  
> > $ time ruby b\_orig.rb  
> > ruby b\_orig.rb 12.46s user 0.01s system 100% cpu 12.467 total  
> > $ time ruby b\_filter.rb  
> > ruby b\_filter.rb 8.29s user 0.12s system 100% cpu 8.402 total  
> > $ time ruby b\_hashsucc.rb  
> > ruby b\_hashsucc.rb 5.00s user 0.01s system 100% cpu 5.004 total
> 
> –  
> Daniel Carrera  
> Graduate Teaching Assistant. Math Dept.  
> University of Maryland. (301) 405-5137

---

<div class="post-metadata">

**Author:** ![Brian\_Candler](https://avatars.discourse-cdn.com/v4/letter/b/5f9b8f/32.png) [@Brian\_Candler](https://rubytalk.org/u/Brian_Candler)\
**Post date:** [21 February 2003 14:18 UTC](https://rubytalk.org/t/optimization-question/4813/17 "2003-02-21T14:18:07Z")

</div>

Nice. Perhaps could be made more general by checking if the value is a  
Fixnum first? (And if not, it could do h = h.succ)

Regards,

Brian.

> **···**
>
> On Fri, Feb 21, 2003 at 05:41:39PM +0900, MoonWolf wrote:
> 
> > I wrote faster extension 'hashsucc.so'.  
> > glib is not needed.

---

<div class="post-metadata">

**Author:** ![Travis](https://avatars.discourse-cdn.com/v4/letter/t/bbce88/32.png) [@Travis](https://rubytalk.org/u/Travis)\
**Post date:** [20 February 2003 15:38 UTC](https://rubytalk.org/t/optimization-question/4813/18 "2003-02-20T15:38:33Z")

</div>

> i think that better way to speed up this code is:
> 
> h = data.scan(iptok).sort.uniqc.to\_hash

I’m using Ruby 1.6.8, which doesn’t have a to\_hash or uniqc method. When  
were these methods introduced?

-Travis

---

<div class="post-metadata">

**Author:** ![Daniel\_Carrera](https://avatars.discourse-cdn.com/v4/letter/d/c67d28/32.png) [@Daniel\_Carrera](https://rubytalk.org/u/Daniel_Carrera)\
**Post date:** [20 February 2003 15:51 UTC](https://rubytalk.org/t/optimization-question/4813/19 "2003-02-20T15:51:42Z")

</div>

Yeah. I’ll think about writing an Array#uniqc method this afternoon. It  
might turn out to be easier than the one I wrote yesterday.

> **···**
>
> On Thu, Feb 20, 2003 at 03:57:03PM +0900, Bulat Ziganshin wrote:
> 
> > Hello Daniel,
> > 
> > Thursday, February 20, 2003, 9:13:16 AM, you wrote:
> > 
> > > I think that sorting is about as expensive as hashing.  
> > > Here is a quick benchmark for 5,000 iterations:
> > 
> > i think that really expensive is interpreting the code.  
> > if you think about C code, you can try to squeeze second  
> > block in my program into Array#uniqc method. imvho,  
> > it is the simplest way to speed up your program - just  
> > because other variants will require much more efforts  
> > to code
> 
> –  
> Daniel Carrera  
> Graduate Teaching Assistant. Math Dept.  
> University of Maryland. (301) 405-5137

---

<div class="post-metadata">

**Author:** ![Eric\_Hodel1](https://avatars.discourse-cdn.com/v4/letter/e/a9adbd/32.png) [@Eric\_Hodel1](https://rubytalk.org/u/Eric_Hodel1)\
**Post date:** [20 February 2003 16:55 UTC](https://rubytalk.org/t/optimization-question/4813/20 "2003-02-20T16:55:33Z")

</div>

Yeah, I understand the learning bit 🙂 I do lots of stuff that other  
people have done, just for the hell of it.

You’ll just feed each corpus file into the filter, one marked as spam,  
the other marked as good. After that, you’re done. Use procmail to  
look at each message, decide if it is spam or not, then place it in a  
spam folder if its spam, or let it go through the rest of your filters  
if not. There’s also a mutt keybinding that marks it as spam/good mail,  
which removes it as spam, then re-adds it as good.

Also, if you want help with RubyInline, I suggest you mail  
[ruby@zenspider.com](mailto:ruby@zenspider.com), or the author himself, he doesn’t read this list.

> **···**
>
> Travis Whitton ([whitton@atlantic.net](mailto:whitton@atlantic.net)) wrote:
> 
> > > Since I’ve lost the original email, I’ll just say that I there’s a  
> > > more efficient way to do what you’re doing. Keep a real database of  
> > > tokens, and use mail to update it, rather than re-tokenizing the whole  
> > > email set.
> > 
> > This is a good idea, and it looks like an interesting project. Does it allow  
> > you to create a database file from already existing corpus files, or does it  
> > require you to start from scratch? I’ve spent a good amount of time building  
> > up the 2000 some-odd messages I’m currently using to gather my statistics,  
> > and I’d hate to have two huge corpus files wasted. Also, the main reason I  
> > started this project was to learn, so I’d still like to find a fast way to  
> > update a hash key without having to access it twice.
> 
> –  
> Eric Hodel - [drbrain@segment7.net](mailto:drbrain@segment7.net) - [http://segment7.net](http://segment7.net)  
> All messages signed with fingerprint:  
> FEC2 57F1 D465 EB15 5D6E 7C11 332A 551C 796C 9F04

[Next page](https://rubytalk.org/t/optimization-question/4813.md?page=2)