した特別な場合に当たる。表現されるが、今は四則演算に限っている。最小個数を決定することを考え、そのためのアルゴリズム例を紹介する。どちらも1~5000の範囲」としておく。今、箱がいくつもあって、箱1・箱2...と番号が振ってあるとする。1個使って作れる数を格納する。箱2には、「箱1の任意の数と箱1の任意の数に四則演算を施したもの」を格納する。箱3には、「箱1の任意の数と箱2の任意の数に四則演算を施したもの」を格納する。箱4には、「箱1の任意の数と箱3の任意の数に四則演算を施したもの」と「箱2の任意の数と箱2の任意の数に四則演算を施したもの」を格納する。以下同様に進んで、だんだん大きい番号の箱を埋めていく。現れれば、そのときの箱の番号が求める答え。作れる数の集合は有限であり、その要素は整然と列挙される。書くと、骨格は次のようになる。そのまま格納し、2番以降の箱には「既存の箱の中身をミックスして作った数」を格納する。箱Aと箱Bを「ミックスする」ということは、Aの中身(箱Aに入っている数)のそれぞれと、Bの中身のそれぞれとの間で四則演算を行い、生じた数を保存することだ。このバージョンにおいては「連想配列のキー」として実装されている。プロパティー名であり、文字列である。数値型に変換しないと、足し算が文字列の連結になってしまうので注意。引き算については、スワップの結果、負数が発生しなくなり、マイナスにならない方向に引き算した結果だけが保存されることになる。同様に、割り算については、割り切れる場合だけ考えれば足りる。掛けて分母で割れば、整数演算だけで同じ結果が得られる。何個使っているか」という本筋には影響しない。このようにしないと、生成できる数の個数が増えてメモリーが浪費され、計算量が増大して検索が遅くなる上、割り切れない数が絡む計算については丸め誤差に悩まされることになるだろう。作れる数)については重複して新しい箱に入れることはしない」と約束しておく。持つプロパティーが「マップ(連想配列)のキー」の役割を果たす。設定されるということだ。入っている」という命題の真偽を表す。配列とオブジェクトが同じように表現可能なため、上記は2次元配列のように見えるが、本物の2次元配列ではない。自身に既に入っているか」のチェックはしていない。入っていても、構わず同じキーと値のペアが再格納される(結果的に箱の中身は変化しない)。いう答えが、それも0.1秒未満で得られた。解が小さいので良かったが、一般には、このままでは速度的に問題がある。バージョン1を使ってそれを求めると、テスト環境では約6秒もかかってしまった。高速化その1高速化には「数学的な考察によって、実装すべき処理を改善する=無駄な仕事を引き受けない」という面と、「プログラミング的な工夫によって、処理を改善する=引き受けた仕事の効率を上げる」という面がある。この章では前者を扱う。要素数も箱12で10万個以上、箱13で30万個以上。これでは計算量が大きいのも当然で、計算精度も問題になる。大きな数を無制限に保存しても仕方ない。大きい数しか得られない。そのような数を経由してパズルが解ける可能性はない。以上の数は必要ない(四則演算のみという今回の前提においては)。個前の箱において、YXkである。「あ」より大きな数は、解に関係しない。箱を作るとき、これより大きい数を無視することにしよう。超える数を弾くようにすると、箱に格納される要素の個数が激減し、計算量が桁違いに減って処理が速くなる。いう解が得られた場合、基本的にそれは厳密解であり、「12個以下にはできない」ということが証明される。いくつなのか分からない。h」を利用するのでは、循環論法になってしまう。生成されることもあるが、簡易検索では(速度を優先するために)その可能性を無視する。設定し全数検索を行う。ほとんどの場合、最初と同じ結果が得られるが、2回目の結果は厳密解となる。最小(すなわち求める解)であることが証明される。作る方法」が発見される可能性もあるが、その場合、その個数が「全数検索による解」となる。対する上界を兼ねている。以上の数が現れた場合、そのままでは、この「厳密解」には理論上のきずが残る。「13個の27で2015」の計算時間はバージョン1では約6秒だったが、約3秒(簡易検索2.8秒、検証0.2秒)に改善された。大きな解を扱うことを考えると、まだまだ遅過ぎる。「16個の91で2079」は、簡易検索20秒、検証3秒を要する。おいて、ある数が既存か新規か判定するために、既存の全部の箱の中を調べていること。箱の中はマップであり、キーの有無を検索するだけでも少し時間がかかる。一つの数を検討するごとに毎回毎回いくつものマップを調べるのは、できれば避けたい。作り、既存か新規かの判定はそこへの1回の問い合わせだけで完了するようにしよう。以降、「箱の配列と箱番号」を渡す代わりに、単に「作成中の箱」(への参照)を渡せば足りることになる。2カ所に作られるためメモリー使用量はざっと2倍になってしまうが、これだけで(他の最適化とは独立に)4~6倍程度の高速化が実現される。マップとする一方、箱は配列にして使い分ければ、2通り保持することがむしろメリットとなる。一般に、箱の番号が増えるほど、箱の生成に必要な計算量は増大する。箱の番号が1増えるごとに、計算量はざっと2倍になるようだ。当然ながら、計算終了時点の最後の箱は、生成に一番時間がかかる。分からない状態での最初の試行では、箱そのものも巨大になる。大きい数がフィルターされているだけで、背後で行われている計算は必ずしも劇的には減っていない。定義されると中間の箱のサイズが増加し、それを経由した最後の箱の生成についても計算量が増える。どちらの場合についても、ここに高速化の余地がある。生成されたとたん、そこで計算を中止して構わない。小さくならないからだ。定義されたかどうか頻繁にチェックすればいい。後者の方法はマップ検索なので効率が悪い。返し、呼び出し側はこれをトリガーに検索を打ち切るのがいい。これだけで、平均2倍近く速くなる。箱に入れたとたんそれに気付くようにする。そのまま呼ぶと、全く同じ四則演算がざっと2回ずつ実行されてしまう。同じ意味であり、同じことを2回やるのは無駄だ。必要になるが、重複を省いて、ざっと半分の回数で済ませたい。箱を自分自身とミックスする場合、箱の中身を並べたキーの配列を作り、インデックスにより範囲を絞って無駄な演算の重複をなくすべきだろう。導入して呼び分けると、それだけでかなりの高速化になる。バージョン1では「箱12に数100が入っているという命題の真偽」と等価だったが、バージョン2では「箱12に入っている100番目(ソートされていない)の数」となる。外部にデータベースを作ったので、箱には「既存・新規の判定」の仕組みは必要ない。これで速度が上がる理由の一つは、(一般的に言って)配列のイテレーションの方がマップのキーのイテレーションより速いことだ。キーは基本的に文字列ということがある。数値と文字列の相互変換は遅い上、数値を文字列として保持するとメモリーが無駄になり、受け渡しの効率も悪いのだろう。その検討については、付録参照。下げると速度が改善される。作れる」という経験則。絞ると、簡易検索の結果が過大になる可能性が上がる。「い」という方法もある。バージョン2では、このチューンを使う。小さくすることもできるはずだ。作れる場合、このチューンには効果がないが、害もない。バージョン2上記のアイデアを織り込みながら、各部を更新してみた。フラグについては後述。作る方法」が全数検索される。呼ぶと、簡易検索が実行される。