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 array. This is true in make 3.81 and above; I didn't check 3.80 or below. _______________________________________________ Help-make mailing list [email protected] http://lists.gnu.org/mailman/listinfo/help-make
