On Thu, Aug 21, 2003 at 06:37:52PM -0400, Benjamin Goldberg wrote: > > > Nicholas Clark wrote:
> > Particularly when the regexp engine is written assuming O(1) random > > access. > > It doesn't *need* to assume O(1) random access; after all, it's never > accessing *randomly*, it's always accessing just one character away from > some other character that it's recently accessed. Sounds like a job for > an iterator for me. With an iterator, it needs only assume that > advancing the iterator a distance of 1, takes O(1) time. Probably true for the actual regexp engine. But I'm pretty sure that where perl wins (or won, historically - the world is catching up) was in the optimiser, which takes shortcuts and works out where things can't match. I suspect that that does think of things in terms of random character offsets, and independent of that I'm confident that thinking about one in O(1) is easier than thinking about one in O(n) But I've never written one, so who am I to say? Nicholas Clark
