APM: Sparse arrays

Mike South msouth at shodor.org
Thu Jul 10 09:30:30 CDT 2003


>From: "Brian Michalk" <michalk at awpi.com>
>To: <austin-pm at pm.org>
>Date: Thu, 10 Jul 2003 08:00:44 -0500
>
>Let's say I have a sparse array:
>$ary[100]=1;
>$ary[100000]=2;
>$ary[1000000]=3;

How is that array being created?  If you just keep track of where
the occupied indices are in another array, you can iterate over
that. 

>
>Now, I want to iterate over the array, either from lowest to highest array
>index, and still retain the index of the element returned.  How do I do
>that?
>
>foreach $elt (@ary) {
>	$some_value = $elt;
>	$the_index = ????????;			# how do I get this information?
>}
>
>
>This algorithm is chewing up CPU time, causing the process to take days to
>complete... the dataset is several gigabytes large.
>

#!/usr/bin/perl -w
use strict;

my @occupied_index = ();
my @data = ();
&add_element(100,1);
&add_element(100000,1);
&add_element(1000000000000,1);

foreach my $index (@occupied_index) {
    print "the element at $index is $data[$index]\n";
}

 
 sub add_element {
    my ($index, $element) = @_;

    push @occupied_index, $index; # you may need to be fancier 
                                  # here if you are trying to keep 
                                  # these in numerical order

    $data[$index] = $element;
}

__END__


mike



More information about the Austin mailing list