Re^3: Perl Drag Racing - sum/delta list

You are right, I didn't do the math on paper originally, and due to false laziness, lack of an existing encode() or motivation to write one made me not verify my code with different data, even though I knew that might come back and bite me in the tender parts.

I fixed the code; this time, no comments, since I don't know how to explain it briefly. I guess it warrants a longer comment in front of the subroutine containing the math.

sub decode3 {
    my ($diff, $delta, $next);
    $diff = $_[0];
    $delta = -$_[0];
    $diff -= $delta += $_ for @_;
    $_[0] = $diff/@_;
    return map { $next += $_ } @_;
}
[download]

Your tests verify this one, and the benchmark on my 5.6.1 says it is consistently about 42% faster than the for version and 35% faster than the map one. The main win was removing the intermediary @results. If I put that step back in, it only beats the vanilla versions by 12% and 8%, respectively, which means you can speed up your own versions by 25% if you omit the temporary array.

The rest of the speed difference is mainly because I avoid a couple off-by-one corrections by not shifting off the total. It is debatable whether the loss of clarity (or the requirement for comments..) is worth the speed gains. Some profiling would be in order to determine the impact of decode()'s speed on overall program perforamce.

Makeshifts last the longest.

Comment on Re^3: Perl Drag Racing - sum/delta list Download Code

Replies are listed 'Best First'.
Re^4: Perl Drag Racing - sum/delta list by John M. Dlugosz (Monsignor) on Aug 19, 2002 at 19:02 UTC
I think it's avoiding those "off by one" corrections that helps. Because of the interpretive nature, ($x+1) has a certain amount of overhead, compared to the machine INCrement instruction of a register. But "big" instructions like map and foreach have spread the overhead over a lot of work, so it is not noticable. I conjecture that map is good because it knows that the output list will be the same size as the input list, and can set things up properly ahead of time, as opposed to push'ing each element as a separate instruction Very clever how you initialize $delta to avoid the shift and "+1" corrections. Many thanks for illustrating your techniques. —John	[reply]
Re^5: Perl Drag Racing - sum/delta list by Aristotle (Chancellor) on Aug 19, 2002 at 23:36 UTC
Actually, `map` doesn't know that. You can write something like `@x = map { () } @y;` and then the resulting list is empty. You can also do something like `@x = map { ($_, func($_)) } @y;` in which case it's twice as large as the input list. Or something like `@x = map { split } @y;` in which case it's entirely up in the air how many elements the result list will have. If you do `@x = map /re(g)(ex)/, @y;`, input strings that don't match the regex will leave no trace in the output list, while those that do produce two entries each. And if you add a `/g` to the regex, even the latter constant becomes random. I have no idea of the perl guts, but my guess is that it's because in a `for` loop, the array modification is an explicit operation. It's an independent op which needs to deduce the address to a scalar inside the array, and so it does so for each iteration, over and over. The `map` on the other hand creates a list implicitly and knows to keep track of where to dump the next value(s). Anyway, that's just an educated guess. If anyone who knows better can offer some enlightenment, I'll be glad to learn more. Makeshifts last the longest.	[reply] [d/l] [select]