[Haskell-cafe] pure Haskell database
Manlio Perillo
manlio_perillo at libero.it
Wed Oct 1 15:09:36 EDT 2008
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
More information about the Haskell-Cafe
mailing list