1 Oct
2008
1 Oct
'08
3:09 p.m.
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