roxen.lists.pike.general

Subject Author Date
Re: Arrays, multisets, mappings: avoiding unnecessary memory (re)assigns Martin Stjernholm <mast[at]lysator[dot]liu[dot]se> 08-09-2009
"Arjan van Staalduijnen" <<Arjan.van.Staalduijnen[at]rtl.nl>> wrote:

> Hopefully properly answering one of my own questions:
>
>> In this case I was using the multiset as a 'single entry per index
>> only', so the ids[ identifier ] = 1/0 should work just fine for me.
>> Instead of a multiset which sets a specific index to 1 or 0, I
>> could use a mapping and the same construction, using m_delete
>> instead of the setting to 0. Would there be a difference in impact?
>
> Multiset would be faster, because it would only have to do a single
> memory dereference for the index, instead of two for a mapping; one
> for the index, one for the value. If there'd be more differences,
> I'd still be happy to learn about them. :-)

I'm not sure what you mean with those memory dereferences, but if you
want an indexed container without duplicates and where the values
aren't significant then I'd say that a mapping is generally faster.
It's a hash table, and as such people usually consider it O(1) for
lookups. A multiset is a binary tree which has O(log(<size>)) for
lookups.

I often use mappings for such things, and just store a 1 in the value.
E.g:

    mapping(MySomething:int(1..1)) my_set_of_stuff = ([]);

    // Code to dig up a set of MySomething's that I want to do
    // something with.
    ...
    foreach (....)
      foreach (....) {
        ....
        if (!my_set_of_stuff[x]) {
          ...
          my_set_of_stuff[x] = 1;
        }
      }
    ...

    // Now I can iterate over the set of MySomething's.
    foreach (my_set_of_stuff; MySomething x;)
      werror ("%O\n", x);