Re: Data structure challenge

[dragonchild]

What about using soft references? I used BrowserUk's harness and changed the engine around a little.

#!/usr/local/bin/perl -sl
use strict;
use warnings;

local $, = ' ';

{
    no strict 'refs';
    no warnings 'uninitialized';

    my $C = 0;

    sub query{
        my $i = shift;
        my $x = ${"a_$i"};
        return (0 <= $x and $x < $C and ${"b_$x"} == $i ) ? 1 : 0;
    }

    sub insert{
        my $i = shift;
        if( !query( $i ) ) {
            ${"b_$C"} = $i;
            ${"a_$i"} = $C;
            $C++
        }
    }

    sub del{
        my $i = shift;
        if( query( $i ) ) {
            $C--;
            my $x = ${"a_$i"};
            my $y = ${"b_$C"};
            ${"b_$x"} = $y;
            ${"a_$y"} = $x;
        }
    }

    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;

--------

Query before insert
56155 : 0
20459 : 0
15365 : 0
55048 : 0
47183 : 0
49635 : 0
32939 : 0
17320 : 0
54582 : 0
62554 : 0

Query after insert
56155 : 1
20459 : 1
15365 : 1
55048 : 1
47183 : 1
49635 : 1
32939 : 1
17320 : 1
54582 : 1
62554 : 1

Query after deleting half
56155 : 0
20459 : 0
15365 : 0
55048 : 0
47183 : 0
49635 : 1
32939 : 1
17320 : 1
54582 : 1
62554 : 1

Query after deleting the rest
56155 : 0
20459 : 0
15365 : 0
55048 : 0
47183 : 0
49635 : 0
32939 : 0
17320 : 0
54582 : 0
62554 : 0

Now, I think that doing this is cheating, a little, because I'm using the symbol table, which is a hash. But, I don't think this is possible in pure Perl, not with the constraints you've placed on it.

[BrowserUk]

I came up with something similar using a hash to emulate a sparse array

Read more... (2 kB)

But then realised that I might as well just use the hash to start with and save all the bother. Besides, the hash scalaes better. The overhead of allocating 4GB of ram in order to allocates 3 unique 32-bit integers (for example) is far higher than hashing those 3 integers.