standard ranges

[Roman D. Boiko]

On Thursday, 28 June 2012 at 10:02:59 UTC, Roman D. Boiko wrote:
> On Thursday, 28 June 2012 at 09:58:02 UTC, 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.
>
> Just a remark, indexing would take O(N) operations and N/B 
> memory transfers where N = str.length and B is size of cache 
> buffer.

That being said, I would be against switching from string 
representation as arrays. Such switch would hardly help us solve 
any problems of practical importance better (by a significant 
degree) than they have to be solved with current design.

However, a struct could be created for indexing which I mentioned 
in two previous posts to give efficient random access for narrow 
strings (and arbitrary variable-length data stored consequently 
in arrays) without any significant overhead.

Respective algorithms are called Rank and Select, and there exist 
many variations of them (with different trade-offs, but some of 
them are arguably better than others).

I have investigated this question quite deeply in the last two 
weeks, because similar algorithms would be useful in my DCT 
project. If nobody else will implement them before me, I will 
eventually do that myself. It is just a matter of finding some 
free time, likely a week or two.