[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: memmem speedup
From: |
James Youngman |
Subject: |
Re: memmem speedup |
Date: |
Tue, 8 Jan 2008 14:34:28 +0000 |
On Jan 8, 2008 1:32 PM, Eric Blake <address@hidden> wrote:
> (I may later factor out the two_way static functions into a parameterized
> header, in order to share code with strstr, strcasestr, ...; however, note
> that strstr can never achieve sublinear performance, because it costs O(n)
> to find the NUL byte that terminates the haystack, and it is not safe to
> read beyond the NUL).
It may be generally useful for applications to have some way of
indicating that they are searching for a constant needle in a large
number of haystacks. In such cases, the preparation only needs to be
done once at all. In the specific case of findutils, locate will
typically search for a single needle in one or two million haystacks.
Of course, locate also always knows the length of both the needle and
the haystack, too.
James.