Re: [9fans] env walk

[Sam <sah@softcardsystems.com>]

schweet

John had looked at it on Monday and it said Showers Sat-Mon...guess the storm 
got pushed back.

... ok, I'm getting a little excited now.

:)

On Wednesday 09 May 2001 12:58, you wrote:
> The n**2 comes from the ls M* walking each entry in the environment
> with envwalk walking from the first to that entry every time.  All the
> time is spent in the devdir+convM2D in procgen.  The
>
> 	for(e = eg->entries; e && s; e = e->link)
> 		s--;
>
> is pretty much fleeting even for 1000 entries.  Otherwise the algorithm for
> your example would be n**3.
>
> for example:
>
> #include <u.h>
> #include <libc.h>
>
> struct X
> {
> 	struct X *next;
> };
>
> struct X x[1000];
>
> void
> main(void)
> {
> 	struct X *p;
> 	int i, j;
>
> 	for(i = 0; i < nelem(x)-1; i++)
> 		x[i].next = &x[i+1];
>
> 	for(i = 0; i < nelem(x); i++)
> 		for(j = 0, p = x; j < i && p != nil; p = p->next, j++)
> 			;
>
> }
>
> takes .01 seconds on my crufty old machine.
> The advantage to your loop is that you take all the useless stuff
> that devdir does out of the inner loop, not too mention the call
> itself.

-- 


Sam Hopkins
------------------------------------------------
QOTD:
"Design top down, implement bottom up."