in reply to Re: A Not so Simple Append
in thread A Not so Simple Append

while (<DATA>) { 
        my ($one, $two) = split; 
        $seen{$one} = [$two, exists $seen{$one} ? @{$seen{$one}} : () 
+]; 
}

[download]
You should rely on autovivification rather than recreating the array each time. For example, the easy form of what you wrote is: 
while (<DATA>) {
  my ($one, $two) = split;
  push @{$seen{$one}}, $two;
}

[download]
If you insist on having the new elements at the beginning, change push to unshift, slightly less efficient.

-- Randal L. Schwartz, Perl hacker

Replies are listed 'Best First'.
RE (tilly) 3 (less?): A Not so Simple Append
by tilly (Archbishop) on Oct 03, 2000 at 04:51 UTC
    Conceptually push and unshift are exactly symmetrical, along with pop and shift. Is there really a performance difference?

    I tried it and wow: 

    use strict;
use Benchmark;
use vars qw(%test);

%test = (
  push => sub {
    my @tmp;
    push @tmp, "bar" foreach 1..10000;
  },
  unshift => sub {
    my @tmp;
    unshift @tmp, "bar" foreach 1..10000;
  },
);

timethese (-5, \%test);

__END__
Benchmark: running push, unshift, each for at least 5 CPU seconds...
      push:  5 wallclock secs ( 5.46 usr +  0.05 sys =  5.51 CPU) @ 17
+.42/s (n=96)
   unshift:  8 wallclock secs ( 8.08 usr +  0.11 sys =  8.19 CPU) @  0
+.73/s (n=6)

    [download]
    Why is the one so much faster than the other?
[reply]
[d/l]

      benefits of the array structure... you just make a new scalar and add a pointer to the end of the array with push. With unshift, you make a scalar, copy every pointer in the array over one, and stick the new pointer at the beginning.

      PerlGuts Illustrated may help you see that. See Arrays.

      --
      $you = new YOU;
      honk() if $you->love(perl)

[reply]
        I know all that.

        I just had not realized that they place the array right at the beginning of the space allocated. I guess I shouldn't be surprised, after all that is the same algorithmic mistake they made on map.

        Look at the following: 

        use strict;
use Benchmark;
use vars qw(%hash %test);

%test = (
  shift => sub {
    my @tmp = map "foo", 1..10000;
    foreach (@tmp) {
      my $val = shift @tmp;
      unshift @tmp, $val;
    }
  },
  pop => sub {
    my @tmp = map "foo", 1..10000;
    foreach (@tmp) {
      my $val = pop @tmp;
      push @tmp, $val;
    }
  },
);

timethese (-5, \%test);

__END__
Benchmark: running pop, shift, each for at least 5 CPU seconds...
       pop:  7 wallclock secs ( 6.60 usr +  0.00 sys =  6.60 CPU) @  6
+.67/s (n=44)
     shift:  7 wallclock secs ( 6.27 usr +  0.00 sys =  6.27 CPU) @  6
+.70/s (n=42)

        [download]
        When you have the space available, unshift is not appreciably slower. Just place the new array 1/16 of the way off from whichever way it is being moved. The memory wastage is insignificant, push is also pretty much the same speed, and unshift will become fast.

        *sigh*

[reply]
[d/l]
RE: RE: Re: A Not so Simple Append
by clemburg (Curate) on Oct 03, 2000 at 12:18 UTC

    Thanks for pointing this out! I did not know that this is possible - all the documentation about autovivification mentions it in the context of "chain" dereferencing, so I thought (or rather, "feeled") that it was connected to this operation exclusively. Is there any statement in the docs or the source somewhere that defines when autovivification will happen?

    Christian Lemburg
    Brainbench MVP for Perl
    http://www.brainbench.com

[reply]
      It's pretty simple. I don't know how it's documented, since I learned it mostly by folklore (and by watching the response to bug reports on P5P {grin}).

      When a variable containing undef (or a new element of an array or hash) is used in an "lvalue-context" (on the left side of an assignment, for example) as a reference, a reference to the appropriate anonymous thingy is inserted and the operation continued, rather than throwing an error for an attempt to dereference undef.

      So, push @$x, 35 works even if $x is undef, because we're about to dereference $x while trying to store something.

      It's really just an extension of the principle that 

      $last_name{"fred"} = "flintstone";

      [download]
      works, even though I didn't originally create the element with that key.

      -- Randal L. Schwartz, Perl hacker

[reply]
[d/l]

        Thanks for saving me the hours to watch the p5p list ... and for the crisp explanation!

        Christian Lemburg
        Brainbench MVP for Perl
        http://www.brainbench.com

[reply]
      merlyn and I disagree on whether it is documented.

      Look at perlref, item 6 on how to create a reference is to dereference them in a context that assumes they exist. That is why chained lookups autovivify, to continue down the chain the previous lookups were dereferenced in a context that assumed they existed. Likewise if you start assigning to stuff, it autovivifies. That holds for hashes and variables.

      Now merlyn certainly knows this piece of documentation, so why do we disagree on whether it is documented? Well to his eyes this requires serious "reading between the lines" and you cannot expect people to figure it out. To mine, well the reader's attention is not drawn to the point, but once I saw that this is the rule that applies, I have not since run into an autovivification situation which I had trouble understanding...

[reply]
[reply]

In Section Seekers of Perl Wisdom