Повышение эффективности алгоритма - PullRequest
Новая
       6

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

4 голосов
/ 23 сентября 2011

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

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

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 записей.Анализ выполняется довольно быстро, за исключением создания массива ошибок.Есть ли более эффективный способ создания этого массива?

Спасибо

Ответы [ 2 ]

6 голосов
/ 23 сентября 2011

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

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

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

2 голосов
/ 23 сентября 2011

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

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

$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.
  • Когда все остальные вещи равны, меньшее количество операций происходит быстрее, поэтому это отсекает ненужные операции.
...