記憶法 ランダムアクセスはリストではO(n)であり、配列ではO(1)です． 人の記憶はきっとリストなのでしょう．array = [1,2,3,4,5] list = '(1 . (2 . (3 . (4 . (5 . ())))))手続き言語で書くならば、配列は普通にint[] array = {1,2,3,4,5}であり、（これは誰でも知っている．）一方リストはC言語ではサポート されていないので構造体から自分で作ってstruct list_ { int value; struct list* next; }つまりリストのn番目を見る為には(n-1)回、nextを辿る必要がある． だからランダムアクセスに時間がかかる． 一方配列とはn番目を見るためには先頭からnコ隣を見ればいいと わかっているのでいちいちnextなんて知る必要がない． ある適当な地点から時系列的に追っていかないと其の事象を 思い出せない．その適当な地点、いわばアクセスポイントを多く 作るのが良い記憶術であり、受験科目である歴史の勉強なんか に非常に役立つ． 例えば私はあの人とのやり取りを思い出そうとしても、ただそいつが 全然似合ってなくてヘンな服を着ていたことしか思い出せない． 水色に青色の生地を継ぎ接ぎにしたようなデザインのTシャツで、 たくさんの"power"という白い文字があちこちの方向を向いて プリントされていた．少しサイズが小さいのも凄く嫌だった． どうせ大したことではないけど、しかもたぶん私がひどく傷つく ような出来事が、私と彼女との間であったのだけれど思い出せない．cons = function(x,y) { return function(f) { return f(x,y); }; }; car = function(pir) { return pir(function(x,y) { return x; } }; cdr = function(pir) { return pir(function(x,y) { return y; } };何もしたくないけれどとにかく家にだけはいたくなくて大学に向かった． とは言っても授業を受けるわけでもなく、学習端末室と名を付けられた まるで体を表していないただ24時間開放され学科の生徒がダラけている だけの教室に行ってみたが先輩が数人、ボードゲームに興じているのみで 私のあまり多くない友人はいなかった．知人程度の同級生は数人いたが、 私は別に挨拶だっていちいちしたくもない、ただ漫画を選ぼうと近寄った 時に目があって会釈したに過ぎなかった． さてそろそろ日も沈んだろうという時間になって私は自由に外を出歩く 気分になり、私の目当ての古本屋は自転車でひたすら坂を下る． 古本屋、という文字列から受けるイメージとブックオフと言ってしまった 場合に受けるイメージはまるで違うであろうから正確にメモをする目的 からはその名前を出しておくべきだろう．ついつい見栄えする方を選んで しまう．その古本屋にたどり着くまでに適当なお店をうろうろし、 そのうろうろする為にいちいち自転車をあちこちに違法駐車するのは 非常に面倒だ．ちょっと店を覗く為に自転車を停めて鍵をしては、満足したら また鍵を外し、を繰り返す．ある場所を拠点とし、一旦自転車をそこに停めたら そこからはもう歩いて行動する、というやり方もあるが、それには街は少し 広すぎるし、それに、10Mの距離でも自転車ならば2秒で済むのに、歩くと 時速8キロとしても4.5秒かかってしまうなどという計算を頭の中でしては うんざりする． なんとなく入ったUFOキャッチャーしか置いていないそのゲームセンターで 300円しか費やさずにTシャツを手に入れたのは思わぬ収穫だった． それだけを着て外出するのは気後れするような絵柄であったが．cons :: (N, N) → N 2つの自然数を取って一意に自然数にマップさせることが求められ、 それがただひとつの要件である．例えば def cons(x,y): return y + (x+y)*(x+y+1)/2 これは、横方向を0から始まるxの列、縦方向を0から始まるyの行とする 表を書いて小さいx,yに対するいくつかのセルに、実際にcons(x,y)の値を 書いてみると何のコトかすぐにわかるであろう． それはよく(N,N)の濃度(有理数の濃度といえる)とNの濃度が等しい (曰くアレフゼロ)という説明に良く使われるヤツだ． 先にその表を書いてみせて、それから上の計算式を考えるのが普通だろう． その考える過程で次の性質を発見して、そして利用した cons(x,0) = 1 + 2 + .. + x cons(x,y) = y + cons(x+y, 0) car, cdrはこれを逆算する、満たす(x,y)を探すのである． それには 引数として取る z = cons(x,y) に対して 1 + 2 + .. + x' < z となるようなx'を見つけてから、そして少し調整すればよい． pythonらしいと思われる書き方を心がけてみた． def cocons(z): (x_, y) = [(i, z-cons(i,0)) for i in range(0,z+1) if i*(i+1)/2<=z][-1] return (x_-y, y) 中で再びconsを利用してしまっているのがお恥ずかしい． これを利用して def car(z): return cocons(z)[0] def cdr(z): return cocons(z)[1]その古本屋、乃至はブックオフは6階建てであり、目的はともかく私は 一気に最上階まで行ってそれぞれのフロアを見て1つずつ下の階に 行く事にした．結局コレが一番効率が良いのだ、私の経験則であるが． とにかく目的の物はおぼろげにあるにはあるが、本屋さんの楽しみは なんといっても興味の外のジャンルの本との出会いであろうから、 全ての棚に収められた全ての本の、背表紙に書かれた表題を全て読むぞ という意気込みで、棚と棚、或いは棚と壁によって作られた全ての道を 最小路で歩くことを目的として、ああ、そうだ、もう完全に思い出した． その最上階の割りと初めの段階で、ある棚から抜け出たところでちょうど 彼女に見つかったのだ．しかし彼女はいつの間にここに来ていたのだろう． 瞬間移動じゃないかしら．彼女は私を見てニヤニヤしていて、それがまた 凄く下品に思えた．ここで私を発見したことを誰かに言ったりはしないと 思うけれど．ここでは全ては自然数、である． データも自然数であればconsによって作られるペアも自然数である． 傍目には区別がつかない．一つのペアであることを知らなければならない． >>> cons(32, 100) 8878 8878をペアだと覚えていることで初めて次のコードは意味を持つ． >>> car(8878) 32 >>> cdr(8878) 100 ペアのペアを扱うこともあるだろう． >>> cons(32, cons(32, 100)) 39707383 偶然ペアに入れておきたいデータとペアが同じ自然数であることも もちろんありえて、当然ながら結果としての自然数は一致する． >>> cons(32, 8878) 39707383何もしたくない病気が再発した． 例として、 最近あったことを思い出すためになんでもない日常から書いてみたのですが あまりにくだらないですね．必要のない記憶は忘れるようにできてるです． 試験に挑む其の人は、試験に必要な知識に関してはほとんどO(1)でアクセス できるでしょうし、リスト版のハッシュテーブルになっているでしょう．
コメ(0) | トラ(0)