[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: What is the runtime complexity of $(filter )?

From: Paul Smith
Subject: Re: What is the runtime complexity of $(filter )?
Date: Fri, 8 Jan 2010 13:34:15 -0500

On Sat, 2010-01-09 at 11:33 +1800, Peng Yu wrote:
> I run $(filter ) with each argument of thousands of strings. It runs
> slow. I'm wondering what the run time complexity of $(filter ) is.
> Suppose I have n strings for each argument. Is the run time complexity
> n*n or log(n)?

If you run $(filter <N-strings>,<M-strings>) then the worst-case
complexity is N*M of course.

However, make does try to be smart.  If N and M are large enough (and
actually, "large enough" is pretty small: if N>1 and N*M>9) then instead
of doing the matching linearly, make will add the words (M, above) into
a hash table and do hash lookups for matching rather than walking an

This is true in make 3.81 and above; I didn't check 3.80 or below.

reply via email to

[Prev in Thread] Current Thread [Next in Thread]