【7日目】アルゴリズム勉強法
正直海外旅行中なのでなかなか進めることができない。しかもネットに繋がらないというトラブルが発生したため、記事を読んでいくこともできないでいる。
言い訳ではあるが、そういうこともあり、勉強法を紹介させてもらう。その名もファインマンテクニックである。
ファインマンさんは『ご冗談でしょ、ファインマンさん』でも有名なノーベル物理学賞ももらっているすごい人です。
この人は学問を本当に愛しており、理解力もずば抜けています。その人の勉強法がシンプルで応用範囲も広いのでアルゴリズムに使っていこうと思い、紹介です。
1：「概念」を選ぶ
2：その「概念」について「人に教える」
3：教科書(元の資料)に戻る
4：再検討と単純化
という方法です。
かなりシンプルですね。詳しくは下記を参考にしてください。
https://www.google.co.jp/amp/s/gigazine.net/amp/20160627-the-feynman-technique
【6日目】アルゴリズム関連の本
いつもするようにしていることの１つに、学ぶ本の読み物を片っ端から読んでいくというものをしている。
学び始める前はどうしても視野が狭くなってしまう。例えば「アルゴリズムとは」と調べると手順であるであったり、とっつきやすい話題としてソートアルゴリズムなどが紹介されたものを多く見つける。
ただ、実際にどういった使われ方をしているのか、どんなものがあるのか等どうしてもイメージがわかない。
その際に関連する読み物を読むと大まかなイメージがつかめる。こんなメリットがあり、こんなデメリットがある。
こうゆうことに使えそうだし、こうゆう考え方がある。など。
それによってなんだそんなもんか、と感じて仕舞えばそれ以降を学んでいく必要はない。
そんな世界に入っていけるならと思えるなら、学ぼうと思った際にモチベーションも上がる。
そう言った本をここでは紹介していく。
1,『世界でもっとも強力な9のアルゴリズム』
https://www.amazon.co.jp/世界でもっとも強力な9のアルゴリズム-ジョン・マコーミック/dp/482228493X
まずはこれである。アルゴリズムに興味があるなら一度これを読んでみてほしい。今まで何気なく利用していたものの見方が一気に変わる。
検索エンジンや圧縮(zipなど)のような普段から何気なく使っているものを中心に紹介されている。それが数式など一切使わずに説明されている。
非常にわかりやすい。それを知ったからと言って仕事の効率が上がると言うことはないが世界の見方の変わる良い本である。
2,『アルゴリズムが世界を支配する』
https://www.amazon.co.jp/gp/aw/d/B00FMI2XIW/ref=tmm_kin_title_0?ie=UTF8&qid=&sr=
金融に偏っているものの十分に面白い。実際に起こった事例についてストーリー仕立てで説明されている。
アルゴリズムとはどんなものか、という視点よりはアルゴリズムがどう使われているか、こんな凄い事例がある、というように書かれている。
アルゴリズムって何に使われてるの？って思う方はぜひ読んでほしい。そんな馬鹿なと思えるような世界が見えると思う。
3,『はじめアルゴリズム』
https://www.amazon.co.jp/はじめアルゴリズム-モーニング-KC-三原-和人/dp/4065105218
これは珍しい漫画である。ただ、これはまだ読めていないので、読んだら追記させてもらう。
レビュー自体も高評価で、そもそもアルゴリズムを主題の漫画というだけで気になってしまう。
読んですぐ感想を言おう！
4,『数学ガール/乱択アルゴリズム (数学ガールシリーズ 4)』
言わずと知れた数学ガールのアルゴリズム版である。これも読めておらず、紹介した本の半分も読めてないじゃないかと言われそうだが、実際そうだからぐうの音もでない。
この作者はドナルドクヌースさんの本の間違っているところを指摘し、小切手をもらっているほど、アルゴリズムにも精通している。
※クヌースさんの本は世界で最初に本の中の間違いを指摘した人に小切手を送っている。
世界的に有名でプログラマーのバイブルともされている本を世界で最初に間違いを指摘するとはそれだけですごい。
自分だと読むので精一杯の本を読み込んでいるというだけでも尊敬に値する。
とまあ、ここまで紹介したが、まだまだあるはずである。アルゴリズムをやっている間は本だけでなく、記事も追っているが人によって楽しみ方が違ったり、イメージがずれていたりと面白い。
この記事はできる限り更新していきたい。また、何かあれば教えてほしい。
ではありがとうございました。
【4日目】at coder問題
今日はこの記事に沿って何問か解いてみた。
けんちょんさんの記事は本当に参考になるし、面白い。これ読んでやってくだけで事実解けていける感覚になるのも有難い。
ただ、実家に帰っていることもあり、進捗が悪い。明日からも旅行だし、続けられるのやら。
A問題までは普通に解けて、なんなら物足りないくらいでB問題が今は丁度良いんだけど、時折全然わからない時がある。
そういうのでつまづいて、進まなくなってしまうと面白くなくなるが、けんちょんさんが紹介している記事を読んでからだと発展問題も解きやすい。
しかもアルゴリズム自体の紹介も多いから楽しい。
明日からは、どうやって時間作ろうか。
【3日目】アルゴリズムは
更新が遅れたと言うか次の日になってるけどとりあえず3日目。
アルゴリズムは社会の中でどう役に立つのか？AIやOS、検索エンジン、全てがアルゴリズムを元に始まっている。
原点はここにある。ただ、これらは業務や問題を解決する方法で、それらの業務自体をデータ構造と見たときの、それらの解決策をアルゴリズムという。
だからプログラマーはプログラミングに関わる、インターネットやプログラミング言語などのソフトウェアにプラスして、業務知識を入れなくてはならない。
また、効率的に新しい概念を入れたいならアルゴリズムから当たるのは案外いいのかもしれない。
p2pは分散ハッシュテーブルだし、ゼロ知識プロトコルなどブロックチェーンで使われている。ディープラーニングなどにも多くのアルゴリズムが使われている。
後は日常でひたすら仕組みを考える。これは簡単な3ステップで考えられる。
それはなにをするのか？それはどんな仕組みか？それは自分でも作れるか？これらに答えていけばいい。
作ってみると問題が小さな問題が浮き彫りになる。補完し、応用すれば知識は積み上がる。
まあ、要するに作ってみたら遊んで(改造して)見ようというだけである。作って終わりほど勿体無いものはない。
【2日目】アルゴリズム参考記事
いやー飲み会で帰るのが遅くなってしまった。考えてみればゴールデンウィーク前って三日坊主になる感満載のタイミングで始めてしまったな。
二分木とはの記事を読んでのメモを貼っておきます。
・二分木は二分探索や二分ヒープを実装するために使われる。
・「二分木は連結された (connected) 閉路をもたない (acyclic) グラフで、各頂点 (vertex) の次数 (degree) （各頂点に出入りする辺の数）が3を超えないもの。」と定義されている。要するに同じノードに戻ってくるようなものは分岐は２つまで。まあ二分木だしね。
・唯一の根を決めることでどんなメリットがあるのか？入力が１つに絞られるのは確かに有難い。
・二分木を実装するなら、まずルートをつくりその下にleft、rightをつくりそこをまずはnullにしておく。ルートの下に階層をつくりたい場合は関数を呼び出し、leftやrightに同じようなものをルートを作る。これ実装できるかな？これができたらファイル構造を作れるかもしれない。
・配列に二分木を格納するという方法はなっとくアルゴリズムでやった気がする。リンクリストではないからハッシュテーブルかな。
・2i+1、2i+2で配列に格納していける。i=0なら1と2に、格納し、1の子ノードとして3と4に格納される。二分ならそこまで大変そうではない。空きが大量になることはあってもそこは使われているからそこは使っているから別のところへ行ってくれというのはない。
・n個のノードをもつ高さhの二分木の場合、配列の要素の数は2^h - nのペースで増えていく。二分木は大きくなればなるほどメモリの消費は激しくなる。そこは気をつける必要がある。
・二分木の巡回方法はいろいろある。根をまず調べて(子ノードまで調べる)、その後で子ノードの根を調べるやり方。子ノードがなくなるまで調べてを繰り返すやり方などがある。
・ノードの中に１つしか線がないものが続いてしまったらそれはもう連結リストになってしまう。二分木としてやっている以上効率が下がってしまう。
・全てを漏らすことなく、同じものを重複せずに調べることを走査という。調べると言われればこれをしなければならない。
・走査には2種類あり、幅優先探索と深さ優先探索がある。⭐️これらをまずは実装してみる。そもそも二分木をクリックもしくは呼び出したら新しい二分木がでてきても作ってみたい。面倒ならファイル構造を対象にできるようになると楽しい。
・写経でいいからまずはこれを実装する。写経でこの長さを書けなければコードを自分でこの長さ書けるとは思えない。
参考記事
https://ja.m.wikipedia.org/wiki/%E4%BA%8C%E5%88%86%E6%9C%A8
https://programming-place.net/ppp/contents/algorithm/data_struct/007.html
【1日目】二分探索とはなんぞや
アルゴリズムの中で考え方としても汎用性が高く、高速に動くものとしての代表として二分探索がある。
これは考え方自体がかなりシンプル。ソートされたデータに対して使うことができる。
例えばlist = [1,3,5,7,9]の配列があったとする。その中から7を探すにはどうしたらいいか？
まず思いつくのは前から順番に比較していく方法が考えられる。しかし、これはlistの中身が5つくらいなら早いが、10万になってしまうと１つずつ比較することになり時間がかかる。
ではどうすれば早くなるだろうか。真ん中の数字と比較して大きいか小さいかを判断すればいい。
大きければ真ん中より小さい数はもう考える必要がなくなる。
[1,2,3,4,5]だとして4を探すなら3より4は大きいので、残りは4,5だけになる。これを見つかるまで繰り返すだけである。
要素がいくつになろうが繰り返す。これだけである。もちろんない場合もあるのでそれも考えなくてはならない。
ない場合を考えなかったら3より大きいけど5より小さいをいくら繰り返しても見つからないことになってしまう。
参考サイトは下記に載せておくのでとりあえずコードを書いていく。
def binary_search(list,item): low = 0 high = len(list) - 1 while low <= high: mid = (low + high) // 2 guess = list[mid] if guess == item: return mid elif guess < item: low = mid + 1 else: high = mid - 1 return None
これでとりあえず実行できる。一番オーソドックスなものである。
以上です。ありがとうございます😊
