in reply to Data structure challenge

There is an out-by-one error in the logic somewhere that I cannot find right now, but otherwise, I think this complies with the rules of the challenge.

#! perl -slw
use strict;
local $, = ' ';

my( $A, $C, @B ) = ( undef, 0 );
open SPARSE, '+> :raw', \$A;

sub readA{  
    seek SPARSE, 4 * $_[ 0 ], 0; 
    sysread  SPARSE, my $n, 4; 
    unpack 'N', $n; 
}

sub writeA{ 
    seek SPARSE, 4 * $_[ 0 ], 0; 
    syswrite SPARSE, pack( 'N', $_[ 1 ] ), 4; 
} 

sub query{
    my $i = shift;
    my $a = readA( $i ) || -1;
    return 0 unless 0 <= $a and $a < $C;
    my $b = $B[ $a ];
    return $b == $i ? 1 : 0;
}

sub insert{
    my $i = shift;
    if( !query( $i ) ) {
        $B[ $C ] = $i;
        writeA( $i, $C );
        $C++
    }
}

sub del{
    my $i = shift;
    if( query( $i ) ) {
        my $a = readA( $i );
        my $b = $B[ --$C ];
        $B[ $a ] = $b;
        writeA( $b, $a );
    }
}

sub clear{
    $C = 0;
}

my @numbers = map{ int rand( 2**16 ) } 1 .. 10;
   
print 'Query before insert';
printf "%5d : %s\n", $_, query( $_ ) for @numbers;

insert $_ for @numbers;

print "\nQuery after insert";
printf "%5d : %s\n", $_, query( $_ ) for @numbers;

del $_ for @numbers[ 0..4 ]; ## Delete half

print "\nQuery after deleting half";
printf "%5d : %s\n", $_, query( $_ ) for @numbers;

del $_ for @numbers; ## Delete them all regardless if they still exist
+s

print "\nQuery after deleting the rest";
printf "%5d : %s\n", $_, query( $_ ) for @numbers;

[download]
Examine what is said, not who speaks.
"Efficiency is intelligent laziness." -David Dunham
"Think for yourself!" - Abigail

Replies are listed 'Best First'.
Re: Re: Data structure challenge
by ambrus (Abbot) on Mar 18, 2004 at 15:57 UTC

    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.)

[reply]

      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) || ..

      [download]

      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.

      Examine what is said, not who speaks.
      "Efficiency is intelligent laziness." -David Dunham
      "Think for yourself!" - Abigail
[reply]
[d/l]
[select]

        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.

        Warning: Unless otherwise stated, code is untested. Do not use without understanding. Code is posted in the hopes it is useful, but without warranty. All copyrights are relinquished into the public domain unless otherwise stated. I am not an angel. I am capable of error, and err on a fairly regular basis. If I made a mistake, please let me know (such as by replying to this node).

[reply]

In Section Meditations