From: Martin Hansen <mail@...>
Date: 2011-04-19T22:13:02+09:00
Subject: Re: Need for speed -> a C extension?

> IMHO it would be better to separate representation of the sequence and
> the matching process.  The matcher then would only carry a reference
> to the sequence and all the data it needs to do matching.

I am not sure if I understand this. I have tried to copy the behavior of 
String#match.

> Also #vector_update creates a lot of objects and does so for each
> position in the sequence.  That's likely where you can improve things.

Yes, that is quite possible. I might be able to skip .dup on line 128 
and 130. That will require some thinking and testing on my side.

> I am not sure what the matching algorithm is exactly.  Can you summarize
> it?

Well, it is a dynamic programming algorithm to do fuzzy searches of 
patterns in strings - allowing for custom matching rules (A==N, etc) and 
a maximum edit distance. Inspired by the paper by Bruno Woltzenlogel 
Paleo (page 197):

http://www.logic.at/people/bruno/Papers/2007-GATE-ESSLLI.pdf

A short example:

http://pastie.org/1811496


> you can make matching simpler
>
> def match?(char1, char2)
>     (EQUAL[char1.ord] & EQUAL[char2.ord]) != 0
> end

Yes, but that should not give any significant speed increase?

> You might as well consider changing the Array into a Hash.  Then you
> can even get rid of the #ord call.

Actually, I started with a hash for this - and it was slightly faster. 
However, I think this bit field is very elegant - and since I was 
preparing for porting to C - I think this is the way to go!



Cheers


Martin

-- 
Posted via http://www.ruby-forum.com/.