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: string::find complexity.

From: Ian Lance Taylor <ian at wasabisystems dot com>
To: Paolo Carlini <pcarlini at suse dot de>
Cc: libstdc++ <libstdc++ at gcc dot gnu dot org>
Date: 10 Jun 2004 12:10:08 -0400
Subject: Re: string::find complexity.
References: <1086847470.13398.8.camel@localhost.localdomain><xypwu2fsany.fsf@miranda.boston.redhat.com><m3d6472ytj.fsf@gossamer.airs.com> <40C8866B.2060000@suse.de>

Paolo Carlini <pcarlini@suse.de> writes:

> Ian Lance Taylor wrote:
> 
> >Of course, KMP is only a win when the length of the string is
> >significantly greater than the length of the pattern.
> >
> ... and, what happens when that't not true? Does it lose bad?

How bad is bad, and how much do we care?  There are certainly cases
where KMP loses quite badly.  Consider a pattern of length 100 and
text of length 101.  Suppose all the characters in the pattern are
different.  If the pattern does not match at the head, the current
algorithm does at most one extra compare.  With KMP you spend a lot of
time building an automaton, and you still do one extra compare.  I'm
sure the overall time would be much worse (especially in the micro
benchmarks you've been using).

Ian

Follow-Ups:
- Re: string::find complexity.
  - From: Paolo Carlini

References:
- string::find complexity.
  - From: Dhruv Matani
- Re: string::find complexity.
  - From: Jason Merrill
- Re: string::find complexity.
  - From: Ian Lance Taylor
- Re: string::find complexity.
  - From: Paolo Carlini

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