Item — HN Reader

>In particular, I thought of the case of searching arrays of strings. If you are doing repeated searches against the same array, you can easily build a table breaking the array down into subarrays all sharing the same first character. (I'm assuming ASCII there!) Using that can quickly eliminate 5 or so comparisons that would be required with a naive binary search.

depending on the extent of your "fan-out" your memory budget might explode...

1 comments

ASCII can be stored in a byte, so at most he is going to use

256*(index+length).

Assuming he doesn't have more than 2^64 byte of data, he will only need 24576 bytes to the index, and only 32768 if he needs a 64 bit, rather than a 32 bit length.

You might even not need the length argument as it is only the next array index subtracted from the current. In that case you need only 16384 bytes.

If you want two bit unicode, you have to use 49152, 65536 and 32768 bytes, respectively.

Remember he only wanted to index the first value.