Graham Fawcett ha scritto:
[...]
Never though about sparse array, what is the advantage?
For the complexity, the same of a good hash map.
Almost certainly worse complexity than a hash map; but the overhead
could be much smaller. If (for example) you only needed a small number
of key/value pairs (say, hundreds of thousands), you could implement
your "database" trivially, e.g. a NULL-terminated array of key/value
structs in shared memory. (Though having separate arrays for keys and
values might help cache locality and boost performance). Lookup might
be O(n) but with a small-ish N and with such a low overhead, it could
perform very, very well.
This seems an interesting idea, thanks.
Manlio Perillo
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
