This is the mail archive of the libstdc++@gcc.gnu.org mailing list for the libstdc++ project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: Search algorithms in __gnu_cxx::


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.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]