[DGD] Remove Multiple Instances from Array

[Michael McKiel]

> 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 });
> }

I've been thinking on this, and a way to preserve order/nonalphabatized for
very large 1000s+ sized arrays would something like this get rid of the
O(N)^2 problem? assume arr is a passed in large array.


mixed * nonAlpha_nix_dupes_in_array(mixed *arr)
{
    mapping map;
    mapping dat;
    int i, sz, count;

    map = ([ ]);
    dat = ([ ]);

    for (i=0, sz=sizeof(arr); i < sz; i++)
    {
        if (!map[arr[i]] && arr[i] && arr[i] != "") {
            count++;
            map[arr[i]] = TRUE;
            dat[count] = arr[i];
        }
    }
    return sizeof(map_values(dat)) ? map_values(dat) : nil;
}

AH think anyways. Though I think I'll keep my one liner for ittybitty arrays
hehe :)


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