Повышение эффективности алгоритма

Прежде всего, я хотел бы извиниться, если этот вопрос был задан. Трудно найти ответ, не найдя, как создавать массивы хэшей и хэши массивов....

Я создаю анализатор логов. Каждая запись об ошибке находится в форме

timestamp # # human_timestamp errno #

я создал хэш хэшей, используя функцию сопоставления, чтобы сделать следующее:

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

Позже я проведу некоторый анализ, где я хотел бы изолировать записи между номерами строк. Записи анализа также хранятся в хэшах...

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

$analysis{errors} будет ссылкой на массив. Он заполняется следующим образом.

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;
}

Мои файлы журналов нередко содержат более 30000 записей. Анализ выполняется довольно быстро, за исключением создания массива ошибок. Есть ли более эффективный способ создания этого массива?

Спасибо


perl perl-data-structures
person trialUnplugged    schedule 23.09.2011    source источник
comment
Всякий раз, когда вы обнаружите, что говорите что-то вроде $hash{++$counter} = ..., спросите себя, не будет ли более уместно использовать массив ($array[++$counter] = ...).   -  person mob    schedule 23.09.2011
comment
Конечно, это делает больше с тех пор. Хэш-ключи изначально не были числовыми и последовательными. Ускорит ли изменение этого массива время выполнения алгоритма?   -  person trialUnplugged    schedule 23.09.2011

Ответы (2)


arrow_upward
6
arrow_downward

Всякий раз, когда вы обнаружите, что говорите что-то вроде $hash{++$counter} = ..., спросите себя, не будет ли более уместно использовать массив ($array[++$counter] = ...).

Для извлечения хеш-элемента $hash{$key} требуется, чтобы Perl передал ключ через хеш-функцию и прошел по связанному списку, выполнив одно или несколько сравнений строк, чтобы найти значение. Также может потребоваться некоторое усилие, чтобы упорядочить ключ.

Поиск элемента массива выполняется намного быстрее. Perl, возможно, потребуется преобразовать индекс в число, но оттуда легко найти ячейку памяти, содержащую значение массива.

person mob    schedule 23.09.2011
comment
Спасибо... Я должен был знать лучше. :) - person trialUnplugged; 23.09.2011

arrow_upward
2
arrow_downward

Вы спрашиваете о микрооптимизациях. Иногда это трудно предсказать, поэтому ключевым моментом является бенчмаркинг.

Хэши — это массивы связанных списков. Они по своей сути будут медленнее, чем использование массива, поэтому

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

немного медленнее, чем

push @$logRef, ...;

Преобразование в массивы и выполнение некоторых других микрооптимизаций оставляет вам:

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

или, может быть, даже

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

Потому что

  • grep EXPR, и map EXPR, быстрее, чем grep BLOCK и map BLOCK.
  • При прочих равных чем меньше операций, тем быстрее, поэтому ненужные операции отсеиваются.
person ikegami    schedule 23.09.2011