Search algorithms in __gnu_cxx::

Paolo Carlini pcarlini@suse.de
Mon Sep 18 10:06:00 GMT 2006


Dhruv Matani wrote:

>> all the complexity figures of the Boyer-Moore algorithm are not valid
>> anymore.
>
> No, we don't want to do that. Because using a map like that means that
>
> Yes, you are kind of right, but not entirely. The complexity remains
> the same. It's just that the constants in the big oh notation get
> blown out of proportion because of the lookup times in the hash maps.

No, at minimum we have to start talking about *average* complexity, 
instead of plain complexity as in the real BM algorithm. And of course, 
in practice, the constants are plain horrible...

>> Therefore, either we find a better way to deal with that
>> problem (I suggest we don't give up so quickly, no reason to rush) or we
>> have to deliver the algorithm only for chars.
>
> I'm not ruling out any possibilities, but in all fairness, I think the
> Boyer-Moore(and other string matching) algorithms rely on the fact
> that these tables could be created and looked up fairly
> quickly(comparable to character compare time)

Certainly.

Paolo.



More information about the Libstdc++ mailing list