3 ms·
And once you relalize that they are really hashes you also realize that a fast and memory efficient representation will use at least nine machine words or 72 by
by fhars 15y ago
And once you relalize that they are really hashes you also realize that a fast and memory efficient representation will use at least nine machine words or 72 bytes per value: 1 + x for the pointer in the bucket array (you don't want 100% occupancy to avoid hash collisions), 2 for the cons cell of the list stored in the bucket (the second element of which will usually be NULL if you have a good hash function and low occupancy), 2 for the key-value pair pointed to by the first element of the cons cell representing the index and the value, and two each for the integer key and value plus their tag words). And you may also want to store some metadata (like the length of the list stored in each bucket) with the hash, so the PHP array in the example is within a factor of two from the naive optimum for a dynamically typed language without specialized arrays.
Its just the price you have to pay for not caring about the type of your "array" keys.
- obtu 15y agoThat or specialize. Lua, Javascript, and PyPy all have more efficient storage of integer-keyed hashes. Lua's solution is particularly simple and could easily be transferred to PHP.
- lysium 15y agoIn PHP you can mix the types of the key, so that won't work.
- lysium 15y agoIn another thread, dchest points out http://news.ycombinator.com/item?id=3360369 http://news.ycombinator.com/item?id=3360369 that Lua 5.0 allows mixed-typed keys, too, so that may work.
- obtu 15y agoYes. You can specialise the implementation without breaking semantics. Lua, PyPy, and some Javascript VMs are examples of that.
- deleted 15y ago[deleted]
- deleted 15y ago[deleted]
- wotnarg 15y agoYou can mix types and specialize; HipHop does. The key is that the implementation needs to be able to switch array types on the fly and convert itself. In the common case, using a specialized array will be big wins in space and time, and in the uncommon case, it can revert to a generic version.