暇つぶしに教えて!gooで挙げられてた問題を解いてたんだが。
いや、暇つぶし、ってのはウソだ(笑)。単に現実逃避してただけ、だ(笑)。
正の整数に以下の式で繰り返し生成する数列を定義する.n → n/2 (n が偶数)n → 3n + 1 (n が奇数)13からはじめるとこの数列は以下のようになる.13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 113から1まで10個の項になる. この数列はどのような数字からはじめても最終的には 1 になると考えられているが, まだそのことは証明されていない(コラッツ問題)さて, 100万未満の数字の中でどの数字からはじめれば最長の数列を生成するか.注意: 数列の途中で100万以上になってもよい
コラッツの問題、と言う。
まぁ、こんなカンジで質問が投げられてたわけだが。
色々と質問の仕方が間違ってる典型例ではあるんだが。
そもそもプログラミング未経験者が簡単に理解出来るわけがない。それを「説明してくれ」なんつーのは無理ゲーだ。
しかもプログラミング未経験者がC、C++、Javaなんぞを使うな。なんでプログラミング未経験者が「クソムズい言語」を使って理解出来る、等とナメた事を言えるのか。
そして「forで解けそう」ってのは考えとは言わない。当たり前の基礎構文を使う、ってのは当たり前の話であって、思考の結果じゃないんだ。
正直言うと、質問文読んだだけでアタマがクラクラしていた。まるで、
中国語、アラビア語、日本語のどれかで(※1)量子力学に付いて物理学未経験者でも簡単に理解できるように説明してほしい。
と言うくらい不躾な質問だ。
少なくとも、マジメに質問するんだったら、最低の素養でも獲得しろ、ってな話になる。
とは言っても説教はしてない。
っつーか、僕は、大方のこのカテゴリの教えて!gooの回答者が抱えてるような、説教の趣味は基本的にない。
丸投げ族は雨後の筍のように生えてくるし、撲滅は出来ない。「理論的に考えるなら」土台殲滅が不可能、って前提な以上、説教なんざ意味がないんだ。他人に説教するのが快感で趣味、ってぇんでもなければね。
そしてそういう暇人は実在する。
ところで、上でケチ付けたような事を書いてるんだけど、このテの問題、ってのはどのみち、どの言語で解くとラクなのかと言うのがハッキリ出てくる問題なんだ。ラクな言語を使えばラクに解けるけど、そうじゃないと悲惨な目に合う。
個人的な考えだと、C/C++/Javaを選択した時点で難易度がメチャクチャ上がるわけ。そして問題の本質がブレる。
言い換えると、C/C++/Javaを選択する、ってのは選ぶ武器を間違えてる、って事だ。
そもそも、この辺のProject Eulerの問題は厭らしくって、力の弱い、C/C++/Java辺りだと簡単にオーバーフローしたりセグメンテーションフォルトを喰らうようなデカい数値を持ってきてて、一見数学の問題に見えるが、実際は「実装法」の問題にすり替わってしまう。
出題者側のそういう意地が悪い意図は避けるのが賢明なんだ。
そしてC/C++/Javaはいつもそういう問題が付きまとう。いっつも言ってるけど、アルゴリズムの「ロジック」そのものと、言語の弱さの問題で複雑な実装をせねばいけない、って言うのは全く別の話なんだ。
特にプログラミング初学者はロジックはロジックで理解出来、そのまま書けるような言語を選択すべきだ。
じゃないとロジックと全く関係ないトコで足をすくわれてしまう、って事なんだよ。
この問題のプログラムの難点は、どうしても再帰絡みになる、って辺りで、スピードを得る為には必要な再帰以外をどうやって避けるのか、ってのが実装上の問題となる。つまり、不要な再帰を避ける仕組みが必要になる。
ところで、いくつかコラッツの数列を手書きででも計算して並べてみよう。
1 -> 1
2 -> 2, 1
3 -> 3, 10, 5, 16, 8, 4, 2, 1
4 -> 4, 2, 1
5 -> 5, 16, 8, 4, 2, 1
6 -> 6, 3, 10, 5, 16, 8, 4, 2, 17 -> 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1
コラッツの問題は未解決問題で、全ての整数に於いて最終的に1に収束するのかどうかは分かっていない。
しかし、少なくとも、既知の範囲では1に収束することが知られている。
もっとパターンを良く見てみると、数列の「途中」から既存のパターンになってる、って事がわかる。
例えば2は2, 1と言うパターンで、3は、3, 10, までは新規パターンなんだけど、それ以降は5が形成するパターンになってる。6が形成するパターンは6が3が形成するパターンに接続されてる。
つまり、既知の範疇では、「新規の数が出てきてもどっかのパターンに接続されてる」と言う事が言える。また、仮に新規パターンが出てきたとしても、先頭の数値が「今まで出てこなかった」場合、その数値が形作るパターンを「先読み」可能だ、と言う事だ。
例えば3が形作るパターンは、3の次の数は10になっている。って事は3の次の数は自然と10が形成するパターン生成を意味してる。って事は10を計算する前に「10のパターンを」知る事になる、って事だ。
言い換えると、プログラミング上、パターンを何かに順次登録してしまえば無駄な計算は全部省ける、って事になる。
要は数値が出てきた時、未知のパターンが出てきた場合には計算して登録、そうじゃなければ参照だけすれば良い、って事だ。
7はこういう先頭を持つパターンで成り立ってる7 -> 7, [22, [11, [34, [17, [52, [26, [13, [40, [20, 10, 5, 16, 8, 4, 2, 1]]]]]]]]]つまり、この時点で22、11、34、17、52、13、40、20、が形成するパターンを知った事となり、これらの数が今後出てきても再計算する必要がない。
このテの場合、一番単純なやり方はメモワイズを使う事だろう。ハッシュテーブルの力を借りて、整数をキー、形成するリストを値としてテーブルにガンガン登録していくんだ(※2)。
当然、この問題はLisp辺りじゃハナクソをほじってる間に書ける。
例えば、Racket辺りならこういうコードになるだろう。
(define (collatz-seqs n table)
(if (hash-has-key? table n)
table
(let ((key (if (even? n) (/ n 2) (add1 (* 3 n)))))
(let ((table (collatz-seqs key table))) ;; ここで再帰
(hash-set table n (cons n (hash-ref table key)))))))
(define (euler14 n)
(caar (sort (hash-map
(foldl collatz-seqs (hasheqv 1 '(1)) (range 2 (add1 n)))
(lambda (k v)
(cons k (length v))))
> #:key cdr)))
これは実はまだ非効率的なんだけど(と言うのも完全に関数型プログラミングにしてる為だ・※3)、コード自体は大して負担にもならず書ける簡単なモノではある。
計算も、数がデカい為、アッサリ、とは言わないが、キチンと結果を返してくれる。
つまり、100万以下だと83万7799と言う数が最長のコラッツ数列を返す、って事だ(ちなみに、その長さは525で、そこに現れる最大値は29億7498万4576だ)。
ところが、Lispで書けば簡単なこんなプログラムでもC/C++/Javaで書くと一筋縄じゃイカんのだ。ハッキリ言えば、書けるかどうか分からん。
いや、苦労すれば書けるんだろうけどよ。少なくともJavaやC++で書こうとしたら上手くイカんかった。で、諦めた、ってワケだ。
C++もJavaも関数型言語の機能を取り入れてはいる。が、実際のトコ不格好過ぎるんだよな。使い勝手が悪い。直感に反する。
しかも先程書いた通り、そもそも扱える数値に限度がありすぎる。事実、上で見せたが、引数が100万の時、最大の長さを持つコラッツ数列の最大値は30億に近いが、引数100万以下の全コラッツ数列で現れる最大の数値は569億9148万3520だ。long long型を使え、とでも言うのか。long long型なら最大値が922京3372兆368億5477万5808だからな。
しかしちと待て。そもそも上で、Racketで試したから最大値がわかるわけだ。いきなりC++やJavaで書いても「そんな数値が最大値」なんてどうやって知るんだ。わかるわけねーだろっての。
しかも特にJavaだが、Javaは再帰が苦手だ。Python並に苦手だ。従って、本質的に要再帰なアルゴリズムは書けない。すぐスタックオーバーフローを起こす。馬鹿野郎。
C++も作ってみると大して速くもないし、Racketに比べても遅いわ安定せんわ。ダメだ。少なくとも俺如きのプログラミング技術じゃどうにもなんねぇ。
結局やってみると、Lispが一番速くて一番安定してんだっての。マジだよ。ロバストで高速。マジでC++やJavaが到達しない安定性を誇る。Lispで作ったモックアップが一番信頼性が高いんだ。
図らずしも、グリーンスパンの第10法則を改めて実感しちまった、と言う話だ。
十分に複雑なCまたはFortranの プログラムは全て、後付けで、正式な仕様がなく、バグがてんこもりの、 遅い、Common Lispの半分の実装を含んでいる
ここにC++やJavaを付け加えても良い(※4)。
Lispマジ最強。
※1: あるサーヴェイによると、世界で最も学ぶのが難しい言語の一位は中国語、続いてアラビア語、日本語らしい。
と言うことは、日本語は自然言語界のJavaなのか(笑)。
※2: この役目を果たしたのがcollatz-seqs関数だ。
例えば引数に11を与えると、11から形成される経路の全て(いくつかの数値からスタートするコラッツ数列のリスト)を一回で取得する。
よってここで取得された全ての経路は再計算される必要がない。
これを生み出すのが再帰なわけだが、初回計算時にはこのように、それなりに再帰のコストがかかる。
しかし、同じ値の再計算を妨げて、全体の計算量負荷を減らす、と言うのがメモワイズのポイントとなる。
※3: 実用的には、ハッシュテーブルは大域変数として作成し、データを破壊的変更をした方が効率はいい。元々ハッシュテーブル自体は「破壊的変更前提の」データ形式であり、性質指向的にはリレーショナルデータベース等にむしろ近い。そしてそれが意味する事は、関数型プログラミング向けの存在じゃないんだ。
もう一つ言うと、foldlを使うと言う事は新たなハッシュテーブルを常に生成し、置き換える、と言う事だ。と言う事は廃棄されたハッシュテーブルを回収する為にLispのガベージコレクタがメモリを綺麗にする為に走り回る。このガベージコレクタのコストがかかるんだ。
一方、ハッシュテーブルを破壊的変更するなら、新しいハッシュテーブルは作られないし、ガベージコレクタも走り回らない。
ただし、Scheme系言語の場合、コーディング的には破壊的変更をするコードは書式にペナルティがかかるように見える。破壊的変更は値を返さないんで、値を返す際にはどうしても書く行が1行増えてしまう。
よって、コーディングスタイルとしてはどうしても、実行効率より見栄えを重視すれば、Scheme系言語では「関数型プログラミングで書く」方がスッキリする。
そして自己満足にせよスッキリする誘惑にはなかなか抗えなかったりするんだ。
ただし、関数型プログラミングスタイルのコードでもコンパイルすれば最適化により実行効率が落ちない可能性は常にある(要するにコンパイル時点でコンパイラが「破壊的変更」に置き換えてくれる事がある)。
インタプリタで非効率なコードでもコンパイルで「無駄が省かれる」と言う事も良くあるので、この辺、結論としてはちと一概には言えない辺りが悩ましいトコだ。
※4: C++を、洒落だとしても、いっつも書くのに苦労するが、一方、この問題で「ここまで上手く動かない」とは思わなかった。小さい数値なら計算出来たので尚更、である。
ちなみに、最初は、データ型の扱いでJava有利か?とか思ってたけど、そんな事はなくって、相変わらずJavaへの信頼度は最底辺である。
