Algorithm Efficiency Improvement

Question

First I would like to apologize if this question has been asked. It is difficult to search for the answer w/o finding how to create arrays of hashes and hashes of arrays....

I am creating a log analyzer. Each error entry is in the form

timestamp # # human_timestamp errno #

i have created a hash of hashes using a mapping function to do the following:

$logRef->{++$errCnt} =
{
    line       => $lineNum,
    timestamp  => $timestamp,
    humanStamp => $humanStamp,
    errno      => $errno,
    text       => ''
};

Later on i do some analysis where I would like to isolate the entries between line numbers. The analysis entries are stored in hashes as well...

$analysis{++$iteration} =
{
    result    => $result,
    startLine => $startLine,
    endLine   => $endLine,
    errors    => undef
};

$analysis{errors} is going to be an array reference. It is filled by doing the following.

foreach my $iteration ( keys %analysis )
{
    my @errKeys = grep { $logRef->{$_}{line} >= $analysis{$iteration}{startLine} &&
                         $logRef->{$_}{line} <= $analysis{$iteration}{endLine} }
                  keys %$logRef;

    my @errs = ();
    push @errs, $logRef->{$_}{errno} foreach ( @errKeys );

    $analysis{$iteration}{errors} = \@errs;
}

It is not uncommon for my log files to contain 30000+ entries. The analysis run fairly quickly, with the exception of creating the errs array. Is there a more efficient way of generating this array?

Thanks

Answer 1

Whenever you find yourself saying something like $hash{++$counter} = ..., ask yourself whether it would be more appropriate to use an array ($array[++$counter] = ...).

Retrieving a hash element $hash{$key} requires Perl to pass the key through a hash function and traverse a linked list, performing one or more string comparisons to find the value. It might also take some effort to stringify the key.

Looking up an array element is much faster. Perl may need to convert the index to a number, but it is straightforward to find the memory location holding the array value from there.

Answer 2

You're asking about micro-optimisations. Sometimes it's hard to predict, so Benchmarking is key.

---

Hashes are arrays of linked lists. They're inherently going to be slower than using an array, so

$logRef->{++$errCnt} = ...;

is a tiny bit slower than

push @$logRef, ...;

---

Converting to arrays and doing some other micro-optimisations leaves you with:

foreach my $analysis ( @analysis )
{
    $analysis->{errors} = [
       map $_->{errno},
         grep $_->{line} >= $analysis->{startLine}
             && $_->{line} <= $analysis->{endLine},
           @$logRef
    ];
}

or maybe even

foreach my $analysis ( @analysis )
{
    $analysis->{errors} = [
       map $_->{line} >= $analysis->{startLine}
           && $_->{line} <= $analysis->{endLine},
               ? $_->{errno}
               : (),
         @$logRef
    ];
}

Because

• grep EXPR, and map EXPR, are faster than grep BLOCK and map BLOCK.
• When all other things are equal, fewer ops is faster, so this cuts off unnecessary ops.