Mappings in DGD

From: DGD Mailing List (Par Winzell)
Date: Tue Apr  6 08:08:01 2004
Subject: [DGD] Remove Multiple Instances from Array

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

From: dgd at list.imaginary.com (Felix A. Croes)
Date: Mon Oct 22 10:32:01 2001
Subject: [DGD] Invalid ranges...

Troels Therkelsen wrote:

>[...]
> Ok, I personally think that is a bit far-fetched and contrived.  Out of
> bounds is out of bounds, period.  IMHO, anyway.  And if
>
>   ({1, 2, 3})[3..] == ({ })  <=>   ({1, 2, 3})[3..2] == ({ })
>
> why doesn't it work for range underflow:
>
>   ({1, 2, 3})[-1..0] == error

Oh, but it does:

    ({ 1, 2, 3 })[0 .. -1] == ({ })

So the two special cases are [0 .. 0-1] and [size .. size-1], and the
general case is [x .. x-1] == ({ }), for 0 <= x <= size.  To be
consistent with normal ranges, xxx[-1 .. 0] would have to be an array
of <two> elements, if it worked at all.

I'm sorry that you think this is kludgy.  Personally, I think that
returning ({ }) for any invalid range is dangerous, <unless> ({ }) and
([ ]) were somehow equivalent with nil -- which is something that many
have requested for the sake of convenience, but actually, LPC is a more
expressive language with that distinction.

Regards,
Dworkin

From: DGD Mailing List (Felix A. Croes)
Date: Sat Mar  6 10:21:01 2004
Subject: [DGD] Bitwise on Arrays & Efficiency

Michael McKiel wrote:

> I've recently come across bitwise operations on arrays, though I seen them
> before in passing never really grasped what they were doing, nor really how
> bitwise could be done on an array.
> What I was wondering is, are there any other operators that can be used on
> arrays, besides '&' '|' ?

A & B: A - (A - B)
A | B: A + (B - A)
A ^ B: (A - B) + (B - A)


> Previously I had been using the member_array() that is found in Melville, but
> realized that loops thru the array piece by piece til it finds the element.
> Regarding efficiency, I'd assume bitwise AND(&) to be better than that,
> but...
> Wouldn't it in effect have to do the same type of looping - just at the
> driver level? ie: 
>     sizeof(someArr & ({ element })) != 0

The driver doesn't do anything extraordinary.  It is only faster because
it works at a level below LPC.


>[...]
> And for array concatenation we have:
> 1/    someArr += ({ element });
> 2/    someArr = someArr | ({ element });
>
> I take it version one creates a new array in memory to perform its task, and
> version 2 doesn't?

A | B is not array concatenation, see above.  By the way, you can
use &=, |= and ^= on arrays, too.


> And the only way I can find to remove nil's from arrays would be:
> 1/    someArr -= ({ nil });
> 2/    someArr = someArr - ({nil});
>
> Again I assume those both make another array, is there some way to do so
> without making another array? :)

No, the only operation on an array that modifies it without creating
a new array is arr[i] = val.

Regards,
Dworkin