Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl: the Markov chain saw
 
PerlMonks  

Efficient access to sparse lists?

by Improv (Pilgrim)
on Jan 25, 2001 at 16:16 UTC ( [id://54251]=perlquestion: print w/replies, xml ) Need Help??

Improv has asked for the wisdom of the Perl Monks concerning the following question:

Is there an efficient way to shift a list and be guaranteed to shift past undef'd list members? I need the numbered insertions to keep track of events in a turn-based system, and need to keep the list constantly shrinking so passed events don't keep on taking memory, but the list will be mostly empty, with probably about 5% of the members being full. I want to avoid the need to pass by all the members that are not defined for speed reasons.

Replies are listed 'Best First'.
Re: Efficient access to sparse lists?
by mwp (Hermit) on Jan 25, 2001 at 16:47 UTC
    There are a couple options. You need to know the index, so foreach is out. You could do something like this:
    for(my $x = 0; $x <= $#array; $x++) { next unless $array[$x]; # do stuff with $x and $array[$x] }

    But that is obviously inefficient, especially if your list is VERY sparse. Like with elements numbered 100, 435, 1040, etc.

    Why not use a hash? You can convert a sparse list to a hash like so:

    my %hash = map { $x => $y } grep { my $y = $list[$x]; $y ne $undef; [$x, $y] } for(my $x = 0; $x <= $#list; $x++);

    And use it like this:

    $list{100} = 'dog'; $list{435} = 'cat'; $list{1040} = 'tax form'; while(($index, $element) = each %list) { # do stuff with $index and $element }

    Other alternatives include using a pseudohash, or writing a tied array implementation that acts like a list in your code but works like a hash behind the scenes.

    Good luck!
      Instead of the map/grep/for mess I gave you, try something like this to convert a sparse list to a hash:
      my %hash = (); for(my $x = 0; $x <= $#sparse_list; $x++) { my $y = $spase_list[$x]; next if $y eq undef; $hash{$x} = $y; }

      As an aside, you can use exists and delete on array elements but it comes highly discouraged. So don't do it.

      Apologies for the typos...
        The problem is that I need fast *ordered* access, something that a hash really won't help me with.

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: perlquestion [id://54251]
Approved by root
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others wandering the Monastery: (5)
As of 2024-04-23 15:11 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found