デカルトみを感じたいなら、コンピュータ科学をやれ!【アルゴリズム3】#3
Вставка
- Опубліковано 16 лип 2024
- アルゴリズム最終回。一見効率が悪そうなクイックソートの話から、「コンピュータ科学はデカルトみの学問」という結論を導きます。デカルトみを感じたい人はコンピュータ科学一択です。
【目次】
0:00 コンピュータ科学徒が最も尊敬する人物は?
0:49 前回の復習。効率の良い友だちの減らし方。
1:38 奇妙で巧妙なアルゴリズム「クイックソート」
6:54 クイックソートのオーダーを計算する算数タイム
16:16 アルゴリズムの楽しさは「巧妙なトリックで快い驚きを感ずる」こと
18:49 「どのデカルト?」クイズ。「我思う故に我あり」ではなくて…
27:45 現代ソフトウェア工学はデカルト先生大歓喜工学
31:28 アルゴリズムは高速化のものじゃない。コンピュータ科学徒の本懐
36:43 今回置き去りにした「データ構造」
【参考文献のリンク】
○アルゴリズムとデータ構造
amzn.to/3FJSIsN
聖書。非プログラマーが読むのはキツいが、絶対古くならない名著。
○世界でもっとも強力な9のアルゴリズム
amzn.to/3qDudHv
一般書で誰でも楽しく読めるし、専門家が書いてるので骨太。アルゴリズムの「すごさ」「楽しさ」を気楽に味わいたい人はこちらをどうぞ。
○アルゴリズムが世界を支配する
amzn.to/34c4yya
他の参考文献と違って、「おもしろ事実」にフォーカスしたノンフィクション本。「世界で最初にコンピュータによる自動取引を始めたハッカー」の話などが中心。あまりアルゴリズムに深く立ち入らないが、面白い。おもしろ半分で読みたい方はこちら。
○アルゴリズム・イントロダクション
amzn.to/3EGZCO7
MITで使われてる教科書。堀元は思わず買ったが、あまりの長さにペラペラめくって満足した。30ページくらいしか読んでない。エアプ。
【親チャンネル:ゆる言語学ラジオ】
/ @yurugengo
【おたよりフォーム】
forms.gle/BLEZpLcdEPmoZTH4A
※皆様からの楽しいおたよりをお待ちしています!
【お仕事依頼はこちら!】
yurugengo@gmail.com
【堀元見プロフィール】
慶應義塾大学理工学部卒。専門は情報工学。WEBにコンテンツを作り散らかすことで生計を立てている。現在の主な収入源は「アカデミックに人の悪口を書くnote有料マガジン」。
Twitter→ / kenhori2
noteマガジン→note.com/kenhori2/m/m125fc452...
個人UA-cam→ / @kenhorimoto
【水野太貴プロフィール】
名古屋大学文学部卒。専門は言語学。
某大手出版社で編集者として勤務。言語学の知識が本業に活きてるかと思いきや、そうでもない。
【参考文献のリンク】
○アルゴリズムとデータ構造
amzn.to/3FJSIsN
聖書。非プログラマーが読むのはキツいが、絶対古くならない名著。
○世界でもっとも強力な9のアルゴリズム
amzn.to/3qDudHv
一般書で誰でも楽しく読めるし、専門家が書いてるので骨太。アルゴリズムの「すごさ」「楽しさ」を気楽に味わいたい人はこちらをどうぞ。
○アルゴリズムが世界を支配する
amzn.to/34c4yya
他の参考文献と違って、「おもしろ事実」にフォーカスしたノンフィクション本。「世界で最初にコンピュータによる自動取引を始めたハッカー」の話などが中心。あまりアルゴリズムに深く立ち入らないが、面白い。おもしろ半分で読みたい方はこちら。
○アルゴリズム・イントロダクション
amzn.to/3EGZCO7
MITで使われてる教科書。堀元は思わず買ったが、あまりの長さにペラペラめくって満足した。30ページくらいしか読んでない。エアプ。
水野さん選択ソート、堀元さんクイックソートでこち亀全巻並べ替え選手権して欲しい
日本語で理解する意味の「分かる」
語源的には「分ける」に対応する自動詞であり、つまり「分割された」という意味なので、結局人間も、分割して初めて理解できるようになる
このコメント上げたいわ
本家で解説してたよなw
どクリシェ
「同じ単位にすんな」は多くの人が思っていたらしく、最近は 1000B が 1kB、1024B が 1KiB って表記されたりしますね。Ki(キビ) Gi(ギビ) Ti(ティビ) …
KiB、生まれた経緯やその定義以外の文脈でほとんど見たことがない
+の逆演算としての-
×の逆演算としての÷
^(べき乗)の逆演算としてのlog
ていうのが良くする説明
y=a+x x=y−a
y=ax x=y/a
y=aˣ x=logₐy
指数関数の威力ネタは
『ドラえもん』のくりまんじゅうバイバイン回
紙を半分に折り続けて何回目に月に着くか
秀吉の褒美として米一粒をマス目増えるごとに倍にする人
の三銃士だと思う。
異論は認める
同感です。
栗まんじゅうを借金の利息が怖い教材にするといいと思う🙂
あえてメモリに踏み込まないのに好感を得ました。
世の中の参考書って正確にしようしようと頑張りすぎてハードル高くなりすぎなんですよね。
このくらい緩い方が初学者の一歩としてはちょうど良い気がします
36:30 あたりのくだり、狂信的すぎてデカルトみというよりカルトみが強い
デカルトが教祖のカルト集団ですね…
水野さん「完全に理解した」状態になった
「押すなよ!絶対に押すなよ!」並みのフリ。
ゆるコンもゆるげんも良いコンテンツすぎて子育て以外の時間が無限に溶けていく
アラン・チューリングが一瞬で出てきて、それに「おーすごい!」ともならないレベルのおふたりの教養に感服です。。。
ノイマンとチューリングに対するフォローが一切ないのがすごいな
小学校教員です。
クラス30人分のプリントなどをバラバラに回収してしまい、並べ替える際、最初選択ソート的なやり方でやってました。が、効率が悪いなと感じ、やり方を変えました。
まず、取り出したプリントを1~10, 11~20, 21~30に振り分けます。その後、それぞれのかたまりごとに並べ替え、最後に合わせます。
まさにdivide and conquerしてるわ!と気付き、デカルトみを感じました。
トランプを順番に並べるときに、
(1)赤黒色分け 2分割
(2)マークで分ける 4分割
とすると、13枚の並べ替え4回にできて、クイックソートの威力を理解できる。
底辺高校でlog学ばなかったけど、このラジオ聞いただけでlogのこと理解できる内容ですげぇ…
だから、最初に水野さんが本の並べ替えかたを聞かれたときに答えられていた
「まず1桁のヤツを一回出してそれだけ並べ替えて、10台のヤツを出してそれだけ並べ替えて……」
と、2段階でやるのが、高々数十冊程度の並べ替えを人間がやるときの最適な方法の一つなんですよね。
「パッと見て10の位が同じ本を見つける」や「10個程度のものを並べ替える」が高速にできるので。
ちなみに、コンピュータでも2段階で処理するというのはよくやります。
例えば、glibc の qsort (C言語の標準のソート関数)だと、
分割した各部が4個以下になるまではクイックソートして大雑把に並び替えたあと、
最後に全体を通して挿入ソートで並べ直すという実装になってます。
これが実装された当時のコンピュータ(Sun 4/260)で一番バランスの良い分割方法だったと、
ソースコードのコメントに残されていて、時代を感じます。
このソースコードは意外な程に短いので、興味がある方は一度読んで見ることをおすすめします。
(リンクを貼るとUA-cam君に蹴られそうなのでやめておきますが、 glibc stdlib/qsort.c をググれば行けます)
堀元さんが「過言ではない」って言う度に、堀元ボイスで「かごん~↑」って脳内再生される
「母語話者なのに?」
主に母語話者が母語について詳細な理解をしていない場合に用いられるゆる言語学ラジオ界隈のスラング
対義語:「コンピューター科学徒じゃないのに」
主に文系の人物の数学力を称賛するときに用いるゆるコンピューター科学ラジオ界隈の新しいスラングになるかもしれない用語
視聴者はみんな用意された台本がバキバキにぶっ壊れるところを期待していると言っても過言ではない。
???「過言です」
世界史好き的には、「分割統治」のフレーズが出てくると「古代ローマ共和制み」を感じる。
「わたしが検討する難問の一つ一つを、できるだけ多くの、しかも問題をよりよく解くために必要なだけの小部分に分割すること。」(『方法序説』岩波文庫版、谷川多佳子訳、原文フランス語)
Cogito ergo sum(コーギトー・エルゴー・スム)のようにラテン語風に言うとすれば、
Divide et impera(ディーウィデ・エト・インペラー)という決まり文句があり、
これを英訳したのがDivide and Conquerだが、Divide and Ruleという訳の方がしっくりくる。
ヴィトゲンシュタインの「見渡せることは発明だ」という言葉も同じようなことを語っていると思われるが、
例えば円周率のように記述するだけで黒板やノートが埋まってしまう上にいつまでも完了しないような数をπと置くことで容易に利用可能にする事情をも表していて好き。
あ、コンピュータは「見渡す」ことができないんだっけ。
28:35 「敷衍しましたけど、敷衍ってか当てはめた、援用したのは」
もう、ミーム「水野的失敗」と言っていいのではないだろうか。言い換えても使う言葉が難しいんよ。
このコメントなかったら敷衍とか一生知らんままでした。ありがとう。
水野さん優秀すぎておいてかれる説。
でもこの2人だから観てる感もあるので引き続き楽しみです。
あと音が良いので無限に聞ける。
堀元さんがタクソノミー好きって話と、プログラミングの本質は分割であるって話は根底を共有していそう。
反省後にも相変わらず台本壊しまくる水野さんw
ルロイ修道士の「困難は分割せよ」が元はデカルトの言葉だったというのをはじめて知りました!
私はマジシャンなのですが「困難を分割する」はマジシャン用語にもあります
そして、マジシャンはまさに
「現象実現のために、自分の能力に沿った分割する」
という行動をしていますね
人間でも「一桁巻、10~19、20~29、30の手ごろな群にババッと分けて、それから並べ替えする方が速い」し、「人間は10進数で、システムは2進数だから仕分けの基準(人間は上位の位で、システムは上下)が違うだけ」ということでしょうか。いずれにしてもデカルトみは深いですね。
人間が実際にやるならマージソートがやりやすいのかなあと思いますね
複数人での同時作業にも対応できるし、覚えておいて損がない
「究極に簡単な汎用分割単位1と0の計算ですべて計算できるんじゃね?」って言い出したライプニッツさんが直接的な父な気がします。
普通の人は「分割するほど分割数は増えるんだから、そこそこ簡単 x そこそこ分割が一番はやくね?」って思っちゃいますもん。
機械論的科学観の人でコンピュータの歴史を語るときって、普通はライプニッツが出てくると自分も思います。
ゆるコンは、堀本さんの音声コンテンツへの矜持が感じます。
コンピュータ・サイエンスを視覚情報なしで説明されるの凄い!
数学能力がありすぎる水野さんに「100匹のアリの問題」を出題したら、解答を導き出しそう。
難しくて読み進められなかったVBA入門書、このシリーズを見終わってから内容がいきなり理解できるようになりビックリです!ありがとうございました。
今回もまた最高だったのでこのくらいの知識量で次もお願いしたいです!(n=1の忌憚ない意見)
n=2にしときました!
プログラム的には
n=👍
堀元さんの描いた想定の未来を
水野さんが悪気なくぶち壊していくところがめっちゃ好きです
クイズノックと交互に見る楽しさよ
めちゃくちゃ面白かった!
既に次のシリーズを楽しみにしています!
30:53 この補足わかりやすいしすごいしでヤバイ。
このシリーズを見てたので、クイズノック鶴ちゃんがモグライダーのネタ解説して興奮してる理由がちょっとわかった
わぁ美川さんだぁ! 美川さん美川さん!
てんびん座より後ろですか!
クイズノックの解説のほうがわかりやすかった(n=1)
循環してますけど、何を持って後ろとするプロトコルですか?
2の補数回楽しみにしています。
今回も面白かったですよ。難しい数学的な話を分かりやすく解説してもらって良かったです。良い知的刺激になりますので、ゆるコンピューターサイエンスも是非継続して下さい。データ処理に役立つ正しいデータ構造ついて、大学でちゃんと学んだ人からの話を聞けるのも楽しみにしています。
35年くらい前なのですが、プログラミングを学び始めたころに、
「プログラミングのセンスはサブルーチンの組み方を見ればわかる」
と言われたことがあるのですが、
これって堀元さんが言ってることと同じですよね。
これがこんなに普遍的に重要な概念だとは知りませんでした。
勉強になります。
プログラミング勉強してますが今回もすごく快い驚きを感じました。ありがとうございます。
日曜の楽しみー
水野さんが何度も「“log”って説明大丈夫ですよね」と自分は分かってても非理系目線で極力解説しようとしてるのに、堀元さんは「は?そんな基本中の基本に説明要る?」みたいなスタンスでグイグイ先進むのオモロ。でも楽しそうに話してるのが一番人の学習意欲を高めるのでヨシ。
Divide and Conquer (Divide and Rule)はローマから始まり特に大英帝国が用いた帝国主義の植民地運営の方法だけど、分断し怒りや不満の矛先をお互いに向けさせるよう工作し、宗主国は仲裁するかたちで双方を支配した。ローマ帝国の辺境だったブリタニアがビクトリア時代という黄金期を迎え「太陽の沈まない国」になったのはこの手法によるからに他ならず、無敵なのは実証済みなのだが、分断する政策は報復に報復を重ねる現代の紛争の種を世界中に撒き散らすことになった。英国植民地だった地域と関わっていると、どうしてもこの言葉にネガティブなイメージを持ってしまう…。でも、親の数を上回る子どもがいる家庭ではこのDivide-and-Conquer手法で挑まないとこっちがやられる!
読み上げソフトを使ってない 会話形式の他の解説系動画をみると、いかにこの二人の解説が 聞きやすく、分かりやすいかよく分かる(このお二人の動画見て当然と思ってたけど)、フィラーがなかったり、話の順序立てがうまいんだよなぁ。
30年以上前に汎用機業界に携わった人間としては、2進数の優れている点(論理演算やシフトなど、例題として1000本のボトルのうち1本に毒薬的な問題)を取り上げて貰えるとうれしいです
この2人なんだから自然言語処理でしょ!!
Word2vecとか最初知った時感動した。
Divide and conquer、コンピューター科学に限らず仕事全般に役立つ概念ですね!
水野さんがキレキレすぎて、生徒じゃなくて先生みたいだなって何度も思いました。
人間に例えてもクイックソート使えますよ。事務所の古い名刺1000枚くらいを整理するときに
①頭文字の子音順(あかさたな)に分ける
②母音順に(aiueo)にわける。
③残り枚数多ければ2文字目に同じ作業をする。
以下繰り返しって作業手順しました。
情報処理やってて別分野の職ついてるんですけどdivideの概念ほんとに有能なんですよね
無茶振りされても「できる範囲」「できない範囲」のdivideするだけでどう進めていけば良いかが瞭然になるんですよねー
divide and conquerの、特にconquerの中で重要な能力が一般化だと思う。
例えばカレー作りなら、玉ねぎやトマトはくし切り、じゃがいもは8等分とかにしたい。この、「切る」はどこまで一般化したら便利か、どこまで具体的であるべきか、このセンスがconquerに求められると思う。
What an amazing content! everything you upload keeps getting better and better, Thank you for sharing my friend 💜
ある部分で久しぶりに大爆笑しました。
本当にありがとうございます。
これからも宜しくお願い致します。
本読むの大変だなと思ったら「アルゴリズム図鑑」ってアプリで勉強するのも良さそうです!
堀本さん、引き作るの上手いなぁといつも思う
言葉にトゲはあるけど、ついつい聞き入ってしまう
本棚に空きがなく、取り出した本を置く場所もなく、さらにブックカバーがついていて背表紙から巻数が見えない本を並べ替えるときにクイックソートは役に立ちそう。
最終的に結合(join)して統合(integrate)することを意識せずにdevideして設計(design)してしまうと、問題が解決(resolve)せずに却って新たな問題を引き起こすことはよくあります。
製品を作るときはソフトウェア工学だけでなく品質工学の知見も必要で、問題は必ず起きるという前提に立ち、設計時には機能性(functionality)だけでなく試験性(testability)や解析性(analizability)の観点を入れて見積もることが大事です。
データ構造の回も楽しみにしています。
28:35 「敷衍」を「援用」とクイックに言い換えるのいいです。この二つの概念が切り分けられている。
面白かった!
コーピュータ素人の自分は最初ふーんくらいで聞いてたけど、スターリンソートや大本営ソートなどのネタソートを知って改めて聞き直してようやく理解できました!
単発でもいいから堀本さんのネタソート話聞きたいなぁ
デカルトみの納得感すごいですね笑
要望としてはライフゲームとチューリング完全とかの話も聞いてみたいです!
「困難は分割せよ」を信奉してるから、堀本さんタクソノミー好きなのかー
知恵の悲しみって言葉、自分は頭良く無いからピンとこないなーと思ってたけど
確かに水野さんほど賢過ぎるとそれはそれで大変な事もあるのかと納得した
今まで選択ソートで分類していたトランプをクイックソートに変えました。おかげで爆速で分類できるようになり、時間に余裕が生まれました。ありがとうございました。
面白すぎる...興味がすごくわきました
大学受験程度の簡単な数学で、大学の内容に踏み込んで下さるので有り難いです
面白かった~。人生の勉強にもなりました。
おもしろかったです
面白かったです。
頑張って下さい。
こんなすごい人がいるんだなーと感心しました。
デープラーニングというアルゴリズムで、できないとを可能にするとは、目からウロコでした。
本家の雑談回みたいな扱いで、コンピュータ科学ニュースコメンタリー回を挟んで、本編の基礎科学ベクトルとニュース回のトップダウンベクトルの2方向で積み上がっていくと、クイックソートみが出てきていいかもしれない。
ゆる言語学と違って、podcast聞くだけだと理解できないとこがあって動画見直しました。テロップと図がわかりやすいです。それでもログと指数の基本的知識なさすぎてまだ理解できてない〜!水野さんすごい!
divine-and-conquer! コンピュータ科学には哲学がありますなあ。データ構造もぜひシリーズ化を!
水野さん、すごく頭いいなあ。
私はクイックソートを理解するのに自分で何回も書いてすごく時間がかかったのに。。。
ものすごい面白かったです。個人的にはそこまで難しいと感じませんでした。データ構造も楽しみにしています。
ちょうどコンピュータサイエンスを哲学の文脈で語れないか考えていたので助かりました
ゆる言語学ラジオではソシュール回、サピア回を通して言語学の道具を紹介されていたので、ゆるコンピュータ科学でも新たな道具を持ち込んだ偉人に着目する回を見てみたいです。
やっぱりチョムスキーですかね
分割統治以外の3つ、明証性の尊重、単純性の尊重、網羅的列挙もプログラミングをやっている者にとって日常的に気をつけていることとぴったり一致します。
体育の時間で二人組をつくる時に有用
先生が適当に生徒を半分ずつにしていく
先生と組む生徒は毎回ランダムになるので悲しい記憶を持つ人間が減る
これ、映像というか、イメージを見るとめちゃめちゃわかりやすい。
次の配信を楽しみにしています。シリーズの最終話はホモデウスに繋がると予想。二相コミットの難しさとかも取り上げてほしいなぁ。
アダム・スミス『諸国民の富』第一章は分業の話しかしていないといっても過言ではありませんが、分業を「タスクの分割」と解釈するとあれってデカルトの発想の後継者といえるんですね。
自分の処理出来るレベルに落とし込むことは勉強にも確かに言えますね
ビジネス書の「過言」をひたすら笑っている方が、とんでもない過言を飛ばし倒してるのめっちゃ面白いww
困難は分割せよ
は本当に素晴らしい言葉ですよね!
我が塾の小学生は私が図形問題のときにいつも言うので、口癖になってしまっています。
1つ難点は、それは全体から一部分を引いたほうがいいのになぁ〜という面積問題までもを、
「僕は困難を分割するんだ!」と言って分割しまくる子が出てきてしまってます。
台本ブレーク楽しんでおります、もっとやってくださいw
Win98、Win95 のチーフアーキテクトだった中嶋聡さんも、著書「なぜ、あなたの仕事は終わらないのか」で同じことをおっしゃってました。
そして『デカルトは「困難を分割せよ」と言い、ビル・ゲイツは「問題を切り分けろ」と言った』をタイトルにブログもpostされていて、この動画を見て繋がった〜!感がありました👏
問題が起きたときにバグを探すために切り分けるのも、困難は分割せよだったのですね
ゆる言語学ラジオとチャンネルが違うのに気づいて急いで登録した
クイックソートは再帰呼出しのありがたみを初めて実感したときだったな
まってました
リアルでやっても計算処理が楽だから疲れてるときはそういう並び替えしようかな
ログはググってなんとかついていきました。水野さん文系なのにほんとすごいですね。
データ構造18回シリーズ待ってますのでよろしくおねがいします。
二分木構造は強いですよねw
始めて覚えた時は「詰め込んで行くだけで揃っちゃう!」と感動しましたからw
取らないでおれのデカルトみで大爆笑した
「人工知能やディープラーニングに関する誤解を解く」というテーマを取り上げて欲しいと思います。このフレーズだけできっと分かってくれるはず。
結局のところ科学=西洋哲学の本質は
いかにしてdivideするか、
分かることでそれをconquerして幸せになろう!
という「分別智」にあるのでしょうね。
それに対して東洋哲学の本質が
分けようとするな!それを支配できると思うな!
その考えが不幸のもとだ!
という「無分別智」であることなのが面白いと思います。
水野さんのレベルが高いですね…すんなりソートの話を受け入れられていらっしゃる。
私は最初にソートを知った時、どうしても「2つのものしか比較できない」が自分の体感と合わず、理解ができなかった記憶があります。
なのでずっとスパゲッティソートの思考から抜けられず、バブルソートでさえ「なんでこんなことしないといけないんだ?」と理解に時間がかかりました…
ピタゴラスイッチの
じゃがいもソートが
何をやっているのかが初めて本質的に分かりました