今日の3限後半はアルゴリズムとデータ構造の中間テストだった
その解答・解説を4限に行っていたのだが…
自己採点結果: 72点
ものすごぅく痛い, かなぁり残念な結果になってしまった…
乞う, 中間点!!
本日の5限は南棟中演習室1(4F)J41にてScheme演習だった
既に遠い昔にほろ酔い気分で課題は終えてあったので先生, 本当に申し訳ございません勝手に『あしぇんぶりゃ』をやっていた
ちなみにその『あしぇんぶりゃ』の課題はマルチワード用の加算器と乗算器を作るというものだった
加算器の方は終えていて, 乗算器の方も(ｎ-words) x (n-words) = (2n-words)を実装, 課題ではn >= 4ならnを固定しても良いn個の(n + 1)-wordsの数値を足して2n-wordsの数値を作る部分を作れば完成, ようはumul命令九九表を使って式の下に因みに1-word進数での話, 人間には出来ないなぁ…1桁 ｘ ｎ桁の結果の羅列を作るまでは出来ていたんであとは最後の足し算を実装, でもこれは計算機システムの時間ではなくてアルゴリズムとデータ構造演習の時間…時間中に完成
とりあえず実装は終わったので他の人のdequeueを見る, その実装ではありえないであろう実行時のものではなく, 循環参照のこと無限ループが発生していたりと色々面白い実装が見られました
Environmentのエミュレーション?実装をリストではなくAVL木でやろうとするつわものがIS日記メンバーにいたりして…狐には全く出来そうにありません…というより絶対にやりたくないです, Schemeで木なんて
J41閉室時間になったので舞台は南棟大演習室1(2F)J21へ…
そこでも他人のdequeueを見てたり…
他人のEnvironmentの実装を見てたり…
他人の『あしぇんぶりゃ』を見てたり…lレジスタは0～7まで, 因みにiとoは0～5だったはず(6かも)%l8なんてレジスタはありません
恐らくあれはメモリ上のものを読んでから加算処理をやらないとレジスタは文頭で『恐らく』と使っておきながら…絶対に足らなくなります
別にmovを散在させてその中で各桁を入れてもダメなわけじゃないですけど…
とりあえず加算器の方はループを使わない4-words固定のものを完成できるように誘導, 自分のやつと考えはダブっているけど, 個性が出るのはループ時の処理なのでループを解いたVersionぐらいは教えてもまずくはあるまい
因みに何でループ処理に個性があらわれるかは以下に示しておこう
(激しくネタバレ要素ありです, 本当に困った時か完全にループ版の実装を含, 『諦めた(涙)』終えた時に見るようにしましょう)
ループはxxxcc(ICCを書き換える命令群)とbxx(ICCの状態で条件分岐する命令群)で実装する
つまり加算時に記憶しておきたいICCはループ処理で失われてしまうことになる
これの回避策としてどのような実装を施すかが今回の課題のもっとも個性が出せる点だろうと思われる
何故加算器の基本的な, コアともいえるような部分を教えたかというと, それができないと絶対に乗算器など作りえないからであって, ここは助け合い精神であれなんであれ頑張ってあと2年間は同じ学部で苦楽をともにする以上, このぐらいは出来たことにしてくれないと困る?乗り越えて欲しいからである
はっきり言って, 乗算の方が加算より3倍は難しいと思います
実装方法のヒントは上の方で言ってしまっているかもしれませんが, まぁ見逃してやってください > TAの皆様
あと, Yレジスタの扱い方を聞いたところYレジスタを使わないで実装しろといわれた人がいるみたいですが聞かなかったことにします
直接クラス全体に言っていたわけでも狐自身がそういわれたわけでもないですのでね…
とりあえずこれから管理人の酔いどれ実装と違って面白い形, 残念ながら実装はまだ完成していない様子新堂さんのdequeueの構造を使って実装を考えてみたいと思います
早速解いてみたんですが, front-delete-deque!がOrder-1で構造上実装できませんでした
もっともデータ構造自体うろ覚えでやっているのでその辺に起因する問題なら仕方ないですが…
でもやはり循環参照するリストでない限りdequeueは実装できなさそうです
∵) リストがfront-delete-deque!とrear-delete-deque!を同時にO(1)で実行できると仮定する
ここで『要素の先頭』とはdequeueの各要素を構成する複数のセル全てにO(1)で到達できる要素(複数でしか全てをさせない場合はその全て)を指すことにする, 納得がいかないならば, これを要素を構成するセル全てのセットと読み替えても差し支えないこのような要素(もしくは要素の組)が存在することはO(1)でその他のリスト操作も含むfront-delete-deque!が複数回実行できることより明らか
front-delete-deque!がO(1)で実行できる必要条件として, リスト長に関わらず, 一定オーダーの計算で先頭から2番目のリスト要素の先頭に到達できなければならない, これは削除後にも言えることなので, ペアが無限個の要素をむしろcarとcdrしか保有できない同時に保有できないことから, これらは一定の規則で並んだリスト構造をとる必要がある
よって各要素の先頭はその次の要素の先頭に到達できる
逆にrear-delete-deque!がO(1)で実行できることより, 同様の論証を持って各要素の先頭は前の要素の先頭に到達できる
以上のことを隣接する2要素について当てはめるとその間に循環参照があらわれている
よって, 循環参照がない構造でfront-delete-deque!とrear-delete-deque!を同時にO(1)で実装することはできない
結構思い付きで書いたので, 多少論証が弱いところもあるかと思いますが, 多分新堂さん方式では循環参照がなくて本当に美しいデータ構造になってるのですが…残念ながらfront-delete-deque!がうまく実装はできないでしょう
できればこの証明もどきの反例を見つけてみたいのですが…聖狐には無理そうです
結論に達したところでSchemeの復習をやめることにします