Re: Data structure challenge

[BrowserUk]

Something like this?

Update: Out by one error corrected.

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

my( $A, $B, $C ) = ( '', '', 0 );

sub query{ 
    my $i = shift;
    my $a = vec $A, $i, 32;
    my $b = vec $B, $a, 32;
    return (0 <= $a and $a < $C and $b == $i ) ? 1 : 0;
}

sub insert{
    my $i = shift;
    if( !query( $i ) ) {
        vec( $B, $C, 32 ) = $i;
        vec( $A, $i, 32 ) = $C;
        $C++
    }
}

sub del{
    my $i = shift;
    if( query( $i ) ) {
        my $a = vec( $A, $i, 32 );
        my $b = vec( $B, --$C, 32 );
        vec( $B, $a, 32 ) = $b;
        vec( $A, $b, 32 ) = $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;
__END__
P:\test>337432
Query before insert
22456 : 0
11958 : 0
15260 : 0
34466 : 0
23110 : 0
 9114 : 0
21434 : 0
37988 : 0
32562 : 0
55488 : 0

Query after insert
22456 : 1
11958 : 1
15260 : 1
34466 : 1
23110 : 1
 9114 : 1
21434 : 1
37988 : 1
32562 : 1
55488 : 1

Query after deleting half
22456 : 0
11958 : 0
15260 : 0
34466 : 0
23110 : 0
 9114 : 0
21434 : 1
37988 : 1
32562 : 1
55488 : 1

Query after deleting the rest
22456 : 0
11958 : 0
15260 : 0
34466 : 0
23110 : 0
 9114 : 0
21434 : 0
37988 : 0
32562 : 0
55488 : 0

[tye]

If amortizing the initialization cost over the lifetime of the structure were allowed, then simple Perl arrays could be used (by not preallocating the size of the array so that the initial creation is still O(1)). Your use of strings 'suffer' from this same 'problem'. So I'm pretty sure Abigail would reject this solution.

Your solution would qualify if you could preallocate the length of the string w/o Perl initializing the contents of the string. This is pretty trivial to do in XS, hence the disqualification of that method.

[dpuu]

I'm not allowed to amortize the initialization over the life of the structure: but what about over the life of the program: is it valid (in the context of this challenge) big array (vec, whatever) at time zero and then manage it using my own allocator?

[sleepingsquirrel]

As long as we're only talking big-O notation, I think that that O(n) initialization is a wash. Inserting n items at O(1) is O(n). And O(n) (for initialization) + O(n) (for n insertions) = O(n).

[Abigail-II]

Just as tye says, the problem is in the initialization. If you assign a value in a vec() string, and it's "out of bounds", perl will zero all the in between values.

That means, that if you were to store just one value, say U - 1, that insertion will cost you Θ (U) time. Which isn't O (1).

Abigail

[BrowserUk]

I thought it was too easy.

So the whole challenge comes down to is there any way to allocate/extend a piece of memory without initialising it, using pure perl?