巧妙なアイデア「ふたまたニョキニョキ」がすべてを解決する【データ構造2】#49
Вставка
- Опубліковано 21 лип 2024
- 「データ構造」シリーズの第2回。「データ構造におけるふたまたニョキニョキは二分探索木」「木構造で素早く社員を見つける方法」「シンプルなルールから豊かなものが生まれる」など、二分探索木の仕組みから実用方法まで話しています。
【目次】
0:00 いいルールは厳しい？甘い？
1:39 ふたまたニョキニョキの前におさらい
4:56 データ構造にもふたまたニョキニョキ
6:04 トレードオフの最適解「二分探索木」
8:17 ファイルの中身をぶら下げていく？
16:36 ハフマン符号化に自力でたどり着く
19:12 ふたまたニョキニョキはどれだけ優秀？
23:58 社員のファイルを木構造にする方法
28:11 C言語がポインタを扱う理由
30:19 ふたまたニョキニョキは何パターン？
34:27 ちょうどいいルールが豊かさを生み出す
45:31 みんなも聖書を読もう
【参考文献のリンク】
○アルゴリズムとデータ構造
amzn.to/3FJSIsN
聖書。非プログラマーが読むのはややキツいが、絶対古くならない名著。
【サポーターコミュニティ加入はこちらから】
yurugengo.com/support
【親チャンネル：ゆる言語学ラジオ】
/ @yurugengo
【フランチャイズプロジェクト：ゆる学徒ハウス】
/ @yurugakuto
【おたよりフォーム】
forms.gle/BLEZpLcdEPmoZTH4A
※皆様からの楽しいおたよりをお待ちしています！
【お仕事依頼はこちら！】
yurugengo@gmail.com
【堀元見プロフィール】
慶應義塾大学理工学部卒。専門は情報工学。WEBにコンテンツを作り散らかすことで生計を立てている。現在の主な収入源は「アカデミックに人の悪口を書くnote有料マガジン」。
Twitter→ / kenhori2
noteマガジン→note.com/kenhori2/m/m125fc452...
個人UA-cam→ / @kenhorimoto2203
【水野太貴プロフィール】
名古屋大学文学部卒。専門は言語学。
某大手出版社で編集者として勤務。言語学の知識が本業に活きてるかと思いきや、そうでもない。
#データ構造 #ゆるコンピュータ科学ラジオ
【参考文献のリンク】
○アルゴリズムとデータ構造
amzn.to/3FJSIsN
聖書。非プログラマーが読むのはややキツいが、絶対古くならない名著。
【サポーターコミュニティ加入はこちらから】
yurugengo.com/support
【おたよりフォーム】
forms.gle/BLEZpLcdEPmoZTH4A
※皆様からの楽しいおたよりをお待ちしています！
水野さんめちゃめちゃコンピューター科学の素質あって羨ましい
ひらめき方がパンピーじゃないんよ
↓これ1番好きな数学ジョークですw
Q.フラクタルの提唱者、Benoît B. Mandelbrot (ブノワBマンデルブロ)のBはなんの略?
A. Benoît B. Mandelbrot
Benoît (Benoît (Benoît (…). Mandelbrot). Mandelbrot). Mandelbrot
水野さんがでかいイメージあるのは実際に会ったことある人だけで、ラジオ動画見てる人だけだと水野さんと堀元さんの身長差に驚くのよ(n=1)
ua-cam.com/video/ugPrgVrR6ag/v-deo.html
これで分かる
コメの高評価の数はサンプル数かな？
自分も押しとこ
ゆる言語学かまいたちペアですね
ランダムな数字を一日中叫ぶ続けることができるランダム部長は相当に優秀な方ではないかと。友達になりたいかどうかは別にして。
このコメントを見て本当にランダムならSCP-4559みたいな使い方が出来そうだなとか思ってしまった
創発かは分かんないけど、洗濯バサミをつなげて複雑な形を作ったことは誰しもあると思う。
なるほど！この番組からパフォーマンスよく知見を得られるのは、厳密コンピュータ科学ラジオでも無秩序コンピュータ科学ラジオでもないからなのですね！
堀元さんが後半の水野さんの抽象化から、データ構造のまとめに戻さずに「創発」までもってくところで、脱線のほうの枝を優先していることがこのラジオのおもしろさをつくっているルールなのだ感じた。
@@aqua372b ありがとうございます。
堀元さんの何となくでランダムに出てきた数字が128ページでしっかり2べきなの、コンピュータサイエンス学徒みが強くて良い
「二分探索木の話じゃなくて木の話だ」の部分、堀本さんが言語学ラジオの方でいってた「塹壕の中に無神論者はいない」に対するジェイムズ・モロウの「それは塹壕の話であって無神論者の話じゃない」を呼び起こして一人でふふってなる
堀元さん、水野さんが喧嘩することなく、これからもずっと仲良くいて欲しいなあ
水野さん予想通り自力でO(log n)にたどり着くの流石ですね。
最悪値についても余裕で気づくと思ってましたｗ
39:25
たぶんだけど水野さん、数列の一般項とか決め打ちした後数学的帰納法で証明するタイプ
ランダム部長が連続する数を叫んだときはテンション上がるよね
水野さんと堀本さんの身長の勝手なイメージが真逆でびっくりした
本質ではないと思いますが、31を32に、32を33にコピーすると全部同じ値になってしまいます（移動のつもりで間違ってそのコード書いた事あります😅）
メインフレームでは0クリアや空白クリアで使うロジックです。
逆に動かさないと移動にはならないの、一回はやるよね。
@@hiroya1192 それは聞いたことないな。Fortranでは配列定義後の初期化はデフォルトですし。全部クリアなら配列取り直すだけで自動的になってくれます。
ほんとうだw
基本情報技術者の試験に出てたな、こういうミス
水野さんの記憶力すげー
いつかデータ圧縮の回をやる時またハフマン符号化に自力で辿り着くかな 楽しみ
アルゴリズムの本読んだときに二分探索が出てきて、だから？となったけどその有用性がなんとなく分かった！ 文系人間としてはこういう話がありがたい！
相変わらず楽しそうでなにより
ニコニコしながら見てます
文系と理系の垣根を越えてくるの、好き～
シンプルなルールが複雑な物を生み出す、って示唆良いですねぇ。
スゴくシンプルなルールで行動する小さなロボットを大量に集めたら、アリ見たいに餌を集めるロボットの群れができたって話を思い出した。
楽しみに待ってました
ポインタに一旦引っかかった人でないと、ポインタの威力って伝わらないかもな～。
とてもいい解説でした！
身長１、２、３ｃｍのやつを与えられた時の水野さんの表情の変化、めちゃめちゃ良かった。
個人的には一番グッとくるデータ構造はスタック。
木構造の深さ方向の探索を見事にメモリ上に落とし込んでいると思う。
なによりスタックへの積み下ろしで、コンパイラーやCGの座標変換などが同じような抽象化で扱えるのが気持ちいい。
ふたまたにょきにょきは天才の発想
スタックは再帰的呼び出しの時に超便利。終了判定をスタックに積み残しがあるかだけで判定出来て、イチイチ比較演算とかをしなくて良くなる。
カードゲーマーがプログラムを学ぶときになぜか知っていることでお馴染みのスタック
現在の台本では飽き足らず、未来の台本までブレイクし始める水野氏、応援してます
うーん、今回も面白かった。「ふたまたニョキニョキという中庸なルールが挿入と探索の両方に有用」を切り取って、動画のメインテーマにするという堀本さんのプランニングセンスにまずは脱帽です。
14:39 より厳密には
水野さんの右側の子は全て水野さんより大きい
ではなく
水野さんの右側の子孫は全て水野さんより大きい
かと思います。
子: 直下
子孫: 子をたどることで到達できる
ゲームブックを思い出した。
各ページにストーリーと選択肢があって、選択肢ごとに何ページに進むか違い、選択によって展開と結末が変わる本。最近あるのかな。
意外とでかいことでお馴染み水野
計算機科学でポインタという時はCのポインタを指すのではなくて配列の添字や例えの中のページ番号のようにデータに即座にアクセスするための値を指す抽象概念だったと記憶しています。Cのポインタはそれを目指してはいるので無関係ではないですが。
で、CのポインタはCの初学者が躓く最大のポイントだけど配列の添字は初学者が躓くことはあまりないので、Cのポインタの学習を阻害する難点は抽象概念のポインタとは関わりが無くて、おそらく型付けがゆるくてポインタがちゃんとポインタでない（型を間違えるとデータの途中の無意味なアドレスを指してしまったり、扱いを間違えると何のデータも指さない無意味な場所やメモリ空間上に存在しない場所を指してしまう）事が問題なのだと思っています。
なので、計算機科学を学ぶにおいて必ずしもCは適切な言語とは言えないしポインタを理解するのにC言語のポインタを学ぼうとするのは非常に非効率なのではないかと思います。
C言語のアレは「アドレス」だからｗ
機械科学生の頃のCNCフライス実習のコード入力で指導員の方から「1行目の次は11行目、その次は21行目というような書き方にしてくださいね」と言われ、理由は「ミス修正時にコードとコードの間に新たなコードを書き足しやすいから」でした。
今回の話と似てるかな〜と思って聞いていましたが、工作機械のコンピュータとは全然違って面白いですね。
CNCプログラミングではNコードという行番号を指定する機能と、GOTO文があるのですね。
実は、昔はFORTRANやBASICといった、用途を特定しないプログラミングに使われる言語（汎用プログラミング言語）でも、行番号とGOTO文を使って、プログラムの制御構造を表現していました。特に、昔のホビーパソコン（マイコン）のBASIC処理系では、行番号を指定している場合は行の編集、指定されなかった場合はコマンドの即時実行といった仕組みのラインエディタが使われていて、全ての行に必ず行番号を付す必要があったこともあり、行番号を10ずつ飛ばして入力する作法は同様でした。
しかし、その後に登場したプログラミング言語では、読んで分かりやすい名前（ラベル）に対するGOTOや、構造化プログラミング、関数の呼び出しといった制御構造が使われるようになり、行番号は使われなくなりました。
BASICの行番号がコンピューターの内部でどうやって管理されていたか探したところ、 ngs.no.coocan.jp/doc/wiki.cgi/TechHan?page=3%BE%CF+BASIC%A4%CE%C6%E2%C9%F4%B9%BD%C2%A4 が見つかりました。図2.11 テキスト格納形式 を見てみると、各行が「リンクポインタ」でつながった構造になっています。木構造ではないですが、ポインタを使って、行を簡単に抜き差しできるようになっていることが分かります。
それは、パンチカードという１行単位でデータを入力するときの名残ですね。
初期BASICにもRENUMという各行の行番号を10単位に揃えるコマンドがありました。
ワークショップデザインとかでも、問いの立て方として、ある程度の制約のある問いの方が場が活性化する、って言うのと同じ話ですね
18:08 水野さんが台本ブレイカーとして圧倒的な成長を見せた瞬間
19:56これどうやって計算してるんですか？
22:30そうか、どっちに行くかを計算するんだから二択だ、、
僕も数学得意だけど、理科苦手なタイプなので、水野さんに親近感を感じています
とてもどうでもいい指摘ですが、新自由主義はケインズではなくフリードマンかハイエクですね。この2人はケインズと対立していたので思想としては逆です。
新自由主義自体レッテル的な要素が多い言葉なのでこの2人に使うのも微妙ですが、、、
細かいことを指摘してしまい申し訳ありません。
お二人のご活動、陰ながら応援しています。
ハフマン符号化の話は詳しく分かりませんが、二分探索木を実装する際には01の組み合わせでデータを保存するので、素晴らしい着眼ですね
この話が終わったらセグ木やBITの話をして、それらの木とコンピュータとの相性の良さを語るのも一興ではないですか？
すごい面白いｗ
メモリ効率を厳密にするなら確かに二分木が最強になるけど
メモリを潤沢に使えるならハッシュテーブル最強なので
そこまで踏み込んで第3回をやって欲しいぜ！
シンプルな規則が複雑性を産む、という水野さんの話からバッカスナウア記法の話とかが始められそうですね！
ニョキニョキの描き方は最初を何にするかで形が全然違ってくるというのは、地図の正距方位図法が中心地点によって形が全然違ってくるのに似てますね。ニョキニョキも正距方位図法も元は同じものだし、全て同じやり方で記述しているのに。
正距方位図法で地図を描いてくれるサイトがあるんですが、ぐるんぐるん動いて面白いです。
知識はハッキリとクッキリしたものであって応用はきかないが、知恵は緩やかに境界があいまいなもので捉えどころがないだけにいかようにもコントロールできると生徒たちには言い続けていますが、それと同じことがコンピュータサイエンスでもあるのですね。それを「やじろべえの精神」と生徒諸君には言っています。
ヒープ構造なんかだと左右の子はそれぞれ自分の番号*2+1(2)のアドレスに格納されるので、水野さんの言うハフマン符号的な考え方と殆ど同じなんじゃないでしょうか？
同じこと思った
大小を比べて並べると丁度良いんですね。素晴らしい。
水野さんすげー
木の通り数は、共通テストに出ると噂のカタラン数ですよね！なんでカタラン数になるかは知らんけど。
水野さんが将来の木の回で自力でカタラン数にたどり着くのが楽しみです😄😄😄
ゲームブックって、ランダムアクセスしてたんだな…
探索も挿入もしやすい！すげぇ。
最初に取り出す値で木構造が変わることは理解したのですが，データを削除・挿入した際に木構造を組み直す(最良を目指す)ことはするのでしょうか。
アップデートってそういうこと？
平衡木と云うのがその考え方
まさにそのとおりです
32:00のような長細い木だと最大で2回分岐をたどる必要がありますが、
32:20のような木だと分岐が1回で済むように、なるべく木の階層の数を小さくするほうが効率が良くなります
削除・挿入時にルールを追加したり、木を組み替えることで効率の良い状態を維持し続けるアルゴリズムがあります(平衡二分探索木と調べると出てきます)
めっちゃ学びがあるコメントモメント！
そこでゆる言放り込んで意味も通ってるの凄い
二分探索木は回転で簡単に整列できるのが良い所なんだなぁ
16:41
素人からすると良さそうに見えちゃうの凄い分かる。
ランダムアクセスできる人とファイルより，マンションの集合ポストとかのほうがわかりやすい例えだったりしないかな…？（人間的にもある程度ランダムアクセスができるので，想像しやすそうかなと）
二人ともめっちゃ頭いいから面白い
30:32 ああ、それでいいんですね… このデータ構造を学んだとき、「あれぇ…データの入れ方で並び方変わるのでは…?? どうやって整列させるんだろう…??」と思っていました
7:11 Wikipediaは(二分木、二進木も)「ぎ」でした。
二分木は「ぎ」の一択だと思います「き」だと二分岐と同音になり同じ文脈で出てくるので混乱するから。
-き だと「器」とも紛らわしいからですね。分類器とか生成器
水野さんボケ倒してておもしろい
トレードオフと創発の話、いつかシステムアーキテクチャ回でがっつりやってほしいです
11:02 計算機科学では木は下向きに生えるものだから......
Knuth先生もTAOCPの中で木って呼ぶわりに下向きに生えてるの不思議だよね（上に伸びていく図になるのが自然）と仰っていましたね。
計算機科学から入るとシャバの感性が分からなくなって「木＝下に生える」という常識が形成されてしまうのはCSあるあるなのかもしれません。
そう考えたらどっちかってっと根っこだよな
この流れで再帰の話題も取り上げてほしい
12:40 チェが苗字でホンマンが名前だから「ホンマンって呼ぶな」ってツッコミは結構シュールな気がするｗ
一般的に、チェ・ホンマンさんをチェで呼んだりホンマンで呼んだりしないよねって話じゃないですか？
チェ・ホンマンさんの母国の人からしたらシュールそうですけどね
まあ外国でNo.1有名日本人の織田信長も「信長」と呼ばれてますしね。
ホンマン呼びは韓国では普通です。
毛沢東を沢東と呼ぶ的な。
かつての冬ソナブームのとき、ペ・ヨンジュンと結婚したら苗字がペになる問題ってのがありましたね
ぼやーんとしてよく分からなかったけど、この例え分かりやすいかも！
39:49 この辺の話で
競走馬シミュレーションゲームのダービースタリオンを作った園部さんっていう人がいるんだけど
この人がシリーズが進むにつれて競走馬のパラメータってどう増えて言ったんですか？みたいなこと聞かれて
増やしてませんよ、むしろ減らせないかって常に考えてました
パラメータが単純だから多種なバリエーションが生まれる 増やしてしまうと固定化されてしまうって言ってたの思い出しました。
二分探索木の概念、意外なとこに意外な観点が潜んでるのだなぁ、と思いました。めくるめくわ。
ラングトンの蟻は、UA-cam動画でもいろんなの上がってて面白かったですが、単純に一方向に伸びてくようなのだけでなくかなり複雑な図形を描くものもあるみたいですよ。
（その分パラメーターの取り方とか複雑になっているのかもしれませんがちょっと私もそこまではわかりません。）
話はズレますがラングトンの蟻って、原始の有機物の様々な組み合わせの試行から生命が生まれたり、ビッグバン以前の混沌の中から今の光とか時間とか重力とか物質とかいった言ったものを定義するこの宇宙の物理法則が生まれたこととか、そんな過程を垣間見れるような現象のように思えてゾクゾクしてしまいます。
これって同値のデータが来たときどうやって処理するんだろう？
分岐をもう一個増やしてくっつければ処理できそうだけど、それだと二分探索木じゃない気が…
右左のどちらかに入れてあげればいいだけだと思いますよ〜。なのでもし同じデータが連続する場合左右に偏ることになって探索の最悪計算量がO(N)になっちゃいます😢 なのでそこを工夫した平衡二分探索木というものがあったりします。ご興味があればぜひ調べてみてください！
水野さん185cmぐらいかなと思ってたけど178なのか、 結構ヒール高い靴履いてる？
実際には187cmです
ふたまたニョキニョキのときは
対象データが正規分布である。最初のデータが中央値に近いデータサンプルのときに、最も効率的な探索ができるってことですかね？
例えば正規分布でも初回データが中央値から離れてたり、分散の度合いが平均値からズレて山が複数出たりすると、偏りが木の分かれ方で多段数が部分的に増えるとか…？？？
表現が正しいかだいぶ怪しいですが…
統計やDBの入門を勉強しようとしててリレーショナルの時と、じゃあ二分探索木がNoSQLで違い出てくるのかなぁとか、色々考えちゃいました…
今後も動画楽しみにしてます！
二分木、むかーし昔に某タゴラ某イッチの作者によるプログラミングについての特番で知ったなぁ すごくおもしろかったけど録画がVHSだったからもう見る手段がない…
16:37 二分木を配列で扱うときの話としては本質な気がする
理系の人桁数のことオーダーって言うよねっていう薄い認識が補強されてよかった
機械工学科学卒の会社員で、面白く視て聴いてます。私は「出たー」＝二人で伏線回収するヤ・ツーと見ています。 今回の巧妙な考え方「ふたまたニョキニョキ理論」ならぬ、【二分探索木】が、チョムスキが提唱した「ふたまたニョキニョキ理論」でなく【Xバースキーマ】理論の、特徴の一つ：句カテゴリの構造は全ての接点で「二股」に枝分かれすること：二股分かれ の原理 (binary branching principle)（他にも: 句構造は必ず句の核（主要部; Head）をもち ；主要部側とそうでないものとを二分木を利用して表現できると仮定する）と似ていて、「出たー」と脳がいっぱいアドレナリンを出して、興奮しています。
19:50 理想的な配置での話であれば、ノードは終点だけでなく各分岐にも存在するので最大13回では？
実際には最大9999回ですね。全部最初より大きいのを挿入していったらそうなる。
現実的には13の2倍以内くらいのパフォーマンスになるかと思います。
@@HitUA-camコメ主さんは分岐の偏りがない理想的な配置の話をされてますよ
ちょうど二分探索木が課題だったから助かる
単純なルールから複雑な構造が出るの ライフゲームだ！となった
創発の話はオートマトンとかの複雑系に近いのかな
ページの左下や右下には、常にそのページの人よりも新人がくるから、182ページの左下に7が来ることは無いのでは
182よりも大きい数が来る気がする
ある程度データが揃った後に木を組んでる想定だと思いますよ(たぶん判ってて言ってるとは思うけど…)
@有識者
16:55
ハフマンツリーのてっぺんって、動画だと1だったけど、0でもokなんですか？
もちろんokです。理論上はどちらでもいいのですから。
しかし実装にあたっては1スタートだと便利なのです。
例えばpythonで実装するとき, 1-indexed なら子 i の親は i
水野さんの最後の気づきがあったのなら、もうライフゲームをやるしかないですね！
つまり……社員のファイルをゲームブックに変えてしまえばいい……ってコト！？！？
03:37
>31番のデータを32番に、32番のデータを33番に
それだと31番以降は全て31番のデータになってしまうじゃないですか！(という細かいツッコミ
データ末番から31番までの順番でデータをコピーしていかないとからないのです……
にぶんたんさくぼく、かと思ってた。
全くの素人なので恐縮なのですが、社員ファイルに身長と体重が書かれている場合には二分探索木以外のデータ構造で扱うということでしょうか？
身長の問題と体重の問題の双方に答えるのが目的であれば、木を2つ作ればいいかと思います。
検索は今まで通りできますし、追加の計算量は２倍ですが、定数倍なので変わらずΟ(logn)です。（ノードの中身を社員情報へのポインタとすれば、データはほとんど増えません）
つまりある程度の制限があったほうが創造性が刺激されるってこと？
水野さんの結論，複雑系科学の本質ついててすごい
最終的には本体は順番に追加して行って別途五十音順、身長順、年齢順など検索したい条件ごとの索引を用意する何とか大辞典が正解と。
ポインタのすごさって
メモリに格納できる範囲のデータサイズのときだよね、直接指定できる凄さの認識あっているのか不安になる…
数十万人のユーザ情報を全部メモリに乗せるのは難しいのかなと。これは当然DBですよね。
それとは別に何か情報参照する上で、判断基準となる表があって、1Gバイト程度であればメモリに全部乗せてしまって、
直接参照したほうがストレージにあるより早く処理ができるってことなのかなと…
まぁ何度も呼び出すのかどうかとか、更新が入るのかどうかとかにもよるんだろうけど…
どこにデータを置くのか、どういった構造なのか
どういった時にそのデータを利用するのか
結局そこらへんも含めて全部考えられる人がすごいプログラマーってことなんかね？
「オルグする」ウケる
水野さんがドラゴンボール超 のモナカに見えて仕方ありません。ぜひ議題として取り上げていただきたいです。
37:31 水野さん😆
30:15 C言語の難しさはポインタそのものというより，ポインタの文法事項だと思うの
乱数上司ニキのかわいいポイントは常時上司であること。
水野さんって常にちょっとマウント取りたい感があって、堀本さんは相手を尊重する態度が見受けられるからちょうどいい相性なんかな？って感じました
兄に対抗する弟（水野）と生意気な弟を暖かく見守る兄（堀本）に見えます。
時と場合によって逆な時もある気がする
Cは避けて通れないんですかね？
今はPHP(Laravel)・Ruby(Rails)・JS(next.js)を学習したところですが、さすがにC言語を学習する積極的な理由が思いつきません😅
暇があるなら触れておくことをお勧めします
C、C++までやっておくと、抽象度の高い言語でもどういう実装で動いているか想像しやすくなり
言語のなぞ制約がなぜ必要かわかったり、処理の重さが感じ取れたりします
実際の具体的な命令を覚える必要はないですが用語類だけでも抑えておくと役立つ事は多いかもです
大学学部の授業で1年齧っただけでしたが別言語の習得やらメモリ管理感覚に繋がったとおもいます
ハードウェアまで動かそうとすると、まだまだCやC++がメジャーだと思います。
Cだとmalloc()みたいな後発言語では隠蔽されている過程も書かないとならないし、ハードウェア資源直結型言語だと思います。
Cを勉強することを推奨する意見ばかりなので、逆も書いてみようと思います。
皆さんが書かれている目的なら、Cを勉強した方がよいですが、少なくともアルゴリズムとデータ構造を勉強するだけなら、PHPでもRubyでもJSでも十分だと思います。
ただし、以下の条件付きです。
- 言語のライブラリーで最初から用意されているのを無視して、あえて自前で作って見ること
- 上記の理由もあり、フレームワークは使わず、コンソールアプリで学ぶべきです。PHPもJSもコンソールアプリを作ることは可能ですが、Ruby（もちろん、Railsは使わない）の方が普通かと思います。
なお、書籍等で本格的にアルゴリズムとデータ構造を学ぶなら、C、Java、Pythonの方が適切かもしれません。
@@Zennin2007 確か自分がアルゴリズムとデータ構造を勉強したときの言語はPascalでした。今ならPythonかのうネスト＝インデントが好きじゃないけど。
木を逆さにするといえばバオバブですね
ラジオ作るのかぁ。今はDSPでの検波が主流だな。（ちがう、そうぢゃない
そだね、AMラジオなんて直接AD変換してデジタル処理できるようになったし。
ハフマン符号というより、ノードの番号付けに近い気がする
1
10
100
101
11
110
111
これを二進数として読めば
1
2
4
5
3
6
7
自然数に一対一対応させられる
全く関係ない訳ではないなー、と思ってた
堀元氏、しょっぱなから分岐予測に失敗
上から0,1,10,11,100,...って番号付けするのはまさにヒープ構造じゃないです？
場合によってはページの抜けを許して、吊るす位置に適したポケットに書類を入れることでも二分探索木を構築できそう。
ただそれだと最悪2^nページ用意しとかなきゃならないんで、空間のコストが酷いことになりますが。
二分探索木においての1ノードは唯一の親と0から2個の子を持ちますが、それが複数集まると子の数が増えてしまうのでフラクタルとは言わないような気がしますね。
一般の木だと子がいくつでも良いのでフラクタルと言っても良さそう。
あとは木構造やポインタの領域を確保することで容量を犠牲にするトレードオフになってるんだよ、みたいな話が欲しかった気がしますね。平均、最悪計算量の話とともに是非いつか補足回を期待します。
エントロピーの話になってます。
平衡二分探索木までは行かないんですね〜
ロマネスコはフィボナッチでは？
プログラミング言語のパーサーは単純な操作ではないですが、文法が人語より超絶シンプルなフラクタル解析？ですね
自分でも感覚すぎてなんもわからん…