最強最速アルゴリズマー養成講座その2

例によって、最強最速アルゴリズマー養成講座から。この連載は最近の楽しみ。

http://www.itmedia.co.jp/enterprise/articles/1003/06/news002.html

mapに計算結果を保存するというところまでは思いついたものの、メモリサイズがえらいことになりそうなのは予想がついた。予想してたくせに手元のMacで実行してみて、スワップを発生させてマシン全体を重くしてみたり。

最終回答にあるような、適当な大きさのバッファを作成するというのは、言われてみれば確かにその通り。固定サイズのキャッシュと考えれば、それほど発想力を要求する訳でもない。ただ、今回のケースでは思いつかなかった。アルゴリズムで完全に解けると思い込んでいたので。

実際の開発ではリソースの都合というのは大きいので、こういうことは結構やっている。パッケージ品なんかだと、この設定値を設定ファイルに落とすのか、ハードコードするのか、結構悩ましかったりする。

蛇足だが、C++で実装した場合のコード。全体のソースについてはサンプルがダウンロードできるので、自作する関数の部分のみ記載。

Class InfiniteSequence2
{
  vector<long long> results;

public:
  long long calc(long long n, int p, int q, int x, int y)
  {
    results.clear();
    results.resize(1000000, 0);
    return calc2(n,p,q,x,y);
  }

  long long calc2(long long n, int p, int q, int x, int y)
  {
    if (n <= 0) return 1;
    if (n < results.size() && results[n] != 0) return results[n];
    long long res = calc2(n/p-x,p,q,x,y) + calc2(n/q-y,p,q,x,y);
    if (n < results.size()) results[n] = res;
    return res;
  }
...
}

ちなみに、昨日、再帰とループの話を書いたばかり。そちらではループの方がさも良いようにのたまっているが、これをループで書くのはなかなか難しい。