[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
## Re: What is the runtime complexity of $(filter )?

**From**: |
Peng Yu |

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

**Date**: |
Sat, 9 Jan 2010 15:07:34 -0600 |

On Fri, Jan 8, 2010 at 12:34 PM, Paul Smith <address@hidden> wrote:
>* 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.*
I want to measure much the runtimes for each of the three operations
that computes A, B and C. I'm wondering how to do it with gnu make.
$ cat Makefile
.PHONY: all
A=$(patsubst %.1, %, $(wildcard *.1))
B=$(patsubst %.2, %, $(wildcard *.2))
C=$(filter $(A),$(B))
all:
echo $(C)
a:
@touch a.1 b.1 c.1
b:
@touch a.2 b.2 d.2