Re: Re: Data structure challenge

[ambrus]

Update: this is stupid, see BrowserUk's reply on why.

I would not think this is constant time. I know nothing about how spares files are implemented, but I would not think it is such that you can access any byte in constant time. (If the filesystem does not have sparse files, the situation is even worse, as the os must fill the file with zero bytes when seeking past end.)

[BrowserUk]

Okay. Forget the bareword SPARSE, it is just a filehandle, opened (R/W) to an in memory file per perlfunc:open (5.8.x):

File handles can be opened to ``in memory'' files held in Perl scalars via:

    open($fh, '>', \$variable) || ..

My inspiration was that if you seek on an in-memory file, the string is extended, without being initialised. Of course it isn't if it is going to emulate a file. If you seek to a position in a random access file you don't want everything preceding it to be overwritten.

So, a pure-perl way of allocating a buffer without initialisation.

[theorbtwo]

It all comes down to what you mean by "constant time", I think. On the one hand, the time taken to access an element is not always the same: accessing elements greater then the internal size of the string is slower then if it's not been prextended.

OTOH, it is still O(1) on the size of the pseudoarray.

[BrowserUk]

I agree completely. I seriously doubt the there is any advantage in terms of (real-time) performance of using either the scalar-as-packed-integer-array, or the uninitialised buffer as packed array over using a hash.

I've always had problems with big-O notation. In part this comes down to the fact that O is measured in some theoretical unit that is completely divorced from any real-time unit of measurement.

It's perfectly possible to have two algorithms to do the same task. One which is defined as being O(1) and the other as O(N) where the former is much slower in realtime than the latter. I think this is why I tend to confuse myself when accesing algorithms. My natural instinct is to conclude that the fastest realtime implementation should have a 'lower' bigO rating than a slower implementation, but that simple isn't the case. For example, a brute force combinatorial solution to a problem written in C or assembler can outstrip an 'intelligent' algorithm written in perl, even though the former rates as O(n*m) and the latter O(n or even O(log n).

Regardless, if my reinterpretation of Abigail's challenge--a pure perl way to allocate an uninitialised buffer--was correct, and he didn't correct me, then I think that perl 5.8.x's 'memory files' meet the challenge.