From: Gavin Kistner <gavin@...>
Date: 2005-05-28T12:53:04+09:00
Subject: Re: How to build an index of phrases in a phrase/sentence?

--Apple-Mail-2--655577882
Content-Transfer-Encoding: 7bit
Content-Type: text/plain;
	charset=US-ASCII;
	delsp=yes;
	format=flowed

Oops, I sent that last reply without performance results.

I loaded in a file with 496 words and calculated all the sub-phrases,  
and measured the time needed to 'parse' the information, and how much  
memory was used. I then timed how long it took to match a sub-phrase  
in the middle of the file, and also to 'find' a phrase that didn't  
exist.

                      user     system      total        real
create array:   12.910000   0.950000  13.860000 ( 15.403606)
run 100:        15.570000   0.220000  15.790000 ( 17.475724)
array - 158MB of VM

                      user     system      total        real
create set:     16.040000   1.100000  17.140000 ( 21.742738)
run 100k:        0.910000   0.000000   0.910000 (  1.088728)
set - 159MB of VM

                      user     system      total        real
create matcher: 85.430000   1.340000  86.770000 ( 96.524512)
run 100k:       10.050000   0.160000  10.210000 ( 11.245722)
matcher - 68MB of VM

Note that the array was measuring only 100 iterations of the 2-phrase  
match, while the other two performed 100 *thousand* iterations.


The array technique is thus over 10,000 slower to find a match than  
the technique using the Set. and about 1,000 slower than the Trie  
version, but does setup the data structure more quickly than either.


The Trie method's memory use should also increase at a slower rate  
than the others as the source string increases, but I don't know how  
to use Ruby to measure VM of a process, so I can't make a simple  
automated test to graph this.


--
"Despite the surge of power you feel upon learning Ruby,
resist the urge to trip others or slap them in the bald head.
DO NOT LORD YOUR RUBYNESS OVER OTHERS!"
- Why the Lucky Stiff


--Apple-Mail-2--655577882--