-----Oorspronkelijk bericht-----
Van: Martin Stjernholm [mailto:<mast[at]lysator.liu.se>]
Verzonden: Tuesday, September 08, 2009 5:26 PM
Aan: Arjan van Staalduijnen
CC: Henrik Grubbström; Pike mailinglist
Onderwerp: Re: Arrays, multisets, mappings: avoiding unnecessary memory
(re)assigns
"Arjan van Staalduijnen" <<Arjan.van.Staalduijnen[at]rtl.nl>> wrote:
> > Hopefully properly answering one of my own questions:
=== snip ===
> > 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.
After some internal off-list discussion, and without knowledge about the
low-level algorithms, we figured multiset had to be the faster of the two for
the exact purpose you're describing. Now we can learn the assumption was wrong,
and I can go review some of my code so it will become faster. :-)
> A multiset is a binary tree which has O(log(<size>)) for lookups.
In some if-statements I rewrote some or-statements to something like:
if ( (< "a", "b", "c" >)[ val ] ) {}
instead of:
if ( val == "a" || val == "b" || val == "c" ) {}
because, apart from being shorter, I assumed it would be more efficient. Wrong
again, or is the multiset way the most-efficient way here?
Regards,
Arjan
|