[Haskell-cafe] pure Haskell database

[Manlio Perillo]

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