Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
0
Help us understand the problem. What is going on with this article?
@superrino130

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

More than 1 year has passed since last update.

はじめに

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 プログラミング入門.番外編 遅延評価と遅延ストリーム

0
Help us understand the problem. What is going on with this article?
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
superrino130
百折不撓 やり方は何通りでもある プログラミングを楽しもう

Comments

No comments
Sign up for free and join this conversation.
Sign Up
If you already have a Qiita account Login
0
Help us understand the problem. What is going on with this article?