読者です 読者をやめる 読者になる 読者になる

初代Masteries

きっとモヒカンにもなれないお前たちに告げる!!!

続・Memoizeの話

簡単にメモ化を実現するMemoizeについては以前紹介しました. 今回はその話の続編... っぽい話です.

Project EulerのProblem 14で, Memoizeを使って実装していたんですが, @の兄から「Perlの実行速度遅すぎね?」とツッコミが入りました.

# C
0.05s user 0.00s system 98% cpu 0.057 total
# Perl
15.50s user 0.09s system 99% cpu 15.620 total

同じような実装をしている割には遅すぎる... ような気がします.
怪しいのはモジュール'Memoize'なので, とりあえずこのモジュールを使わないようにコードを書きなおしてみました.

use strict;
use warnings;
no warnings 'recursion';

my @memo;

sub sequence {
    my $n = shift;

    return $memo[$n] if defined $memo[$n];

    if ($n == 1) {
        return 1;
    } elsif ($n % 2 == 0) {
        return sequence($n/2) + 1;
    } else {
        return sequence(3*$n+1) + 1;
    }
}

my $i = 1;
my ($max, $max_length) = (0, 0);
while ($i < 1_000_000) {
    $memo[$i] = sequence($i);
    if ($memo[$i] > $max_length) {
        $max = $i;
        $max_length = $memo[$i];
    }
    $i++;
}

print "$max_length ($max)\n";

ちなみにPerlは, 関数の再帰が100回を越えると警告が出るらしいので, no warnings 'recursion'; で無効化しています*1.

さて, C言語と, Memoizeを使う/使わないPerlの3つで実行速度を比較してみましょう.

# C
0.05s user 0.00s system 98% cpu 0.057 total
# Perl (use Memoize)
15.50s user 0.09s system 99% cpu 15.620 total
# Perl (not use Memoize)
3.08s user 0.02s system 99% cpu 3.104 total

おお, だいぶ早くなりましたね!

Memoizeは簡単にメモ化を実現できますが, 場合によっては今回のように実行速度に対して(予想以上に)大きな負荷(?)を与える場合があるようです.
Memoizeを使うのは手抜き(?)したい時に留めておくのが良さそうですね*2.

付録: @の兄がC言語で書いたコード

#include <stdio.h>

#define N 1024

int memo[N * N];

int sequence (unsigned long n) {
	if (n < (N * N) && memo[n] != 0) return memo[n];

	if (n == 1) return 1;
	else if ((n % 2) == 0) return sequence(n / 2) + 1;
	else return sequence(3 * n + 1) + 1;
}

int main (int argc, char const *argv[]) {
	unsigned long i, n;
	int max = 0;

	for (i = 1; i < (1000 * 1000); ++i) {
		memo[i] = sequence(i);
		if (memo[i] > max) {n = i; max = memo[i];}
	}

	printf("%ld: %d\n", n, max);

	return 0;
}

*1:Memoizeを使えば自動的に無効になる... のかなあ.

*2:言うまでもない話ではありますが...