6 : 04 四則演算でYを作るのに必要なXの最小個数

← 6‒03 p↑ もくじ i 6‒05 n →

二通りの暗譜と花の妖精からみた世界

2002年 6月11日
記事ID d20611

暗譜には二通りある。夢みる暗譜と、目覚めた暗譜だ — 正確にいえば、暗譜というより、暗譜による演奏の話だが。夢みる暗譜というのは、文字通り夢をみながら、気持ちよく、音楽に身をゆだねている。自分の世界だ。聴衆の存在は意識されない、あるいは、重要視されない。これに対して目覚めた暗譜では現実に起きていることのすべてが意識され、意識的にコントロールされている。自分がどこにいて、誰の前でどの曲を弾いているのか分かっている。どちらの演奏方法も正しい。しかし両方が混ざることは難しい問題を発生させる。つまり、夢みながら演奏を始めたら、途中で目覚めて次の音は何だったっけ?と暗譜について意識してはいけないのだ。もしそうすると、暗譜がとだえてしまう — 次の音は何だったっけと理性的に再確認しようとしたせいで、かえって次の音が分からなくなってしまうのだ。だから、目覚めることなく、無意識に、指が勝手に音楽を演奏するのを放っておくのが、いちばん良い。このことは音楽家のあいだではよく知られているのだが、さらなる問題は、ふだんそうやって無意識に夢みていても、いざ本番となると、とかく自意識的になって、おうおう夢が破れてしまうということだ。意識しなければすらすら自然に美しく指が勝手に弾いてくれるものを、意識が介入してしまうがために、駄目になってしまう。例えば自分ひとりで静かに楽しむ演奏ならラクだが、大勢の聴衆、とりわけ専門的な審査員の前で演奏することは、たいへんな負荷だ。

このような負荷にうちかつための根拠となる唯一の方法が練習だ。だれもみてなければ本当は弾ける曲、技術的には「本当は」すでに弾ける曲を、観測者の前でも弾けるようにするために、とほうもない努力をはらう。本当とは何だろうか。自分で弾ければ自分は本当は弾けるのだ、と自分は知っていることになる。けれど自分で弾けてもそれをだれかに対して実証できなければ、その曲を演奏できる証拠を示せないのであって、客観的には「まだその曲を弾けない」と言うべきかもしれない。ここでも自分の夢の世界と冷たい現実とがせめぎあう。

天才たちのなかには、現実で夢みつづける者も多い。かれらは一生、夢からさめない。夢のなかで — 自分だけの世界で — 演奏できれば良いのであれば、上達はたやすい。音楽家が払う労力のほとんどは、すでに本当は弾けるものを人前でも確実にうまく弾けるような保証を得るためのもので、だから初めから人を意識しないなら、ほとんど努力は要らない — それが天才のロジックかもしれない。人前でも弾ける保証というのもじつは自分自身にとっての保証、つまり自信というものだ。充分に練習していれば、自然と自信がつく。でも本当は、そんなにしつように練習しなくても、自分で楽しむだけならずっと上手に弾けるのだ。だから練習というのは、もともと弾けるものを弾けると認識するための自己暗示の手段なのかもしれない。どんなに練習しても、人前だと「実力」を百パーセント出せない、という人も多い — この場合も実力とは何か?という問が生じる。あなただけが知っているあなただけの世界の夢を実力と呼べるのか?という問が。実力をもっと客観的で冷厳なものだととらえる人々は、実力はあるのに人前ではそれをうまく発揮できない者について、「つまりそれが本当の実力なのだ」という。人前で、現実で、できなければ、実力でない、と。他方、人前で現実でどうあろうと、本当は自分でそれができるのだ、と自分で分かっていることこそが「ほんとう」なのだ、と考える者も多い。

暗譜の場合、本当は夢みているほうが美しく弾ける。現実を客観的に認識することなく夢みながら弾いたほうがいい。だが現実はあなたの世界にいつ割り込んでくるか分からない。夢が破れて目覚めてしまう。そのときになお平然と演奏をつづけられるために練習するのだ。目が覚めても夢のつづきを続けられるように練習するのだ。さらには現実のコンサートホール、人々、試験官を明晰に認識しながら、なおそこで夢みるためのはがねの意志のために、練習するのだ。現実にある自分を自覚しつつ、しかも夢みるために、この二重意識、このアンビバレント、この不安定な二世界の接触、共存、夢と現実のはざまのために、我々は練習するのだ。単調な繰り返し、ハノンのような機械的でつまらない訓練こそが、我々につねに夢みる権利を与えてくれる。我々がきびしい試練にたえるのは、目覚めていながら夢見る権利を得るためだ。この分裂は — ある詩人が言ったように — 決して特権ではなく、不可避だ。ふたつの世界にどうしても引き裂かれなければ存在できない — そんな形態の存在がかろうじて存在できるための、あやうい、あえかな場所。この行為の本質が、例えば殺人中毒のように極めて反社会的であることは、当事者たちにしか分からない。しかし周囲の人々も、詩人や芸術家と薬物中毒者や社会不適応者のあいだの否定できない関係性を察しているものだ。

花の妖精の話をしよう。

あなたは想像するかもしれない — 花畑が荒らされると、花の妖精たちが悲しむ、と。それは人間さんの考えというものだ。花の妖精にとって、花は宇宙だ。あなたは宇宙がなくなったら悲しいだろうか?

無意味な質問だ。宇宙そのものが失われたときには悲しいも悲しくないも、そもそもあなたは存在していないのだから。それに宇宙そのものが消滅するような大きなちからがあるとしたら、それは人間にはどうすることもできないレベルのものだから、いきどおったり、悲しんだりというのとは違うだろう。決定論的な運命 — 感情や意思の介入の余地のない、絶対にどうしようもない必然的な論理的帰結のようなものだろう。花の妖精にとっての花の破壊もそうなのだ。花が失われるなら、自分は失われるが、それは必然であって、悲しむべきことではない。ただの論理だ。人間にとっての宇宙の消滅と同様に非現実な話だ。もちろんいつかはそれは起きるかもしれないが、だからなんだというのだろう。宇宙の消滅をめぐる杞憂きゆうから、日々びくつきつつ暮らすことはない。いつかはこの世から花が失われる日が来るとしても、だからといって、花の妖精たちは、その日をおそれはしない。これはたとえだ — 我々は花の妖精であり、あなたがたは「いつまでも花があるわけでない。冬にそなえなさい」と訳知り顔で忠告する老人というわけだ。よろしい、花がなくなる日が来ることは認めよう。たぶんいつか、わたしたちにとっての遠い未来に(それはあなたがたに言わせば近い将来なのだろうが……)

花がなくなれば花の妖精はいなくなる。宇宙がなくなれば人間がいなくなるように。花の妖精は花がなくなる日のためにそなえたりしない。人間が宇宙消滅にそなえたりしないように。このように、わたしたち妖精には、最後の最後の一瞬まで夢みる権利が与えられている — これも特権というより妖精の実存をめぐる不可避なのだが。

いつかは夢から目覚めるかもしれないとしても、そのときには、もうわたしたちはいなくなる。それでいい……というより、現実におそわれてもなお夢みつづけることができる強靱きょうじんな精神……妖精とは現実のなかに屹立きつりつする夢なのだ。その頑強がんきょうさは、だが峻厳しゅんげんではない……ある種のごまかし、本当はありえない両立、本来ありえべからざるもの、あいまいさ……そのあやういはざまに、夢と現実のきわどいすきまに、妖精たちのすみかがある。夢と心中する覚悟を決めた者だけが訪れることのできる秘密の花園が。わたしは夢みない。夢であるのだ。夢から覚めるとき、わたしは、ない。

学校なんてやめちゃって、デカダン、酔いしれ暮らさないか?

それもいい。脱獄するのは自由を求めてだ。脱獄囚は自由だし、独房の外のやつらは最初から自由だ。 — だが、オレは、あの牢獄のなかで、外の自由人よりいっそう自由でありつづけることができたのだった。というより、本当の問題は、しばられていることでなく、決してしばられることができない、ということなのだ。できることなら現実にしばられたい。現実と関係を持ちたい。どこかでそう願っていたのかもしれないが、そうした願いが意味を持つのは同じ平面上にいるときだけだ。

リンク

この記事のURL


「西暦・平成パズル」を解くアルゴリズム

2016年 3月27日
記事ID e60327

2016年は平成28年だが、整数 28 と四則演算の組み合わせで 2016 を表すためには、最小でも9個28 が必要だ。例えば:

2016 = (28+28+28)×[28−(28+28+28+28)/28]

どうして「9個が最小」と分かるのか? 「8個以下ではできない」ことは、どのように示されるか?

全数検索で解くのは困難なようにも思えるが、この種のパズルは、50~100行程度のシンプルなコードにより高速に解決される。

以下ではそのアルゴリズムを紹介し、JavaScript による実装例を示す。実験として ES6 (ECMAScript 2015) の MapSet も試した。Map は従来のマップ風 Object とほぼ同じ機能を持つが、数値をキーとする場合には効果が高い。おまけとして「組み込み関数の splice より速い配列への要素挿入法」も紹介。

パズル自体は面白いだけで何の役にも立たないが、アプローチの中には応用の利く事柄もあるかもしれない。

[1/7] パズルの内容

「2828も2個の28だ」と見なすなら、次のように、この数は5個まで減らせる。

「反復による桁増やし・べき乗・平方根などを許容するかしないか」のルール設定により、一般に解(必要となる最小個数)は異なる。最初は「純粋に四則演算のみ使用可。数を並べて桁数を増やすのは駄目」というシンプルなルールでいこう。

27 を使って 2015 を作る場合、最小でも13個27 が必要になる。例えば:

2015 = {[27×27−27−(27+27+27)/27−27]×(27+27+27)−27}/27

問題は次の形に一般化される。

簡単に言えば:

「西暦・平成型」は、X = Y−1988 とした特別な場合に当たる。もっと一般の場合の例として、20167個4 で表現される。

指数を許せば、5個4 で表現されるが、今は四則演算に限っている。

以下では、この種の問題における必要な X の最小個数を決定することを考え、そのためのアルゴリズム例を紹介する。

「任意」だと具体的に試しにくいので、一応「XY は、どちらも1~5000の範囲」としておく。

[2/7] アルゴリズムのスケッチ

28 を使って 2016 を作りたいとする。

今、箱がいくつもあって、箱1・箱2…と番号が振ってあるとする。

箱1には、28 を1個使って作れる数を格納する。それは 28 自身にほかならない。

箱2には、「箱1の任意の数と箱1の任意の数に四則演算を施したもの」を格納する。任意と言っても箱1には 28 しか入っていないのだから、結果は 28+28=56, 28−28=0, 28×28=784, 28/28=1 の4個に限られる。

箱3には、「箱1の任意の数と箱2の任意の数に四則演算を施したもの」を格納する。

箱4には、「箱1の任意の数と箱3の任意の数に四則演算を施したもの」と「箱2の任意の数と箱2の任意の数に四則演算を施したもの」を格納する。

以下同様に進んで、だんだん大きい番号の箱を埋めていく。どこかで 2016 が現れれば、そのときの箱の番号が求める答え。

要するに、n 個の 28 で作れる数の集合は有限であり、その要素は整然と列挙される。

[3/7] バージョン1

主要部分(14行)

「アルゴリズムのスケッチ」の内容を JavaScript で書くと、骨格は次のようになる。1番の箱、2番の箱…が順に作られ(最大29番まで)、どこかの箱に Y が入っていたら、その箱の番号 n が報告される。

var X = 28;
var Y = 2016;
Search();

function Search()
{
    var box = []; // box array

    for( var n = 1; n < 30; ++n ) {
        Make_new_box( box, n ); // box[0] is unused

        if( box[ n ][ Y ] ) {
            alert( n );
            break;
        }
    }
}
ミックスによる箱の構築(28行)

「新しい箱を作る」という部分では、1番の箱には X をそのまま格納し、2番以降の箱には「既存の箱の中身をミックスして作った数」を格納する。箱Aと箱Bを「ミックスする」ということは、Aの中身(箱Aに入っている数)のそれぞれと、Bの中身のそれぞれとの間で四則演算を行い、生じた数を保存することだ。

function Make_new_box( box, n ) // n: box number
{
    box[ n ] = {}; // Object, used as a map

    if( n == 1 ) {
        Store( X, box, 1 );
    } else {
        for( var i = 1; i <= n/2; ++i )
            Mix( box[i], box[n-i], box, n );
    }
}

function Mix( boxA, boxB, box, n )
{
    for( var a in boxA ) {
        for( var b in boxB ) {
            Calc( a, b, box, n );
        }
    }
}

function Calc( a, b, box, n )
{
    a = Number(a);
    b = Number(b);

    if( a < b ) { var tmp = a; a = b; b = tmp; }

    Store( a + b, box, n );
    Store( a - b, box, n );
    Store( a * b, box, n );
    if( b != 0 && a % b == 0 ) Store( a / b, box, n );
}

Calc に渡される ab は、このバージョンにおいては「連想配列のキー」として実装されている。JavaScript においては(このコード例においては)、これは Object のプロパティー名であり、文字列である。数値型に変換しないと、足し算が文字列の連結になってしまうので注意。

このとき、箱Aから出した数 a と箱Bから出した数 b について、もし ab より小さいときは最初に abスワップしておく。スワップしても足し算・掛け算の結果は変わらないが、

これらは演算の順序だけの違いなので、「X を何個使っているか」という本筋には影響しない。

このようにしないと、生成できる数の個数が増えてメモリーが浪費され、計算量が増大して検索が遅くなる上、割り切れない数が絡む計算については丸め誤差に悩まされることになるだろう。

生成された数を格納(7行)

生成された数を作成中の箱にどんどん詰めればいいのだが、「既存の箱のどれかに入っている数(もっと少ない個数の X で作れる数)については重複して新しい箱に入れることはしない」と約束しておく。

function Store( number, box, n )
{
    for( var i = 1; i < n; ++i ) {
        if( box[ i ][ number ] ) return;
    }

    box[ n ][ number ] = true;
}

箱の一つ一つは Object であり、その Object が持つプロパティーが「マップ(連想配列)のキー」の役割を果たす。number を箱 n に入れるということは、

ということだ。一方、その箱に入っていない数についてはキーが未定義となり、未定義値をブールに変換すれば false なので、事実上、box[n][c] は、「数 c が箱 n に入っている」という命題の真偽を表す。(JavaScript では配列とオブジェクトが同じように表現可能なため、上記は2次元配列のように見えるが、本物の2次元配列ではない。)

「その数を箱 n に入れるかどうか」の判定において、ここでは「その数が箱 n 自身に既に入っているか」のチェックはしていない。もし既に入っていても、構わず同じキーと値のペアが再格納される(結果的に箱の中身は変化しない)。

バージョン1の結果報告

以上、空行を除けば、合計49行の簡単なスクリプトだが、これを実行すると、めでたく 9 という答えが、それも0.1秒未満で得られた。

この例はたまたま h = 9 と解が小さいので良かったが、一般には、このままでは速度的に問題がある。例えば27を使って2015を作る場合 h = 13 だが、バージョン1を使ってそれを求めると、テスト環境では約6秒もかかってしまった。h = 16h = 17 になることもあるのに、h = 13 の検索がこれでは困る。

とりあえず動くことは分かったので、さっそく高速化にかかろう!

[4/7] 高速化その1

高速化には「数学的な考察によって、実装すべき処理を改善する=無駄な仕事を引き受けない」という面と、「プログラミング的な工夫によって、処理を改善する=引き受けた仕事の効率を上げる」という面がある。この章では前者を扱う。

上界の評価

バージョン1で「13個の27で2015」の検索をすると、箱12以降において中身の最大値が2の53乗以上になり、JavaScript で正しく扱える整数値の限界 253−1 を超えてしまう。要素数も箱12で10万個以上、箱13で30万個以上。これでは計算量が大きいのも当然で、計算精度も問題になる。

大きな数を無制限に保存しても仕方ない。「13個の27で2015を作る」という例でいうと、箱13には、もちろん 2015 より大きい数は必要なく、箱12には、(2015×27)+1 以上の数は必要ない。実際、数を小さくする最強の方法は割り算だが、(2015×27)+1 以上の数を 27 で割っても(そして割り切れたとしても)ターゲットの 2015 より大きい数しか得られない。つまり、そのような数を経由してパズルが解ける可能性はない。同様に考えて、箱11には、(2015×272)+1 以上の数は必要ない(四則演算のみという今回の前提においては)

この考えを一般化すると: 解に関係する可能性がある最大の数は、最後の箱の k 個前の箱において、

である。すなわち、h 個の XY を作れるとき、箱 n において、

より大きな数は、解に関係しない。箱を作るとき、これより大きい数を無視することにしよう。

上記の数を表す変数 MaxLimit を設定し、Store の最初で MaxLimit を超える数を弾くようにすると、箱に格納される要素の個数が激減し、計算量が桁違いに減って処理が速くなる。

上界をきちんと考慮した上で全数検索し、例えば h = 13 という解が得られた場合、基本的にそれは厳密解であり、「12個以下にはできない」ということが証明される。

2パス方式

上記の MaxLimit の設定では「使用する X の合計個数 h」を用いているが、パズルを解かない限り h がいくつなのか分からない。「解を得るための補助パラメーター」として「解が出てからでないと分からない h」を利用するのでは、循環論法になってしまう。

この場合、最初の試行(簡易検索)では、MaxLimit を暫定的に 224 に固定しておくといい。現実には 224 より大きい数を経由して Y が生成されることもあるが、簡易検索では(速度を優先するために)その可能性を無視する。この制限の下で「Xh 個必要」という解(近似解)が得られたとき、今度はその h を使って MaxLimit を設定し全数検索を行う。ほとんどの場合、最初と同じ結果が得られるが、2回目の結果は厳密解となる。

正確に言えば、2パス目では、h ではなく h−1 を使うことができる。実際、1パス目で「それが最小かは分からないが、とりあえず h 個あればできる」ことが分かったとして、2パス目で「h−1 個以下ではできない」ことが分かれば、h が最小(すなわち求める解)であることが証明される。条件によっては、2パス目において「h−1 個以下の XY を作る方法」が発見される可能性もあるが、その場合、その個数が「全数検索による解」となる。(「あ」から明らかなように、同一番号の箱において、大きな h に対する上界は、小さな h に対する上界を兼ねている。)

ただし、MaxLimit253 以上になって、計算に 253 以上の数が現れた場合、そのままでは、この「厳密解」には理論上のきずが残る。

高速化その1の結果

「13個の27で2015」の計算時間はバージョン1では約6秒だったが、約3秒(簡易検索2.8秒、検証0.2秒)に改善された。しかし、もっと大きな解を扱うことを考えると、まだまだ遅過ぎる。例えば「16個の91で2079」は、簡易検索20秒、検証3秒を要する。

[5/7] 高速化その2

マップ検索の高速化

バージョン1のまずい点は、Store において、ある数が既存か新規か判定するために、既存の全部の箱の中を調べていること。箱の中はマップであり、キーの有無を検索するだけでも少し時間がかかる。一つの数を検討するごとに毎回毎回いくつものマップを調べるのは、できれば避けたい。

そこで、グローバルオブジェクトとして「どれかの箱に入っている数は全部記録してある」というデータベース DB を作り、既存か新規かの判定はそこへの1回の問い合わせだけで完了するようにしよう。これによって、Store は「作成中の箱番号」を知る必要もなくなり、Mix 以降、「箱の配列と箱番号」を渡す代わりに、単に「作成中の箱」(への参照)を渡せば足りることになる。

同じキーが箱と DB の2カ所に作られるためメモリー使用量はざっと2倍になってしまうが、これだけで(他の最適化とは独立に)4~6倍程度の高速化が実現される。後述するように、DB をマップとする一方、箱は配列にして使い分ければ、2通り保持することがむしろメリットとなる。

打ち切りによる高速化

一般に、箱の番号が増えるほど、箱の生成に必要な計算量は増大する。箱の番号が1増えるごとに、計算量はざっと2倍になるようだ。当然ながら、計算終了時点の最後の箱は、生成に一番時間がかかる。h が全く分からない状態での最初の試行では、箱そのものも巨大になる。

h が定義され、MaxLimit による制限が厳格になった場合、最後の箱には Y 以下の数だけが入るので、箱のサイズは劇的に小さくなるが、これは見掛け上 Y より大きい数がフィルターされているだけで、背後で行われている計算は必ずしも劇的には減っていない。むしろ一般には、h が定義されると中間の箱のサイズが増加し、それを経由した最後の箱の生成についても計算量が増える。

どちらの場合についても、ここに高速化の余地がある。すなわち、h の最小値を決定するのが目的なら、1個でも Y が生成されたとたん、そこで計算を中止して構わない。さらに計算を進めた場合、「同じ個数の XY を作れるもっときれいな式」が見つかる可能性はあるものの、X の個数 h は小さくならないからだ。

このメカニズムを実現するためには、Calc などの関数が値を返すようにして呼び出し側で戻り値をチェックするか、または、DB[Y] が定義されたかどうか頻繁にチェックすればいい。しかし、後者の方法はマップ検索なので効率が悪い。生成された数が直接見える Store において、Y を格納したら true を返し、呼び出し側はこれをトリガーに検索を打ち切るのがいい。これだけで、平均2倍近く速くなる。

要するに、一つの箱を完成させてから「中に Y が入っていないかな」と探すのではなく、箱を作っているとき箱に入れる数を常に監視し、Y を箱に入れたとたんそれに気付くようにする。

箱を構築する部分の高速化

バージョン1の Make_new_box には、高速化の余地がある。

明白な問題点として、A と B が同一の箱の場合、Mix をそのまま呼ぶと、全く同じ四則演算がざっと2回ずつ実行されてしまう。例えば、{x, y, z} の3要素を含む箱を自分自身とミックスすると、四則演算を # として、x#x, x#y, x#z, y#x, y#y, y#z, z#x, z#y, z#z が実行されるが、第1項と第2項は大きい順に並び替えられるため、x#yy#x などは全く同じ意味であり、同じことを2回やるのは無駄だ。要素数が1000だとすると、Mix では100万回の Calc が必要になるが、重複を省いて、ざっと半分の回数で済ませたい。箱を自分自身とミックスする場合、箱の中身を並べたキーの配列を作り、インデックスにより範囲を絞って無駄な演算の重複をなくすべきだろう。それを行う Self_mix を導入して呼び分けると、それだけでかなりの高速化になる。

どうせそこで配列が必要になるのなら、最初から箱の中身を配列にしておこう!

例えば box[12][100] は、バージョン1では「箱12に数100が入っているという命題の真偽」と等価だったが、バージョン2では「箱12に入っている100番目(ソートされていない)の数」となる。外部にデータベースを作ったので、箱には「既存・新規の判定」の仕組みは必要ない。

これで速度が上がる理由の一つは、(一般的に言って)配列のイテレーションの方がマップのキーのイテレーションより速いことだ。しかし、もっと根本的な理由として、配列なら数値を出し入れできるが、Object のキーは基本的に文字列ということがある。数値と文字列の相互変換は遅い上、数値を文字列として保持するとメモリーが無駄になり、受け渡しの効率も悪いのだろう。

では、いっそのこと DB も配列にして、DB.push() で数を格納してはどうか? その検討については、付録参照。

魔チューン

簡易検索において箱の番号が16以上になったとき、MaxLimit216 に下げると速度が改善される。根拠は「想定している数の範囲では、ほとんどの場合、最大でも16個(まれに17個)の X があれば、Y を作れる」という経験則。ただし、あまり絞ると、簡易検索の結果が過大になる可能性が上がる。過大な h をなるべく防ぎたい場合、

という方法もある。バージョン2では、このチューンを使う。

これが最善というわけではなく、簡易検索における MaxLimit はもっと小さくすることもできるはずだ。

15個以内の XY を作れる場合、このチューンには効果がないが、害もない。

[6/7] バージョン2

上記のアイデアを織り込みながら、各部を更新してみた。

主要部分(38行)

f53 フラグについては後述。

Search(x,y,nBox) を呼ぶと、「nBox 個以下の x を使って y を作る方法」が全数検索される。第3引数を略して Search(x,y) を呼ぶと、簡易検索が実行される。いずれの場合も、y を作れたら直ちに検索が打ち切られ、そのときの(中に y が入っている)箱の番号が answer に格納される。関数は answer を返す(answer を決定できなかった場合は 0 を返す)。

var DB; // database
var MaxLimit = 16777216; // 2^24 (default)
var Y;
var f53 = false;
var MAX_X=5000, MAX_Y=5000, MAX_NBOX=29, DEF_NBOX=29;

var answer = Search( 27, 2015 ); // answer=13 (estimated)
/// answer = Search( 27, 2015, 13 ); // answer=13 (proven)

function Search( x, y, nBox ) // nBox: max number of boxes
{
    if( ! Is_valid( x, y, nBox ) ) return 0;

    DB = {};
    Y = y;
    var box = new Array( ( nBox ? nBox : DEF_NBOX ) + 1 );

    var answer; // Y is in box[answer]
    for( var n = 1, len = box.length; n < len; ++n ) // box[0] is unused
    {
        MaxLimit = Get_upper_bound( x, y, nBox, n );

        if( Find_Y_in( box, n, x ) ) {
            answer = n;
            break;
        }
    }
    box.length = 0; // *1
    Show_results( x, y, answer, nBox ); // *2
    DB = void 0; // *3

    return (answer || 0);
}

nBox は、使う箱の最大個数で、box 配列の長さは、それより 1 大きい。

メモリー不足などもあり得るので、実際のコードではループを try で保護するべきだろう。

Find_Y_in() はバージョン1の Make_new_box() に当たる。

*1 の行はなくてもいいが、box[1]box[2]…に含まれる要素数は計100万を超えることもあるので、用が済み次第、明示的に無効化しておく。

*2 は、検索結果を表示する。

グローバルなデータベース DB については、用が済んだら必ず無効化するべきだろう(*3)。参照可能のままだと、(ブラウザ上で実行しているとして)ページを開いている限り巨大オブジェクトが残ってしまう。

Get_upper_bound は、検索範囲の上界を返す。具体的には:

function Get_upper_bound( x, y, nBox, n ) // nBox: max number of boxes, n: current box number
{
    if( nBox ) return y * Math.pow( x, nBox - n ); // inaccurate if >= 2^53
    else return Math.pow( 2, n < 16 ? 24 : n == 16 ? 20 : 16 );
}

上界の値自身は有効な範囲の一部(許容最大値)なのか、範囲外で無効なのか?」という境界問題は、常にバグの原因になる。ここでは「許容最大値」。値が2の53乗以上の場合、この計算には難点があるが、今回はその問題には立ち入らない。

MaxLimit を参照する Store は、呼び出しの最下層にある。どうやってそこまで情報を伝えるか。

試してみたところ、この場合、変数を引数渡しにすると速度が少し低下し、グローバル変数の方がかえって速いようだ。ここではアルゴリズムを端的に紹介することを優先して、MaxLimit をグローバル変数とした。YDB についても同様。

入力値のエラーチェックは次の通り。|0 はダミーのビットOR。ビット演算を行うと暗黙に数値型・32ビット整数へのキャストが起きるため、入力がそれ以外(例えば非整数)なら、型または値が変わって弾かれる。

function Is_valid( x, y, nBox )
{
    if( nBox === void 0 || nBox === 0 ) nBox = DEF_NBOX;

    return ( (x|0) === x && x >= 1 && x <= MAX_X &&
            (y|0) === y && y >= 1 && y <= MAX_Y &&
            (nBox|0) === nBox && nBox >= 1 && nBox <= MAX_NBOX );
}
箱詰め管理・改良版(32行)

バージョン1の Make_new_box は、バージョン2では Y 発見時に true を返す仕様になり、Find_Y_in と改名された。

/// function Make_new_box( box, n ) // n: box number
function Find_Y_in( box, n, x )
{
    var new_box = box[n] = []; // Array!

    var found = false;

    if( n == 1 ) {
        found = Store( x, new_box );
    } else {
        for( var i = 1, last = (n >>> 1); i <= last && !found; ++i ) {
            if( i != n-i ) found = Mix( box[i], box[n-i], new_box );
            else found = Self_mix( box[i], new_box );
        }
    }

    return found;
}

new_box は、box[n] と同じ配列を指す。(理論上は、こんな名前を付けずに box[n] をそのまま他の関数に渡しても差し支えない。)

n>>>1 は、232 未満の負でない整数 n について、n/2 の整数部分を表す。この場合、last=n/2 と書いて 0.5 の端数を放置しても動作するし、事実上ほとんど違いはないだろう。しかし、余計な端数がない方がいいし、ビットシフトには速度的なメリットもある(付録参照)。

箱2以降の作成中、found は、ループ内において関数から戻り値を受け取る。その値は Y が見つかった場合にのみ true であり、そのときには !found が偽になってループが終わる。

以下の2個の関数は Find_Y_in から呼び出され、「ある箱と別の箱」または「同じ一つの箱」から順々に2個の数を選んで、Calc に渡す。

function Mix( boxA, boxB, new_box ) 
{
    for( var i = 0, lenA = boxA.length; i < lenA; ++i ) {
        for( var j = 0, lenB = boxB.length; j < lenB; ++j ) {
            if( Calc( boxA[ i ], boxB[ j ], new_box ) ) return true;
        }
    }
    return false;
}

function Self_mix( boxA, new_box )
{
    for( var i = 0, lenA = boxA.length; i < lenA; ++i ) {
        for( var j = 0; j <= i; ++j ) {
            if( Calc( boxA[ i ], boxA[ j ], new_box ) ) return true;
        }
    }
    return false;
}
箱詰め実務・改良版(20行)

Calc は通知された2数の間で四則演算を行い、生成された数を Store に送る。

function Calc( a, b, new_box )
{
    if( a < b ) { var tmp = a; a = b; b = tmp; } // [a,b]=[b,a] @ES6

    return ( Store( a + b, new_box )
            || a > b && Store( a - b, new_box )
            || Store( a * b, new_box )
            || a % b == 0 && Store( a / b, new_box ) );
}

バージョン2では箱の中身が数値なので、Calc 先頭での「文字列から数値への変換」は必要なくなった。a または b が 0 の場合、四則演算によって新しい数が生じないのは明らかだから、処理を省略できる。いっそのこと、引き算のとき a>b を要請して、最初から 0 を作らないようにしよう。そうすれば 0 は計算のどこにも含まれず(どの箱にも格納されず)、割り算の前のゼロ除算チェックも必要なくなる。

function Store( number, new_box )
{
    if( number > MaxLimit ) return false; // *1

    if( number > 9007199254740991 ) { // 2^53-1 // *2
        f53 = true; // global flag
        return false;
    }

    if( DB[ number ] ) return false; // *3

    new_box.push( number );
    DB[ number ] = true;

    return ( number == Y );
}

Store は、渡された数が上界を超えている場合(*1)、正確な処理が可能な最大値を超えている場合(*2)、データベースに登録済みの場合(*3)には、その数を受け付けない。それ以外の場合には、その数を new_box に追加し、データベースに登録する。

*2 の拒否は「MaxLimit 以下だが 253−1 を超える数」に対するもの。JavaScript において(一般に倍精度浮動小数点演算において)253−1 を超える整数値は信頼できない(1以上の誤差を含む可能性が高い)。拒否すると全数検索にならないが、少なくとも「箱の中の数は全て正確」という保障が得られる。拒否しないと「信頼できない数」が箱に入り込み、それを経由した「間違った Y の作り方」が誤検出される可能性が生じる。従って、拒否する方が害が少ない。この状況が発生したら、目印として f53 フラグを立てておく。

ES6 では、253−1Number.MAX_SAFE_INTEGER という名前が与えられている。

バージョン1と違い、作成中の箱の中に同じ数があった場合、データベースで「既存」と判定されるため、再格納は行われない。そのため new_box は要素に重複のない配列となる。Y が生成された場合、Store が第一発見者となり、戻り値 true の連鎖をトリガーする。

関数を適当にネストすれば(さらには全体をクラス風にまとめれば)、new_box の受け渡しが不要になってコードが緊密になるが、それをやると速度が低下することがある。

検索結果の出力(13行)
function Show_results( x, y, answer, nBox )
{
    var message = ( "x=" + x ) + ( ", y=" + y ) + ( ", nBox=" + nBox ) + ": [ Results ] ";

    if( nBox ) {
        if( f53 ) message += "Maybe "; // f53: global flag
        if( answer ) message += ( "h = " + answer );
        else message += ( "h > " + nBox );
    } else {
        if( answer ) message += ( "h ≤ " + answer );
        else message += ( "Search failed!" );
    }

    alert( message );
}

nBox=0 は未定義と同じ扱いになる。(これをエラーにしたければ、Is_valid において nBox===0 を通さなければいい。)

結果が「検索失敗」になるケースでは、実際には多分、結果までたどり着けない: スクリプトの実行時間が長過ぎて強制的に中断されるか、メモリー確保に失敗して(捕捉可能な)例外が発生するだろう。

alert は純粋に説明のためのもので、現実のコードでは、もっとましな出力をページ上に書き出せばいい。

バージョン2の結果報告

「2015を作るには27が13個必要」という検証は、バージョン1では5.8秒もかかったが、バージョン2を使うと、0.1秒未満になった。実行時間は環境によって異なるが、相対的に速度が約170倍になった。

「2079を作るには91が16個必要」という証明は、高速化の途中では10秒以上かかっていたが、今では簡易検索0.3秒、全数検索0.6秒になった(f53 フラグが立ってしまうが、15個では作れないことは検証可能なので、解16は確定的)。

「2117を作るには129が17個必要」という解については、フラグが立ってしまうものの、簡易検索0.5秒、全数検索2.4秒だった。簡易検索のあと nBox=16 で全数検索すれば検証1.0秒であり、合計1.5秒で同じ結論が得られる(フラグは立ってしまう)。

「西暦・平成型」で2200年くらいまでを考えた場合、だいたい h=17 がワーストケースだ。それが実用的な時間で解けるようになった。

チューニングやアルゴリズムの改善により、さらなる高速化も可能だろう。例えば、DB として ECMAScript 2015 (ES6) で標準化された Map を使うと、上記の0.5秒/2.4秒が、0.4秒/1.8秒に短縮され、Set を使うと、0.4秒/1.6秒に短縮された(付録参照)。

[7/7] 結論と展望

一見「全数検索は不可能」とも思われる形のパズルだが、50~100行程度のシンプルなスクリプトによって、数秒で(多くは1秒以内に)全数検索が実行される。確かに計算量が壁になるが、地味な工夫をいくつか積み上げることで、結果的にブレークスルーが生じた。

まだ改善の余地・検討すべき課題も多い:

  1. Y が作れた証拠として実際に X の式を出力しないと、パズルが解けた気がしない。その処理は簡単で、CalcStore の処理を少し変えて、データベースには、各キーごとに「どういう二項演算でその数を作れたのか」というレシピを登録すればいい。そのデータベースを見れば、Y を発生させた二項演算が分かり、同じデータベースにより、その二項演算の2項のそれぞれのレシピも分かり、それらのレシピの材料のレシピも分かり…となって、芋づる式に X まで「分解」できる。
  2. 「2通り以上の分解ができる場合に、どの分解をデータベースに書くのか」という点(レシピの優劣判定)は、また別の問題となる。
  3. それらと合わせて、ブラウザ上から試せるデモを公開するべきだろう。
  4. f53 フラグが立ってしまうケースにおいて、厳密性を保障するのは容易ではない。理想は、数学的考察により上界の評価を改善し、巨大な数を極力排除すること。次善の策は、64ビット整数をサポートしている言語を使い、扱える整数の上限を上げること。どうしても JavaScript でやるとなれば、53ビット以上の演算を自分で実装するか、その種のライブラリを使う必要がある。
  5. 現在のアルゴリズムでは X から Y に向かって検索しているが、逆方向に検索するのはどうだろう? つまり「X を2個使えば ABC が作れて、それらを組み合わせれば DEF が作れて…」とやる代わりに、「YST から作れるが、SPQ から作れて…」と帰納的に考えることもできる。状況によっては、その方が速いこともあるはずだ。
  6. 整数以外の Y を効果的に検索できるか? 例えば:

以前にも似た問題を何度か紹介したことがあるが、そのときは「ラムダ関数」「文字列を作ってそれを動的に式として評価する方法」「関数を要素とする配列」といった技巧的な方法に走ってしまった。それはそれでワクワクするが、実はそんな面倒なことをしなくても、普通に+−×÷の計算をすればいい。本文の Calc がその実装例だ。技巧の探求も楽しいけれど、単純なやり方がかえって速ければ、実用上はそれが一番だろう。

付録

ECMAScript 2015 (ES6) の利用

ES6 の MapSet がサポートされる環境では、次のようにすると速くなる。

本文の DBObject なので、キーが(実質は数値だが)文字列となる。言うまでもなく、これは効率が悪い。整数 123 が文字列 "123" として格納されるからだ。Map では、数値が数値のままキーとなるので、効率が上がる。

それと比べると小さな問題だが、本文の例ではどのキーに対しても値が true なので、本来マップにする意味がない。本質的には「キーが定義されているかどうか」で既存・新規が判定され、キーが持つ値は利用されていない。従って、Map ではなく Set を使うと、ちょうどいい。その場合、値を追加するときは、DB.add(c) とする。データベースに「キーごとのレシピ・生成コスト」などの情報を格納する場合、Map が必要だが、値がダミーなら Set の方がすっきりする。

Set を「キーだけのマップ」であるかのように記述したが、実際には「値だけのマップ」。Set の中身を for ループで列挙したい場合、key in ではなく value of になる。

DB を配列にすると?

ES6 がサポートされていない環境においても、DB を数値の配列として、DB.push(c) で数値をそのまま格納することは可能だ。マップ風 Object よりメモリー的な効率は高いだろう。

ただしその場合、DB.has(c) に当たるうまいメソッドがない。

素朴に考えれば、DB.indexOf(c)!=-1 だが、これは「データベースに問い合わせるたびに、既存かどうか、端から1個ずつ要素を調べること」に当たり、速いわけがない。ES7 には DB.includes(c) もあるが、仕様書を見る限り速くない。やるなら、配列をソートしてバイナリーサーチだろう。といっても、検索・挿入のたびに sort() を呼んでソートし直すわけにはいかない。配列を常にソート済みに保っておいて、「渡された数 c が既存だとすれば、配列のどこにあるか」をバイナリーサーチで調べ、その位置に実際その数があれば「既存である」と却下し、その数がなければ「新規なので受け付けます」と、その位置に挿入すればいい。この方式を仮に「自己ソート配列」と呼んでおく。

問題は「新規なので受け付けます」というとき、ソートされた位置(配列のど真ん中)にどうやって要素を挿入するのか、という点だ。コード上では splice() により簡単にできるが、内部的には運が良くても大規模な memmove、運が悪ければ配列全体の再確保が起きると予想される。要素数が1万や10万単位、場合によっては100万単位になる配列では、とてもスケールしないだろう。

本文と同じアルゴリズムで Search(27,2015); とすると、データベースの項目が約8万件になる(件数自体は MaxLimit のチューンで減らせるが、そこは本題ではない)。この例について、DB.indexOf(c)==-1 ならプッシュ…とした場合、テスト環境において全体の実行時間が5秒以上だった。「自己ソート配列」を使うと、実行時間が1.1秒になった。さらに、splice の呼び出しを避けると、0.8秒台にできた。しかし素直に Object のプロパティーをマップ風に使った場合(本文と同じ方法)、同じことが0.1秒未満でできる。

5通りのやり方と、所要時間の例:

DB=[]; if(DB.indexOf(c)==-1) DB.push(c); // too slow (5200 ms)

DB=[]; DB_accept(c); // better but slow (1100 ms/880 ms)

DB={}; if(!DB[c]) DB[c]=true; // much faster (70 ms)

DB=new Map(); if(!DB.has(c)) DB.set(c,1); // ES6 (50 ms)

DB=new Set(); if(!DB.has(c)) DB.add(c); // ES6 (50 ms)

「自己ソート配列」DB_accept(c) の実装は次の通り。

自己ソート配列(17行)

「渡された数が配列内に既存なら何もせず false を返す。新規の数なら配列内のソートされた位置にそれを挿入し true を返す」。例えば:

var DB = [];
DB_accept(5);  // true   DB=[5]
DB_accept(3);  // true   DB=[3,5]
DB_accept(8);  // true   DB=[3,5,8]
DB_accept(11); // true   DB=[3,5,8,11]
DB_accept(8);  // false  DB=[3,5,8,11]
DB_accept(12); // true   DB=[3,5,8,11,12]
DB_accept(6);  // true   DB=[3,5,6,8,11,12]
DB_accept(10); // true   DB=[3,5,6,8,10,11,12]
DB_accept(5);  // false  DB=[3,5,6,8,10,11,12]
DB_accept(2);  // true   DB=[2,3,5,6,8,10,11,12]

前提として、DB を最初に空の配列として生成し、配列の書き換え(要素の追加)を全てこの関数経由で行う必要がある。同じ要素を複数回追加しても、最初の1個しか追加されない点は、Set 風。

function DB_accept( number ) // works ok if DB.length is small
{
    var len = DB.length, start = 0, end = len, index = 0; // DB: array

    while( start < end )
    {
        index = (( start + end ) >>> 1 ); // *0
        var value = DB[ index ];

        if( value < number ) start = index + 1;
        else if( value > number ) end = index;
        else return false;
    }

    if( index < len && DB[ index ] < number ) ++index; // *1
///    if( DB[ index ] < number ) ++index; // *2

///    DB.splice( index, 0, number ); // *3
    DB.push(0); // *4
    for( var i = len; index < i; --i ) DB[i] = DB[i-1]; // *5
    DB[ index ] = number; // *6

    return true;
}

*1 の代わりに *2 と書いても動作するが、その場合、配列の末尾要素の後ろの要素を読んでしまうことがある。結果は undefined(未定義値)だが、仕様書によると undefined は数値としては NaN に変換され、NaN との大小比較の結果は再び undefined。これはブール値としては false なので、インクリメントは起こらない。結局意図通りだが、危なっかしい。

配列に物を挿入する処理は、*4~6 のようなことをしなくても、splice の1行で済む(*3)。普通はそうする。しかし *5 のように自分で1個ずつずらして、空いた隙間に *6 の書き込みを行う方が高速になることがある。Firefox 上のテスト例で、1100 ms⇒880 ms となった。これ自体は(ソートと関係なく)どんな配列にも使える方法だ。ただし、*4 のように先にダミーのプッシュをしないと、逆にひどく遅くなった。ループに入ったとたんメモリーの再確保が起きると、ポインタが全力疾走できずリズムが乱れるのだろう。実はダミーのプッシュを *1 の前で行い、DB.push(number) としておくと、*1 の条件を削った *2 の書き方が安全になる。

しかし、このように頑張っても、伝統的な「オブジェクトのマップ風」より速くならない。配列の長さが10万単位のとき、「マップ風」に勝つには、あと10倍以上速くする必要がある。スケールが拡大すると、ますます負けるだろう。1個レコードを追加するごとに数万件のデータが移動するのは、まずい!

「再割り当てが起きないように最初から巨大サイズの配列を確保して、自分で長さを管理」というのも数パターン試したが、速くならなかった。(ES6 なら面白いこともできそうだが、ES6 でいいなら本物のマップが使える。)

結局「自己ソート配列」が実用になるのは、配列の長さが比較的小さい場合に限られる。常にソート済みなので、使いどころによっては便利だろう。「挿入頻度は低いが、要素の有無を問い合わせる回数が非常に多い」という状況では、意外といいのかもしれない(問い合わせ用のメソッドを別に用意するとして)。

*0 の行の丸括弧は、論理的には全く必要ない。意図を明確にし、優先順位の錯覚による間違いを予防するために付けてある。

整数を2・4・8・16…倍するときや整数を2・4・8・16…で割って余りを捨てるときのビットシフトは、C/C++ では使い古された方法だが、JavaScript の世界では、必ずしも普及していないようだ。sorted-array(参考になる!)では、2で割ってから >>>0 している。Stack Overflow では、2で割ってから parseInt を呼んでいる。Searching JavaScript arrays では「2で割ってから Math.floor」という実装を改訂して、2で割ってから |0 している。

当たり前のことだが、2で割ってからダミーのビット演算で整数型にキャストするくらいなら、割り算せずに右に1ビットずらすべきだ。実際、「2で割ってからビット演算」だと、この例では 880 ms⇒910 ms という速度低下が起きた。CPUが進化した現代でも、相変わらず割り算は遅い

補足

JavaScript の右シフト演算子のうち、

  1. >>> は「内部的に32ビット符号無し整数にキャストした後で、論理シフト」
  2. >> は「内部的に32ビット符号付き整数にキャストした後で、算術シフト」

を行う。これらは「割り算のための演算子」ではないが、以下の用法において、浮動小数点数の割り算より処理が速い:

  1. a0 以上 232 未満の整数で、b0 以上 31 以下の整数の場合、a>>>b によって「a2b で割って商を floor 処理する」のと同じ結果が得られる。
  2. a−231 以上 +231 未満の整数の場合、a>>b によって同様の「割り算」が実行される。「商」は、正負にかかわらず floor 処理される。

シフト実行前のキャストにおいては、正負にかかわらず、端数は切り捨てられる(正の数は floor 処理され、負の数は ceil 処理される)。

付録のまとめ

「西暦・平成パズル」を解くアルゴリズム > 更新履歴

  1. 2016年3月27日: 初版公開。
  2. 2016年4月1日:
  3. 2016年4月3日:
  4. 2016年4月10日: 表現の微調整(3カ所)。

この記事のURL

パブリックドメイン



アドレス = 英語の「クリスマス」の最初の5文字 + アットマーク + faireal.net