On 6/28/12 5:58 AM, Roman D. Boiko wrote:
Pedantically speaking, it is possible to index a string with about 50-51% memory overhead to get random access in 0(1) time. Best-performing algorithms can do random access in about 35-50 nanoseconds per operation for strings up to tens of megabytes. For bigger strings (tested up to 1GB) or when some other memory-intensive calculations are performed simultaneously, random access takes up to 200 nanoseconds due to memory-access resolution process.
Pedantically speaking, sheer timings say nothing without the appropriate baselines.
Andrei
