Help us understand the problem. What is going on with this article?

竹内関数をメモ化で高速化する (物事のやり方は一つではない -- Perl)

はじめに

Perl で竹内関数をメモ化によって、高速にしようとあれこれやります。

竹内関数とは

これです。Perl で書くとこんな感じです。

tarai.pl
sub tarai
{
    my ($x, $y, $z) = @_;
    return $y if $x <= $y;
    tarai(  tarai($x-1, $y, $z),
            tarai($y-1, $z, $x),
            tarai($z-1, $x, $y));
}

簡単な補足

奥村晴彦『C言語による最新アルゴリズム事典』技術評論社では、たらいまわし関数に特に用途はない、と説明されています。
ここでは、プログラムのベンチマークとして利用します。

ベンチマーク測定

少々心苦しいのですが、AtCoder:競技プログラミングコンテストを開催する国内最大のサイト の Language Test 202001 コードテストを使用いたします。
実行時間に加え、メモリの使用量がわかります。

素朴な実装

memo00.pl
use strict;
use warnings;

sub tarai
{
    my ($x, $y, $z) = @_;
    return $y if $x <= $y;
    tarai(  tarai($x-1, $y, $z),
            tarai($y-1, $z, $x),
            tarai($z-1, $x, $y));
}
print tarai(12, 6, 0), "\n";
Perl(v5.18.2) Perl(v5.26.1)
実行時間 3523 ms 2342 ms
メモリ 300052 KB 980 KB

おっ、新しいテスト環境は速くなってる。

メモ化

memo01.pl
use strict;
use warnings;
use Memoize;

sub tarai
{
    my ($x, $y, $z) = @_;
    return $y if $x <= $y;
    tarai(  tarai($x-1, $y, $z),
            tarai($y-1, $z, $x),
            tarai($z-1, $x, $y));
}
memoize('tarai');

print tarai(12, 6, 0), "\n";
Perl(v5.26.1)
実行時間 89 ms
メモリ 2164 KB

メモ化、凄っ。
memoizeって追記しただけなのに。
凄すぎて、パラメータを増やさざるを得ない。

print tarai(100, 50, 0), "\n";
Perl(v5.26.1)
実行時間 158 ms
メモリ 7220 KB

クロージャによる遅延評価

memo03.pl
use strict;
use warnings;

sub tarai
{
    my ($x, $y, $z) = @_;
    return $y if $x <= $y;
    my $zz = $z->();
    tarai(  tarai($x-1, $y, sub { $zz }),
            tarai($y-1, $zz, sub { $x }),
            sub { tarai($zz-1, $x, sub { $y }); });
}
print tarai(100, 50, sub { 0 }), "\n";
Perl(v5.26.1)
実行時間 78 ms
メモリ 908 KB

さらに速い。
メモリ使用量も少ない。

Ruby クロージャによる遅延評価

memo.rb
def tarai(x, y, z)
  return y if x <= y
  zz = z.call
  tarai(  tarai(x - 1, y, z),
          tarai(y - 1, zz, proc { x }),
          proc { tarai(zz - 1, x, proc { y }) })
end

puts tarai(100, 50, proc {0})
Ruby(2.7.0)
実行時間 126 ms
メモリ 9140 KB

オブジェクト指向はメモリ食うよね 適当

まとめ

  • メモ化や遅延評価は、思いの外高速化される
  • Lisp 恐るべし
  • 奥村さんはたらいまわし関数に興味がない

参照したサイト
竹内関数をメモ化で高速化する工程 (Python には負けたくない)
お気楽 Perl プログラミング超入門::メモ化と遅延評価
お気楽 Ruby プログラミング入門.番外編 遅延評価と遅延ストリーム

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした