В Perl цикл while обычно быстрее цикла for?

Question

Я провел небольшой эксперимент, как будет показано ниже, и похоже, что цикл while быстрее, чем цикл for в Perl. Но так как эксперимент был довольно грубым, и предмет мог быть намного сложнее, чем кажется, я хотел бы услышать, что вы скажете по этому поводу. Спасибо как всегда за любые комментарии / предложения:)

В следующих двух небольших скриптах я пробовал циклы while и for отдельно вычислять факториал 100 000. Тот, у которого есть цикл while, занял 57 минут 17 секунд, в то время как эквивалент цикла for занял 1 час 7 минут 54 секунды.

Скрипт с циклом while:

use strict;
use warnings;
use bigint;

my $now = time;

my $n = shift;
my $s = 1;

while(1){
$s *= $n;
$n--;
last if $n==2;
}

print $s*$n;
$now = time - $now;
printf("\n\nTotal running time: %02d:%02d:%02d\n\n", int($now / 3600),
            int(($now % 3600) / 60), int($now % 60));

Скрипт для цикла:

use strict;
use warnings;
use bigint;

my $now = time;

my $n =shift;
my $s=1;

for (my $i=2; $i<=$n;$i++) {
$s = $s*$i;
}

print $s;
$now = time - $now;
printf("\n\nTotal running time: %02d:%02d:%02d\n\n", int($now / 3600),
            int(($now % 3600) / 60), int($now % 60));

Answer 1

Циклы не эквивалентны, и вы в основном разбиваете пакет bigint, и он не имеет ничего общего с for против while как таковым.

Цикл while использует нотацию $s *= $i, но цикл for использует $s = $s * $i. Достаточно просто показать, что они не идентичны. Также считается один цикл; другой отсчитывает. Это влияет на то, насколько большие числа будут умножены. Это эффект второго порядка, но не совсем незначительный.

[ Обновление: пересмотрено, чтобы показать только одну версию кода с временными интервалами менее секунды. Есть основания полагать, что печать должна быть исключена из сроков расчетов; это все усложняет, так что я не беспокоюсь. Я исправил ошибку в предыдущей версии: цикл 4 был таким же, как цикл 3 - теперь это не так. Я также настроил форматирование вывода (хотя обработка за секунду может быть улучшена - упражнение для читателя), и есть более качественная «отчетность о ходе работы». ]

Результаты синхронизации на Mac Mini (Snow Leopard 10.6.2) были следующими:

Count up   $s *= $i:      00:00:12.663337
Count up   $s  = $s * $i: 00:00:20.686111
Count down $s *= $i:      00:00:14.201797
Count down $s  = $s * $i: 00:00:23.269874

Сценарий:

use Time::HiRes qw(gettimeofday);
use strict;
use warnings;
use bigint;
use constant factorial_of => 13000;

sub delta_t
{
    my($tag, $t1, $t2) = @_;
    my($d) = int($t2 - $t1);
    my($f) = ($t2 - $t1) - $d;
    my($s) = sprintf("%.6f", $f);
    $s =~ s/^0//;
    printf "%-25s %02d:%02d:%02d%s\n",
           $tag, int($d/3600), int(($d % 3600) / 60), int($d % 60), $s;
}

my $t1 = gettimeofday;

{
    my $n = factorial_of;
    my $s = 1;
    for (my $i = 2; $i <= $n; $i++)
    {
        $s *= $i;
    }
    print "$s\n: Loop 1\n";
}

my $t2 = gettimeofday;
delta_t('Count up   $s *= $i:',      $t1, $t2);

{
    my $n = factorial_of;
    my $s = 1;
    for (my $i = 2; $i <= $n; $i++)
    {
        $s = $s * $i;
    }
    print "$s\n: Loop 2\n";
}

my $t3 = gettimeofday;
delta_t('Count up   $s *= $i:',      $t1, $t2);
delta_t('Count up   $s  = $s * $i:', $t2, $t3);

{
    my $n = factorial_of;
    my $s = 1;
    for (my $i = $n; $i > 1; $i--)
    {
        $s *= $i;
    }
    print "$s\n: Loop 3\n";
}

my $t4 = gettimeofday;
delta_t('Count up   $s *= $i:',      $t1, $t2);
delta_t('Count up   $s  = $s * $i:', $t2, $t3);
delta_t('Count down $s *= $i:',      $t3, $t4);

{
    my $n = factorial_of;
    my $s = 1;
    for (my $i = $n; $i > 1; $i--)
    {
        $s = $s * $i;
    }
    print "$s\n: Loop 4\n";
}

my $t5 = gettimeofday;
delta_t('Count up   $s *= $i:',      $t1, $t2);
delta_t('Count up   $s  = $s * $i:', $t2, $t3);
delta_t('Count down $s *= $i:',      $t3, $t4);
delta_t('Count down $s  = $s * $i:', $t4, $t5);

---

А вот гораздо более компактная версия приведенного выше кода, расширенная для тестирования циклов while и for. Это также касается большинства вопросов времени. Единственное, что не идеально (для меня), это то, что он использует пару глобальных переменных, и я немного укоротил код в ссылках на код, чтобы он помещался на одной строке, не вызывая полосу прокрутки (на моем дисплее, в любом случае). ). Понятно, что, потратив немного больше времени, тестирование можно было бы поместить в массив, чтобы тестирование выполнялось итеративно - цикл по массиву, выполняющий функцию таймера для информации в массиве. И т.д ... это SMOP - простой вопрос программирования. (Он печатает хеш MD5 факториала, а не сам факториал, потому что легче сравнивать результаты и т. Д. Он действительно указал на пару ошибок, поскольку я рефакторинг кода выше. Да, MD5 не является безопасным - но я не использую это для безопасности, просто чтобы обнаружить непреднамеренные изменения.)

use Time::HiRes qw(gettimeofday);
use Digest::MD5 qw(md5_hex);
use strict;
use warnings;
use bigint;
use constant factorial_of => 13000;

my ($s, $i);

my $l1 = sub {my($n) = @_; for ($i = 2;  $i <= $n; $i++) { $s *= $i;     }};
my $l2 = sub {my($n) = @_; for ($i = 2;  $i <= $n; $i++) { $s = $s * $i; }};
my $l3 = sub {my($n) = @_; for ($i = $n; $i > 1;   $i--) { $s *= $i;     }};
my $l4 = sub {my($n) = @_; for ($i = $n; $i > 1;   $i--) { $s = $s * $i; }};
my $l5 = sub {my($n) = @_; $i = 2;  while ($i <= $n) { $s *= $i;     $i++; }};
my $l6 = sub {my($n) = @_; $i = 2;  while ($i <= $n) { $s = $s * $i; $i++; }};
my $l7 = sub {my($n) = @_; $i = $n; while ($i > 1)   { $s *= $i;     $i--; }};
my $l8 = sub {my($n) = @_; $i = $n; while ($i > 1)   { $s = $s * $i; $i--; }};

sub timer
{
    my($n, $code, $tag) = @_;
    my $t1 = gettimeofday;
    $s = 1;
    &$code(factorial_of);
    my $t2 = gettimeofday;
    my $md5 = md5_hex($s);
    printf "Loop %d: %-33s %09.6f (%s)\n", $n, $tag, $t2 - $t1, $md5;
}

my $count = 1;
timer($count++, $l1, 'for   - Count up   $s *= $i:');
timer($count++, $l2, 'for   - Count up   $s  = $s * $i:');
timer($count++, $l3, 'for   - Count down $s *= $i:');
timer($count++, $l4, 'for   - Count down $s  = $s * $i:');
timer($count++, $l5, 'while - Count up   $s *= $i:');
timer($count++, $l6, 'while - Count up   $s  = $s * $i:');
timer($count++, $l7, 'while - Count down $s *= $i:');
timer($count++, $l8, 'while - Count down $s  = $s * $i:');

Пример вывода (контрольная сумма MD5 сжата во избежание разрыва строки - полное значение 584b3ab832577fd1390970043efc0ec8):

Loop 1: for   - Count up   $s *= $i:      12.853630 (584b3ab8...3efc0ec8)
Loop 2: for   - Count up   $s  = $s * $i: 20.854735 (584b3ab8...3efc0ec8)
Loop 3: for   - Count down $s *= $i:      14.798155 (584b3ab8...3efc0ec8)
Loop 4: for   - Count down $s  = $s * $i: 23.699913 (584b3ab8...3efc0ec8)
Loop 5: while - Count up   $s *= $i:      12.972428 (584b3ab8...3efc0ec8)
Loop 6: while - Count up   $s  = $s * $i: 21.192956 (584b3ab8...3efc0ec8)
Loop 7: while - Count down $s *= $i:      14.555620 (584b3ab8...3efc0ec8)
Loop 8: while - Count down $s  = $s * $i: 23.790795 (584b3ab8...3efc0ec8)

Я постоянно вижу небольшой (<1%) штраф за цикл while над соответствующим циклом for, но у меня нет хорошего объяснения этому. </p>

Answer 2

Одним из ключей к сравнительному анализу является упрощение. Проблема заключается в скорости for против while. Но эксперимент включает в себя несколько ненужных сложностей.

• Два цикла не так похожи, как могли бы быть. Один использует $s *= $n, а другой - $s = $s * $i (как отмечает Джонатан Леффлер). Один использует $n--, а другой - $i++ (кто знает, различаются ли они по скорости?).

• Если нас интересует for против while, нет необходимости привлекать bigint. Это только смущает тему. В частности, ваш скрипт while зависит только от одного объекта bigint ($s), тогда как ваш скрипт for использует два из них ($s и $i). Меня не удивляет, что скрипт for работает медленнее.

Перепишите ваши циклы, чтобы они были как можно более похожими, оставьте факториалы достаточно маленькими, чтобы вам не приходилось использовать bigint, и используйте модуль Benchmark. Тогда вы можете провести честную прямую гонку for против while. Мне будет любопытно посмотреть, что вы найдете.

Answer 3

Я был бы шокирован, если бы была какая-то "реальная" разница между циклами while и for. Предполагая, что они делали «одну и ту же» вещь, интерпретатор должен оптимизировать их так, чтобы они были более или менее идентичны.

Держу пари, что разница, вероятно, была не чем иным, как другими процессами, которые по-разному боролись за ресурсы во время двух выполнений.

Даже если бы была разница, не попадайтесь в Печальная трагедия театра микрооптимизации .