help-make
[Top][All Lists]
Advanced

[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

```

reply via email to

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