This is the mail archive of the libc-alpha@sourceware.org mailing list for the glibc 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: fnmatch has exponential running time


On 3/22/07, Bruno Haible <bruno@clisp.org> wrote:
fnmatch() has a worst-case complexity O(m*n) where m is the size of the
pattern and n is the size of the sample string. Unfortunately glibc has
chosen an implementation with exponential running time.

Yes. Oddly, per some testng I did about a year ago, "find -regex" is much faster than "find -name". The former uses the Gnulib regex support and the latter uses fnmatch().

James.


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