[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: fnmatch has exponential running time
From: |
James Youngman |
Subject: |
Re: fnmatch has exponential running time |
Date: |
Fri, 23 Mar 2007 09:28:47 +0000 |
On 3/22/07, Bruno Haible <address@hidden> 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.