[DGD] Remove Multiple Instances from Array

[Michael McKiel]

 --- Par Winzell <zell at skotos.net> wrote: > Michael,
> 
> > /* Remove multiple instances of the same word, preserving order. 
> > ** Note: >= 1; we don't check the first element since previous
> > ** matching elements in the arrary were already removed.
> > */
> > for (i=sz=sizeof(keys); --i >= 1; )
> > {
> >     if (keys[i] == "" || sizeof(({ keys[i] }) | keys) != sz)
> >         keys[i] = nil;
> > }
> > keys -= ({ nil });
> 
> Pretty smooth, but unfortunately this takes quadratic time. For a 
> one-thousand word string, you'd end up looping over hundreds of 
> thousands of array elements (you loop N times in LPC and the union 
> operator has to loop over an array of size N => N^2).
> 
> Perhaps something like:
> 
> {
>    mapping set;
>    string *words;
>    int i;
> 
>    set = ([ ]);
>    keys = explode(str, " ");
> 
>    for (i = 0; i < sizeof(keys); i ++) {
>      if (keys[i] == "" || !set[keys[i]]) {
>        set[keys[i]] = TRUE;
>        keys[i] = nil;
>    }
>    return keys - ({ nil });
> }
> 
> (note: not tested)
> 
> > Oh yeah I stole Par's comment style ;)
> 
> *beam* :)
> 
> Zell

Well I use it on an array thats guaranteed to be < 10 elements, its to filter
out multiple words in a help query string(redunancy checking to keep things
from breaking by those pesky players that like to do those kinda things, I
think I recall someone like that ;) 
   Though I did have a similiar mapping version as you suggested, that
doesn't preserve order of elements, and alphabatizes them, which I guess in
most cases doesn't matter but - my helpd is perhaps not a common
implementation, and order of elements is one of the facets of how it
determines which help file/object to process when all the arg matchings wind
up with an equal result.

   But good to get that quadradic bit pounded in a little more, I don't tend
to think in those terms, remnants of LISP behaviour I guess, make it small,
make it recursive, do it in one line! hehe.

Zam.

______________________________________________________________________ 
Post your free ad now! http://personals.yahoo.ca
_________________________________________________________________
List config page:  http://list.imaginary.com/mailman/listinfo/dgd