SortedMap

[Nick Gerner]

I'm doing some sparse vector math using the hashmap implementations from hppc. So far it seems pretty good, but I'm wondering if sorted maps on are on the roadmap?

My loop deserialize several maps, merge them via some mechanism (e.g. multiply corresponding elements)

I've implemented that merge step by iterating over one of the maps and pulling corresponding elements from the other map. But if the maps were sorted that merge step would be a simple sorted merge step which I think would be non-trivially faster than the hash lookups.

This might also be smaller in memory than the hashtable approach. 

So how about KTypeVTypeSortedMap implementations?

[Dawid Weiss]

> I'm doing some sparse vector math using the hashmap implementations from
> hppc. So far it seems pretty good, but I'm wondering if sorted maps on are
> on the roadmap?

No, not really. I don't have any use of sorted maps (they're usually
implemented with trees) and this is a pet project to fulfill my
selfish needs :)

> I've implemented that merge step by iterating over one of the maps and
> pulling corresponding elements from the other map. But if the maps were
> sorted that merge step would be a simple sorted merge step which I think
> would be non-trivially faster than the hash lookups.

Merging via sorted data is the way to go, most likely. You could also
try some sort of bucketing if you know your data distribution but I'd
say merging will result in the simplest code. With HPPC you could sort
the key/value pairs for merging (destroying the original maps if you
care for memory). This may be faster or slower than bookkeeping
associated with building sorted maps directly. Again -- my mantra --
it depends on the data and your scenario.

> This might also be smaller in memory than the hashtable approach.

Don't know about that. It'd have to be some sort of heap-like
structure and then you need to rebalance etc. May be tricky. Check out
fastutil -- I think Sebastiano has sorted maps in there (and in a few
different flavors).

Dawid

[Nick Gerner]

No, not really. I don't have any use of sorted maps (they're usually 
implemented with trees) and this is a pet project to fulfill my
selfish needs :)

Fair enough. I'll check out fastutil some more.

 

Merging via sorted data is the way to go, most likely. You could also
try some sort of bucketing if you know your data distribution but I'd
say merging will result in the simplest code. With HPPC you could sort
the key/value pairs for merging (destroying the original maps if you
care for memory). This may be faster or slower than bookkeeping
associated with building sorted maps directly. Again -- my mantra --
it depends on the data and your scenario.

I'll give this a try. 

Don't know about that. It'd have to be some sort of heap-like
structure and then you need to rebalance etc. May be tricky. Check out
fastutil -- I think Sebastiano has sorted maps in there (and in a few
different flavors).

I was hoping the library author would figure that out :P 

Point taken. This was more just a thought anyway.

--Nick