計算結果を記憶する法〜オブジェクト・プロセス・プログラム・テーブル

仕事の Ruby と趣味の Elixir を反復横跳びしている e.mattsan です。

近ごろ仕事では Ruby 以外ばかり書いている気もしなくもないですが、それはそれとして。

Elixir は関数型言語に分類されるプログラミング言語なわけですが。関数型言語は変数が不変であるとか、ある関数に対して入力が同じならば出力も同じになる、などと一般的に言われていますが、そのようなプログラミング言語でも計算の途中経過を覚えておきたいときがあるわけです。いわゆるメモ化などがそれに当たります。

では値を変更できるオブジェクトなどを持たない言語はどのようなことができるだろうか、というのが今回のお話です。

ここではメモ化の例でよく使われるフィボナッチ数を例に、いろいろ実装して考えてみます。

オブジェクトで記憶する〜Ruby
- 記憶しない実装
- オブジェクトで記憶する
プロセスで記憶する〜Elixir
プログラムで記憶する〜Prolog
テーブルで記憶する〜SQL
まとめ

オブジェクトで記憶する〜Ruby

最初に比較対象として、オブジェクトで記憶する例を Ruby で実装してみます。

と、さらにその前に。計算結果を記憶しない愚直な実装を確認しておきます。

記憶しない実装

class FibNaive
  def get(n)
    case
    when n < 1
      raise "'#{n} is not a positive number."
    when n == 1
      1
    when n == 2
      1
    else
      get(n - 1) + get(n - 2)
    end
  end
end

fib_naive.rb という名前で保存して irb で確認してみます。

$ irb
irb(main):001:0> require_relative 'fib_naive'
=> true
irb(main):002:0> fib = FibNaive.new
=> #<FibNaive:0x0000000117758330>
irb(main):003:0> fib.get(1)
=> 1
irb(main):004:0> fib.get(2)
=> 1
irb(main):005:0> fib.get(3)
=> 2
irb(main):006:0> fib.get(10)
=> 55
irb(main):007:1> fib.get(40)
=> 102334155

実行する環境にもよりますが、40 くらいになると結果が返るまでに時間がかかることが感じられると思います。

オブジェクトで記憶する

シンプルに。インスタンス変数のハッシュを用意して、そこに計算結果を記録してゆきます。

class FibMemo
  def initialize
    @memo = {1 => 1, 2 => 1}
  end

  def get(n)
    case
    when n.negative?
      raise "'#{n} is a negative number."
    when f = @memo[n]
      f
    else
      @memo[n] = get(n - 1) + get(n - 2)
    end
  end
end

同様に fib_memo.rb という名前で保存して irb で確認します。

$ irb
irb(main):001:0> require_relative 'fib_memo'
=> true
irb(main):002:0> fib = FibMemo.new
=> #<FibMemo:0x000000010b405900 @memo={1=>1, 2=>1}>
irb(main):003:0> fib.get(1)
=> 1
irb(main):004:0> fib.get(2)
=> 1
irb(main):005:0> fib.get(3)
=> 2
irb(main):006:0> fib.get(10)
=> 55
irb(main):007:0> fib.get(40)
=> 102334155

前段の計算結果を再利用できるので、先ほどは応答に時間のかかっていた計算でもすぐに結果が返ることがわかると思います。

プロセスで記憶する〜Elixir

さて、Elixir です。今回も最初に愚直な実装を確認しておきます。

記憶しない実装

defmodule FibNaive do
  def get(n) when n < 1, do: raise "'#{n} is no a positive number."

  def get(1), do: 1

  def get(2), do: 1

  def get(n) do
    get(n - 1) + get(n - 2)
  end
end

fib_naive.ex という名前で保存して、Elixir のインタラクティブシェルである iex で確認してみます。

ソースコードをコンパイルして読み込むために、プロンプトから c "fib_naive.ex" を入力します。

$ iex
iex(1)> c "fib_naive.ex"
[FibNaive]
iex(2)> FibNaive.get(1)
1
iex(3)> FibNaive.get(2)
1
iex(4)> FibNaive.get(3)
2
iex(5)> FibNaive.get(10)
55
iex(6)> FibNaive.get(40)
102334155

これを踏まえて。 Elixir で記憶する方法を考えます。

自分のプロセスで記憶する

一番簡単な方法は、計算をしている主体が計算結果を持ち回り、次の計算の引数として受け渡す方法です。

関数は n の他に、それまでの計算結果を記録した memo を受け取ります。そして計算の結果として n に対応する数と、その数を算出するための計算結果を記録した新しいメモを組み（タプル）として返します。

defmodule FibMemo do
  def initialize do
    %{1 => 1, 2 => 1}
  end

  def get(_, n) when n < 1, do: raise "'#{n} is not a positive number."

  def get(memo, n) do
    case memo[n] do
      nil ->
        {f1, memo1} = get(memo, n - 1)
        {f2, memo2} = get(memo1, n - 2)
        f = f1 + f2
        {f, Map.put(memo2, n, f)}

      f ->
        {f, memo}
    end
  end
end

fib_memo.ex という名前で保存して iex で確認してみます。

まず初期化で最初の memo を取得します。 1 と 2 に対応する数が記憶されています。

$ iex
iex(1)> c "fib_memo.ex"
[FibMemo]
iex(2)> memo = FibMemo.initialize()
%{1 => 1, 2 => 1}
iex(3)> {f1, memo1} = FibMemo.get(memo, 1)
{1, %{1 => 1, 2 => 1}}

次に n と memo を渡すとn に対応する数と新しいメモのタプルが返ります。新しく取得したメモを次の関数の入力にすることで、それまで記憶した計算結果を利用することができます。

iex(4)> f1
1
iex(5)> {f2, memo2} = FibMemo.get(memo1, 2)
{1, %{1 => 1, 2 => 1}}
iex(6)> f2
1
iex(7)> {f3, memo3} = FibMemo.get(memo2, 3)
{2, %{1 => 1, 2 => 1, 3 => 2}}
iex(8)> f3
2
iex(9)> {f10, memo10} = FibMemo.get(memo3, 10)
{55,
 %{
   1 => 1,
   2 => 1,
   3 => 2,
   4 => 3,
   5 => 5,
   6 => 8,
   7 => 13,
   8 => 21,
   9 => 34,
   10 => 55
 }}
iex(10)> f10
55
iex(11)> {f40, memo40} = FibMemo.get(memo10, 40)
{102334155,
 %{
    ...(略)...
 }}
iex(12)> f40
102334155

この例では次の計算に値を渡すとき、いったん変数で受け取ってから次の計算に渡していますが、このようなときパイプ演算子 |> を使うと、途中の変数を使わずに前段の出力を次段の入力とすることができます。

パイプ演算子を使うと f(a, b) という記述を a |> f(b) と書き換えることができるので、たとえば g(f(a, b), c) という記述を a |> f(b) |> g(c) と記述することができるようになります。

本筋から離れますが、iex はパイプ演算子から記述すると直前の結果を入力として利用できるので、iex でも結果を確認することができます。

iex(1)> c "fib_memo.ex"
[FibMemo]
iex(2)> FibMemo.initialize()
%{1 => 1, 2 => 1}
iex(3)> |> FibMemo.get(1)
{1, %{1 => 1, 2 => 1}}
iex(4)> |> elem(1) |> FibMemo.get(2)
{1, %{1 => 1, 2 => 1}}
iex(5)> |> elem(1) |> FibMemo.get(3)
{2, %{1 => 1, 2 => 1, 3 => 2}}
iex(6)> |> elem(1) |> FibMemo.get(10)
{55,
 %{
   1 => 1,
   2 => 1,
   3 => 2,
   4 => 3,
   5 => 5,
   6 => 8,
   7 => 13,
   8 => 21,
   9 => 34,
   10 => 55
 }}

ちなみに elem(tuple, n) はタプルの n 番目（0始まり）の値を取り出す関数で、ここでは戻り値からメモの値だけを取り出しています。

課題

自分で計算結果を持ち回るばあいの問題は、計算結果の管理が必要になる点です。

たとえば FibMemo.get(memo, 10) で 1 〜 10 までの計算結果を記憶した memo10 を取得したにもかかわらず、FibMemo.get(memo, 40) のように初期化で取得した memo の値を使ってしまうと、10 までの計算をもう一度実行してしまいます。

iex> memo = FibMemo.initialize()           # memo は 1, 2 に対応する数を記憶している
iex> {f10, memo10} = FibMemo.get(memo, 10) # memo10 は 1〜10 に対応するを記憶している
iex> {f40, memo40} = FibMemo.get(memo, 40) # memo は 1, 2 に対応する数しか記憶していないので、3〜10 をふたたび計算する

本来注目している値の以外に計算結果の記録が式の中に混在していることが、煩雑になる一つの原因のようです。

そこで、計算結果を記録する部分を別のプロセスに分離して、注目している値の取得に専念できるようにしてみます。

別のプロセスで記憶する

ここでは Elixir の標準ライブラリにある Agent というモジュールを利用します。

Agent は新しいプロセスを生成し、Agent.get_and_update 関数が呼び出されたばあい、前段の結果を入力として二つの計算結果の組みを返します。一つは関数の戻り値になり、もう一つは次にこの関数を呼び出されたときの関数の入力になります。

またプロセスの識別にはプロセス ID を利用します。

記憶そのものには先ほど実装した FibMemo を引き続き利用し、ここではプロセス制御のためのコードだけを追加します。

defmodule FibAgent do
  def start do
    # プロセスを作成する
    # 初期値は FibMemo.initialize() の戻り値
    # 作成に成功すると :ok とプロセス ID のタプルを返す
    Agent.start(fn -> FibMemo.initialize() end)
  end

  def get(pid, n) do
    Agent.get_and_update(
      # 第1引数: プロセス ID
      pid,
      # 第2引数: memo を受け取り f と新しい memo の組みを返す関数
      # f は get_and_update の戻り値になり、新しい memo は次回呼び出される関数の引数になる
      fn memo -> FibMemo.get(memo, n) end
    )
  end
end

fib_agent.ex という名前で保存して iex で確認してみます。引き続き fib_memo.ex も利用するので c にはリストで二つのファイル名を渡します。

$ iex
iex(1)> c ["fib_memo.ex", "fib_agent.ex"]
[FibAgent, FibMemo]
iex(2)> {:ok, pid} = FibAgent.start()
{:ok, #PID<0.125.0>}
iex(3)> FibAgent.get(pid, 1)
1
iex(4)> FibAgent.get(pid, 2)
1
iex(5)> FibAgent.get(pid, 3)
2
iex(6)> FibAgent.get(pid, 10)
55
iex(7)> FibAgent.get(pid, 40)
102334155

考察

別プロセスに記憶をまかせることで、計算結果を持ち回る煩わしさからは解放されましたが、取得したい結果のための引数の他にもう一つ引数が必要な状況には変わりません。

しかし実際のところオブジェクト指向言語でも、オブジェクト自身を指し示す self や this を暗黙の引数として渡しているという事実があります。

たとえば Rust では、構造体とメソッドの実装は分離していて、メソッドの実装では self を明示します。 Rust はオブジェクト指向言語ではないので説明には不適かもしれませんが、self を受け渡している様子がよくわかると思います。

use std::collections::HashMap;

#[derive(Debug)]
struct Fib {
    memo: HashMap<u32, u32>,
}

impl Fib {
    fn new() -> Fib {
        let mut fib = Fib{memo: HashMap::new()};
        fib.memo.insert(1, 1);
        fib.memo.insert(2, 1);

        fib
    }

    fn get(&mut self, n: u32) -> u32 {
        match self.memo.get(&n) {
            Some(f) => *f,
            None =>
            {
                let f1 = self.get(n - 1);
                let f2 = self.get(n - 2);
                let f = f1 + f2;
                self.memo.insert(n, f);
                f
            }
        }
        
    }
}

fn main() {
    let mut fib = Fib::new();
    println!("{:?}", fib);

    println!("{}", fib.get(1));
    println!("{}", fib.get(2));
    println!("{}", fib.get(3));
    println!("{}", fib.get(10));

    println!("{:?}", fib);
}

$ cargo run
Fib { memo: {2: 1, 1: 1} }
1
1
2
55
Fib { memo: {9: 34, 2: 1, 5: 5, 3: 2, 8: 21, 4: 3, 1: 1, 7: 13, 6: 8, 10: 55} }

実は。 Elixir で、パイプ演算子を使って引数と関数の記述の順序を入れ替えると、メソッド呼び出しと似たような記述になります。

iex(1)> c ["fib_memo.ex", "fib_agent.ex"]
[FibAgent, FibMemo]
iex(2)> {:ok, fib} = FibAgent.start()
{:ok, #PID<0.125.0>}
iex(3)> fib |> FibAgent.get(1)
1
iex(4)> fib |> FibAgent.get(2)
1
iex(5)> fib |> FibAgent.get(3)
2
iex(6)> fib |> FibAgent.get(10)
55

import を使ってモジュール名の装飾を省略して関数を記述できるようになると、コード上の差異はさらに少なくなります。

iex(7)> import FibAgent
FibAgent
iex(8)> fib |> get(10)         
55
iex(9)> fib |> get(40)
102334155

オブジェクトとプロセスという、異なるものを扱っているということを意識する必要はありますが、記憶する側と利用する側の分離という文脈で考えたときに、似たような構造が見えてくるのが面白いところです。

プログラムで記憶する〜Prolog

オブジェクトで記憶する。プロセスで記憶する。他に計算結果を記憶する方法がないかと探してみました。そしてどちらとも異なる方法で実現できるものを見つけました。

はい、Prolog です。

記憶しない実装

ここでもまず愚直な実装から。処理系は今回も GNU Prolog を利用しています。

fib_naive(N, _) :- N < 1, !, false.
fib_naive(1, 1) :- !.
fib_naive(2, 1) :- !.
fib_naive(N, F) :-
  N1 is N - 1,
  N2 is N - 2,
  fib_naive(N1, F1),
  fib_naive(N2, F2),
  F is F1 + F2.

説明は省略しますが、Prolog は真偽を判定する述語でプログラムを実装します。そして引数に変数を与えたばあいは述語の式が真になるような変数の値を返します。このコードのばあい、第 2 引数に変数を与えると、述語 fib_naive が真になるような変数の値を得ることができます。

fib_naive.prolog という名前で保存して、GNU Prolog のコマンド gprolog を起動します。プロンプト | ?- に続いて ['fib_naive.prolog']. を入力してソースコードを読み込みます。

$ gprolog
| ?- ['fib_naive.prolog'].
yes

第 1 引数に数値を与え、第 2 引数に変数 F を与えて式を評価すると、式が真になる F の値が得られることがわかります。

| ?- fib_naive(1, F).
F = 1
yes
| ?- fib_naive(2, F).
F = 1
yes
| ?- fib_naive(3, F).
F = 2
yes
| ?- fib_naive(10, F).
F = 55
yes
| ?- fib_naive(40, F).
Fatal Error: global stack overflow (size: 32768 Kb, reached: 32765 Kb, environment var
iable used: GLOBALSZ)

40 を渡したところでスタックオーバーフローが発生しました。

プログラムを書き換える

最初のコードでは fib_naive(1, 1) と fib_naive(2, 1) を最初から定義しました。定義の数をもっと増やせば、計算せずに結果を取得することができるはずです。

そのようなアイディアのもと、動的に定義を増やすコードを書いてみます。

最初に dynamic で fib_memo/2 が動的な定義であることを宣言します。ちなみに /2 は fib_memo が 2 引数の述語であることを表しています。

さらに計算の最後に asserta を使って新しい定義を先頭に追加します。 fib_memo は最後の定義で計算をしているので、末尾に追加すると再び計算が実行されてしまうので、定義を先頭に追加するようにしています。

:- dynamic(fib_memo/2).

fib_memo(N, _) :- N < 1, !, false.
fib_memo(1, 1) :- !.
fib_memo(2, 1) :- !.
fib_memo(N, F) :-
  N1 is N - 1,
  N2 is N - 2,
  fib_memo(N1, F1),
  fib_memo(N2, F2),
  F is F1 + F2,
  asserta((fib_memo(N, F) :- !)).

ふたたび gprolog を起動し N = 40 を計算します。先ほどはスタックオーバーフローになりましたが、今回はきちんと計算できました。

$ gprolog
| ?- ['fib_memo.prolog'].
yes
| ?- fib_memo(10, F).
F = 55
yes
| ?- fib_memo(40, F).
F = 102334155
yes

定義を確認する

計算実行後の定義の状態を findall と clause を使って確認してみます。ここでも詳細は省略しますので、雰囲気だけでも感じてもらえたらと思います。

確認してみると、計算前では 1 と 2 のケースの定義のみですが、計算後では 1 〜 10 のケースも定義されていることがわかります。なお _ になっているケースは引数を変数で定義している箇所を表しています。

$ gprolog 
| ?- ['fib_memo.prolog'].
yes
| ?- findall([N, F], clause(fib_memo(N, F), _), NFs).
NFs = [[_,_],[1,1],[2,1],[_,_]]
yes
| ?- fib_memo(10, F).
F = 55
yes
| ?- findall([N, F], clause(fib_memo(N, F), _), NFs).
NFs = [[10,55],[9,34],[8,21],[7,13],[6,8],[5,5],[4,3],[3,2],[_,_],[1,1],[2,1],[_,_]]
yes

fib_memo(10, F) を評価したあとの結果は、次のように実装したのと同じ状態になっていることを示しています。実際、この以下のコードを読み込んで定義を確認してみると、上と同じ結果が表示されます。

:- dynamic(fib_memo/2).

fib_memo(10, 55) :- !.
fib_memo(9, 34) :- !.
fib_memo(8, 21) :- !.
fib_memo(7, 13) :- !.
fib_memo(6, 8) :- !.
fib_memo(5, 5) :- !.
fib_memo(4, 3) :- !.
fib_memo(3, 2) :- !.
fib_memo(N, _) :- N < 1, !, false.
fib_memo(1, 1) :- !.
fib_memo(2, 1) :- !.
fib_memo(N, F) :-
  N1 is N - 1,
  N2 is N - 2,
  fib_memo(N1, F1),
  fib_memo(N2, F2),
  F is F1 + F2,
  asserta((fib_memo(N, F) :- !)).

考察

Prolog には、知識をプログラミングするという側面があります。人工知能言語とも呼ばれる所以です。

たとえば次のコードは 1 から 10 までのフィボナッチ数を定義したものですが、

fib_memo(1, 1) :- !.
fib_memo(2, 1) :- !.
fib_memo(3, 2) :- !.
fib_memo(4, 3) :- !.
fib_memo(5, 5) :- !.
fib_memo(6, 8) :- !.
fib_memo(7, 13) :- !.
fib_memo(8, 21) :- !.
fib_memo(9, 34) :- !.
fib_memo(10, 55) :- !.

その真偽を「問い合わせ」ることができます。

| ?- fib(1, 1).    % f(1) = 1 は真
yes
| ?- fib(10, 55).  % f(10) = 55 は真
yes
| ?- fib(-1, 0).   % f(-1) = 0 は偽
no
| ?- fib(10, 123). % f(10) = 123 は偽
no

すでにお話ししたとおり、第2引数を変数にしたばあいは変数の値が真になる値を見つけるふるまいをします。

| ?- fib(10, F). % f(10) が真になるためには F = 55 でなければならない
F = 55
yes

ここで findall を使うと、真になる値をすべて見つけることができます。

findall(
  F,
  (
    between(1, 10, N),
    fib(N, F)
  ),
  Fs
).

なお between(L, M, N) は N が L から M までの間の整数のばあいに真を返す述語です。

実際に評価してみます。

| ?- findall(F, (between(1, 10, N), fib(N, F)), Fs).
Fs = [1,1,2,3,5,8,13,21,34,55]
yes

このように Prolog は、定義をデータベースとして利用しているとも言え、定義を追加することはデータベースにデータを追加する行為に相当します。

構文は違いますが、SQL によるデータベース問い合わせと似ていることがわかると思います。実際、Prolog の構文はある種のデータベースの問い合わせにも利用されています。

 n  | f  
----+----
  1 |  1
  2 |  1
  3 |  2
  4 |  3
  5 |  5
  6 |  8
  7 | 13
  8 | 21
  9 | 34
 10 | 55

select
  f
from
  fib
where
  n between 1 and 10
limit
  10;

テーブルで記憶する〜SQL

計算結果をデータベースで記憶するととらえるのであれば、一般のデータベースでもそれができるんじゃないかという気がしてきますが…実際、できます。ただし SQL で recursive を使えることが条件になりますが。

SQL の recursive を使って計算結果の行を再起的に連結してゆくことで、数列を取り出す例です。

with recursive fib(f, f1, f2) as (
  select 1, 1, 2
  union all
  select f1, f2, f1 + f2 from fib
)
select f from fib limit 10;

ここで次のように n を追加して where で n の値を指定すれば、その n に対応する f の値を求めることができます。このときの注意点として limit 1 を指定しておく必要があります。これを指定しないと二つ目以降の n = 10 の行を検索し続け、検索が止まらなくなってしまいます。

with recursive fib(n, f, f1, f2) as (
  select 1, 1, 1, 2
  union all
  select n + 1, f1, f2, f1 + f2 from fib
)
select n, f from fib where n = 10 limit 1;

 n  | f  
----+----
 10 | 55
(1 row)

まとめ

ここまで計算結果を記憶する方法を、オブジェクトに記録する以外の方法で考えてみました。いろいろと比較することで、あまり知られていない側面を見ることができたのではないかと思います。

個人的には。いろんなコードをたくさん書けたので満足です。

最後に。

株式会社永和システムマネジメントアジャイル事業部はエンジニアを絶賛募集しています。

いろんなコードをたくさん書いて満たされる、プログラミング好きの方のエントリをお待ちしております。

agile.esm.co.jp

ESM アジャイル事業部開発者ブログ

永和システムマネジメントアジャイル事業部の開発者ブログです。

計算結果を記憶する法〜オブジェクト・プロセス・プログラム・テーブル

オブジェクトで記憶する〜Ruby

記憶しない実装

オブジェクトで記憶する

プロセスで記憶する〜Elixir

記憶しない実装

自分のプロセスで記憶する

課題

別のプロセスで記憶する

考察

プログラムで記憶する〜Prolog

記憶しない実装

プログラムを書き換える

定義を確認する

考察

テーブルで記憶する〜SQL

まとめ