Pythonではじめるアルゴリズム入門~伝統的なアルゴリズムで学ぶ定石と計算量~を読んで
抽選で当たりました。ぱちぱち！ので書評を。
初書評です。本は読むほうなので、書評ブログ投稿したいと思っていましたが、なかなか手を付けられずにいました。
機会いただき感謝いたします。
読む前の読者スペック
読む前の読者スペックはこんな感じです。
最低限の知識はあるけど、プログラミング経験は0。こいつが読めたら、誰でも読めるね。って感じのスペックです。
応募（本書を読みたかった）背景
インフラエンジニアとしてサーバの運用保守をしています。
昨今のSite Reliability Engineering(SRE) の流れもあり、Infrastructure as Code（IaC）を取り組む上でプログラミングはインフラエンジニアにとっても非常に重要になってきております。
そこで、勉強しようと色々なもの（オンライン教材や勉強会）に手を出しましたが、文法を教えるだけ（繰り返し分の書き方、変数の定義方法など）というものが多く、この本の第1章ですね。それは調べれば分るのだよな。。。と思っていました。
何が分からないのか分からないので、いくつか自分で実際に書いてみよう！と行動した際に躓いたのがアルゴリズムです。プログラミングをどう書けばいいか分からないのです。もしくは相当な力業でなら書けるけど汎用性がない（その問題にしか適用できず業務では絶対使えないものしかできない）のです。
プログラマーってプログラミング言語自体の知識より、アルゴリズムが大事なんじゃない？それがあれば後はどう書くか調べるだけでしょ？
と極端な考えを持ち始めたのが最近。でもアルゴリズムってどうやって学ぶんだろう。。。と悩んでいたタイミングでこの本に出会いました。上記を期待したうえで読んでみました。
本の目次
第1章 Pythonの基本とデータ構造を知る
1.1 プログラミング言語の選択
1.2 プログラミング言語Pythonの概要
1.3 四則演算と優先順位
1.4 変数と代入、リスト、タプル
1.5 文字と文字列
1.6 条件分岐と繰り返し、フローチャート
1.7 リスト内包表記
1.8 関数とクラス第2章 基本的なプログラムを作ってみる
2.1 フローチャートを描く
2.2 FizzBuzzを実装する
2.3 自動販売機でお釣りを計算する
2.4 基数を変換する
2.5 素数を判定する
2.6 フィボナッチ数列を作る第3章 計算量について学ぶ
3.1 計算コストと実行時間、時間計算量
3.2 データ構造による計算量の違い
3.3 アルゴリズムの計算量と問題の計算量第4章 いろいろな探索方法を学ぶ
4.1 線形探索
4.2 二分探索
4.3 木構造での探索
4.4 さまざまな例を実装する第5章 データの並べ替えにかかる時間を比べる
5.1 身近な場面でも使われる「並べ替え」とは？
5.2 選択ソート
5.3 挿入ソート
5.4 バブルソート
5.5 ヒープソート
5.6 マージソート
5.7 クイックソート
5.8 処理速度を比較する第6章 実務に役立つアルゴリズムを知る
6.1 最短経路問題とは？
6.2 ベルマン・フォード法
6.3 ダイクストラ法
6.4 A*アルゴリズム
6.5 文字列探索の力任せ法
6.6 Boyer-Moore法
6.7 逆ポーランド記法
6.8 ユークリッドの互除法Appendix Pythonのインストール
第一版なので、ミスも多かったりするかと思いましたが、正誤表 以外見つけられず。（2020/2/28時点で4件）
期待に対する結果・本の感想
特に私と同じような悩みを持った方にはお勧めします。
よく初心を忘れている方が書いた中身が難しすぎる入門書がありますが、この本は前提（例えばos別のインストール方法や、二進数の足し算など）を漏らさず説明してから本題に入るので、挫折せずに読むことができました。また、日本語も適切で良く頭に入ってくるため、初心者から採用している企業の研修などで使ったらいいのでは？と思うほどでした。
最後の方は中級者でも楽しめる内容だと思います。
特に2章以降は、プログラミングが得意な方の思考を辿れます。これが初学者にはとても嬉しかったです。
いきなり簡素で正解に近いコードを見せられて、「～というアルゴリズムがあります。」ではなくて、
「最初はフロー図を作りましょう。」「一つ目の繰り返し文を実装してみましょう。」「ここの処理が重複してるので、一つに纏められそうですね。」という感じで、最終的な簡素で綺麗なコードになる理由が思考を追って理解できるのです。
読み進める前に自分なりにフロー図を作ってみたりプログラミングしてみると、よりその思考方法が勉強になります。どんどんコードが少なくなっていくことに快感を覚えながらアルゴリズムを学ぶことができました。
「あ、こういう発想があるのか！」「へーこんなにコード少なくなるのか。これで完璧だ。」「え、まだダメ？あーここも気をつけないといけないのかー。」的な。
更に説明文だけでなく、説明図、フロー図、コードとその実行結果があって、理解の助けが沢山あります。
例えば、「参照渡し」という私にとっては分かりづらいワードがp35にありました。説明文を読んでも図を見ても少し難しかったのですが、実行結果も込みで見たことで、理解することができました。
副産物（期待してたもの以外に得たもの）
計算量と再帰について（本当はもっと奥が深いのでしょうが）理解が進みました。
計算量は基本情報で学んだ記憶があるが、いまいちピンと来ていませんでした。それが今ではOの記号の意味が分かり、『理系が恋に落ちたので証明してみた。』に出てくる会話が分かるくらいにはなってきました。計算量をプログラミング時に意識するべきだと強く感じました。
再帰については、高校数学を思い出しました。あの時解けても意味があまり分かっていなかった数列などの意味が分かり、数学をもう一度学びたくなりました。子どもが数列を学ぶ機会があったら、例として教えてあげようと思います。イメージができるだけで、理解度も上がるし、楽しみながら学べると思うのです。
終わりに
読み進めてるうちに、アルゴリズムについて理解は進んだものの、どうすれば実装時に思いつけるだろうと悩んでしまいました。
しかし、恐らくアルゴリズム一つ一つが研究テーマになるくらいのものだと思うので、まずは型を覚えて頭にインデックスを貼り、どう応用出来るかが大切かと今は考えております。
とにかく筆者の他の本も興味が湧いたくらい内容が分かり易かったです。
コードをいくつか書くうちに慣れてきたので、現在はPythonでサイトのスクレイピングをやってみています。上手くいったらまた記事にします。このように他のこともやってみよう、調べてみようという意欲が湧いた時点で、入門書としてはとても良かったのではないかと思います。
以上です。理解が異なる点、今後のアドバイスなどコメントいただけると幸いです。
病院の先生直伝！乳児・幼児への薬の飲ませ方
今回は趣向を変えて、育児についてです。
私の場合、土台は家庭なので、ここがしっかりしないと仕事になりません。
なので、決してブログのテーマに反してるわけではないのです（小声）
薬を飲まないといけない病気に感染
溶連菌に感染
子どもが溶連菌(※1)に感染してしまいました。2歳2か月のことです。
今までも様々な病気にかかってましたが、薬で困ったことは特にありませんでした。好きなものに混ぜると大抵飲んでくれてましたし、飲まなくても困らない薬が殆どだったからです。
※1（病院で貰ったプリント抜粋）
溶連菌感染症とは
溶連菌という細菌（ばい菌）がのどに感染し、発熱・のどの痛みのほか、時に体や手足に発疹が出ることがあります。舌が赤くなり表面にブツブツが目立ちイチゴの様になることもあります。この菌は人から人にうつることがあります。
この菌による咽頭炎（のどかぜ）は重い病気ではありませんが、ほおって置くと胃腸炎（下痢・嘔吐）うぃ併発したり、数週間後に腎臓病（糸球体腎炎）や、心臓・関節の病気（リウマチ熱）を起こすことがあるため、抗生剤投与など適切な治療をする必要があります。
治療
検査で溶連菌が見つかった場合、抗生剤を10日間飲みます。ほとんどは投与から3~4日後に熱が下がり、のどの痛みもなくなります。
但し、途中で薬をやめてしまうと再発する可能性があるので、必ず指示通りに飲んでください。
飲まないといけない薬を飲まない。。。
しかし！今回は薬がまずいのか、味が濃いのか、溶連菌で喉が痛いのか、いつものように好きなものに混ぜても飲んでくれません。。。
何が困ったって、溶連菌は抗生物質を10日間飲み切って治し切らないと続発症（合併症）を引き起こす可能性があるのが怖いということです。
内服指導を受けることに
何に混ぜても飲んでくれないので、困り果てて病院に電話したところ、
飲まないといけないものなので内服指導します。来てくださいとのこと。
すぐに予約して家を飛び出しました。
（子どもが溶連菌で弱っており、焦っていました）
薬を内服させるうえで絶対NGなこと
診断で今どのように飲ませてるか聞かれたので、ポカリやリンゴジュースなど病気中も飲めていたものに混ぜたことを伝えました。
先生：「それらは好きなものですか？」
自分：「はい、いつもは喜んで飲んでいます。」
先生：「お父さん、それは絶対にやめてください。それは一番やってはいけないことです。」
と怒られました。こっちは試行錯誤しても飲んでくれず焦っていたのにそんなこと言われ、処方した時に言えよとイラっとしましたが、、、
先生：「大人でもいつも飲んでる好きなものを飲もうとして、味が違ったら腐ってる？と思って吐き出しますよね。一緒です。」
と言われ説明自体は分かり易かったです。しかもそれを続けていると好きなものも嫌いになってしまうとのこと。可哀想なことをしてました。。。
追撃で、
先生：「これだけ！これだけ頑張って飲んで！大丈夫だから！とか言ってない？それもダメだよ。自然に口調強くなって怖いし、怪しさ満載だよ。2歳ならもう分かってるからね。」
と言われだめだめでした。言ってましたわ。。。
内服指導で知ったお勧めの飲ませ方
方法1 : 子どもにとって新しいものと一緒に与える
まず味が濃く、子どもが口にしたこと無いものを探します。
例としては
- 蜂蜜
- カルピス原液
- かき氷のシロップ
- チョコ
- チョコアイス
- 餡子
- 水飴
口にしたこと無いもの見つけたら、薬と一緒にあげてみる。
食べたら、食感や味はそういうものだと思わせるように、普段は与えないようにすることが大事らしいです。これは先ほどと同じ論理。
方法2 : スポイト
うちは方法1ではダメでした。もう怪しんで仕方なく、スプーンやコップで与えるものは薬が入ると飲んでくれません。頭良いです。
そこで次に試したのがスポイトです。
この方法が我が子にはドンピシャでした。
子どもを仰向けで抱きかかえ、口にスポイトを近づけます。
十中八九泣いて口が開くので、すかさず奥の方に
ポイント1. 一回に入れる量を唾液くらいにする
唾液くらいの量を口に入れると、反射的に飲み込み易いので、吐き出されにくいそう。
ポイント2. 奥の方に入れる。
舌の先で苦みを検知するのでと言ってた気がするけど、どうなんだろう。そこら辺はよく分かりませんが、まぁ奥の方が唾液と間違えるし、吐き出しにくかったのは確かでした。
ポイント3. スポイトは先がまっすぐで細長いもの
先が丸まっているものは嫌がる子が多いようです。
こういうのがお勧めだそう。
上記ポイントを押さえてあげると...飲むは飲むようになりました！（よかった。。一安心です）
がこれもすごく嫌がりました。。泣きながらで大変だし可哀想。。。
方法３ : 複合技
方法1,2の複合技です。（これは病院で言われたものではありません）
いつも同じ技は通用しないのが常です。
- カルピスの原液で溶かす + コップやスプーンであげる → 飲まない
- 水で溶かす + スポイトであげる → 泣くしすごい暴れる。しかも慣れてくるとちょっとずつ出してくる！
⇒ふと思いつき、カルピスの原液で溶かしてスポイトであげてみました
一口目は泣きましたが、コップやスプーンと違って口に入れることができます。すると甘いのが分かったようで、なんと積極的に飲んでくれます。これは嬉しい！
方法4 : お風呂で
これも病院で言われたものではありません。
やってる途中で発見したのですが、入浴してぽかぽかになったタイミングで薬を混ぜた飲み物を差し出すと、コップで綺麗に飲み切ります。
豆乳を飲み切れる量にして、そこに薬を混ぜると成功率が高かったです。
薬は多かれ少なかれコーティングされてるので、溶けてから暫くすると苦くなっていきます。
なので作ってからすぐに飲ませたいですが、薬混ぜてるところを見せたくないので、2人以上いる時じゃないと難しいところが難点です。
番外編
試してませんが、【おくすり飲めたね】とかは結構口コミはいいので、上記方法がダメになったら試してみようと思ってます。看護師の方もお勧めしてました。
あとは2歳児くらいはまだまだ会話できないと思いがちですが、ちゃんと分かってるそうです。「これ飲めたら病院行かなくてもいいんだよ！」など根気よく伝えていくことも大事だと言っていました。
終わりに
あとは、熱が出た日から数えて2~4週間後に尿検査をする必要があるので、忘れずに行ってきます。後日検査が必要なことからも怖い病気だと感じました。（糸球体腎炎になっているかどうかを確認するためとのこと）
とにかくこれで薬10日分は乗り越えられました。
子どもが自分でできることが増え、無理やり飲ますことができない！一方、まだまだ意味は分かってないことが多く、薬などの必然性は分からないので途方に暮れる親御さんたちは多いと思います。困り果てた方々の一助になると幸いです。 また他にもいい方法がある場合、この方法は良く無いよなどがある場合は教えていただけると大変嬉しいです。
ちなみに。。。
他の病院に行ったとき、治療中の有無を聞かれたので答えると、「普通は薬飲み終わってから検尿までの間に完治したかどうかの検査をしますよ。」と言われて戸惑い中です。
何が正解か分からない。子どもにとって最も良い病院に早く出会いたいです。
お勧めの病院もあったら是非教えてください！
[Linux] duの結果の合算値を出したい
悩み
正規表現で対象絞った際にduの結果を合計する方法
悩み詳細
ディレクトリ以下全てが対象であれば、 例1）のように-s（--summarize）オプションで合計がでます。
が、その中で対象ファイルを絞った上で、合計を出せるようになったら便利！
例1）
#下記のようなディレクトリ構造の場合に
$ ls /tmp/fiets/
10test 6test 7test 8test 9test test1 test2 test3 test4 test5
#ディレクトリに対してduコマンドを実行すれば、ディレクトリ以下のサイズの合計が表示される
$ du -s /tmp/fiets
10240044 /tmp/fiets
しかし、配下の複数ファイルに対して実行した場合は、合計の計算が別途必要...
（ディレクトリ以下全てであれば、 例1） のようにディレクトリに対する実行でいいですが、 例2） のようにフィルタかけて絞りたい場合に困りました）
例2）
$ du -s /tmp/fiets/test*
1024004 /tmp/fiets/test1
1024004 /tmp/fiets/test2
1024004 /tmp/fiets/test3
1024004 /tmp/fiets/test4
1024004 /tmp/fiets/test5
解決方法
1.恒例の力技編
一応できたけど...長いしもっと良い方法ありそうだなーと思ってました。
duの結果をawkで一列目だけ取得し、それを配列に入れてからfor文ですべて足すように回す。。。なんて面倒な。
$ SUM=0;a=`du -s /tmp/fiets/test* |awk '{print $1}'`;a=(`echo $a`);for i in ${a[@]};do SUM=$(($SUM+$i));done;echo $SUM
5120020
2.awkで工夫したbetter編
awkに演算子があり、もちろん四則演算もできるので、表示したものを片っ端から足していき、最後に表示。
$ du -s /tmp/fiets/test* | awk '{sum+=$1} END {print sum}'
5120020
3. -c(--total)オプションを利用したbest編
っ！？てかこんなのありましたわ！！
-c(--tota) : 総計を表示する
$ du -c /tmp/fiets/test*
1024004 /tmp/fiets/test1
1024004 /tmp/fiets/test2
1024004 /tmp/fiets/test3
1024004 /tmp/fiets/test4
1024004 /tmp/fiets/test5
5120020 合計
やはり知ってるだけで楽になる知識ってありますね！（2回目の登場）
※1回目はこちら
豆知識
ディレクトリ以下合計値を出すとき、4KBだけ大きい？
ディレクトリごとdu -sで計算する 例3） の場合と、
ディレクトリ以下のファイルのサイズを合算する 例4） の場合とで、4KB違うのはなぜでしょう。
例3）
$ du -s /tmp/fiets
10240044 /tmp/fiets
vs
例4）
$ du -c /tmp/fiets/*
1024004 /tmp/fiets/10test
1024004 /tmp/fiets/6test
1024004 /tmp/fiets/7test
1024004 /tmp/fiets/8test
1024004 /tmp/fiets/9test
1024004 /tmp/fiets/test1
1024004 /tmp/fiets/test2
1024004 /tmp/fiets/test3
1024004 /tmp/fiets/test4
1024004 /tmp/fiets/test5
10240040 合計
ここで！それぞれバイト単位の出力に変更してみましょう。
-bオプションを付けると、出力がKB(default)→B単位になります。
#ディレクトリに対するコマンド（ディレクトリごとまるっと合計値）
$ du -sb /tmp/fiets
10485764096 /tmp/fiets
vs
#ディレクトリ以下のファイルの合算値
$ du -cb /tmp/fiets/*
1048576000 /tmp/fiets/10test
1048576000 /tmp/fiets/6test
1048576000 /tmp/fiets/7test
1048576000 /tmp/fiets/8test
1048576000 /tmp/fiets/9test
1048576000 /tmp/fiets/test1
1048576000 /tmp/fiets/test2
1048576000 /tmp/fiets/test3
1048576000 /tmp/fiets/test4
1048576000 /tmp/fiets/test5
10485760000 合計
正確には4096バイト差がありますね。なぜでしょう？
これはディレクトリ自体のサイズが入っているからです。
ディレクトリ自体のサイズは、ブロックサイズという大きさの単位で増えていき、最小でも1ブロックサイズを有します。
ブロックサイズの確認方法はファイルシステムによって変わります。
・CentOS6以下のext2,3であれば、tune2fs
# tune2fs -l /dev/mapper/VolGroup-lv_root | grep "Block size"
Block size: 4096
・CentOS7以降標準のxfsファイルシステムであれば xfs_info
# xfs_info /dev/mapper/cl-root | grep bsize | grep data
data = bsize=4096 blocks=117720064, imaxpct=25
ディレクトリ自体のサイズは何で変わる？
上で、ディレクトリはブロックサイズ単位で増えていくと書きましたが、何に起因して増大していくのでしょうか？
それは中身のサイズの総計。ではなく、ファイル数になります。
今ぱっとファイル数多そうなディレクトリを見に行きましたが、下記のようなディレクトリサイズがありました。たしかに4096が単位ですね。なるほど。
12288 (4096*3)
53248 (4096*13)
参考
[Linux] gzファイルの解凍後のサイズを知る方法
悩み
圧縮ファイルを解凍したら、どのくらいのサイズになるのか知りたい！
悩み詳細
サーバを運用していると、末尾が.gzの拡張子で終わるgzip圧縮をしているファイルをよく見かけます。
そのgzファイルを解凍する場合、一番に気になるのは解凍後のサイズです。
もちろんgzファイル自体のサイズはパッと見て分かるのですが...解凍後も分かるなら知りたいです！
解決方法
1.力技編（暫くはこれしか知りませんでした）
gzip -dcとwc -cの合わせ技
-d (--decompress,--uncompress)： 伸長する。括弧内の長いオプションからも分かるように、解凍することと同意
-c(--stdout,--to-stdout) ： 出力を標準出力に書き出し、元ファイルを変更しない
wc
-c : バイト数を集計して表示する
なので、上記コマンドを合わせることで、元ファイルそのままに中身を出力。
それをパイプ(|)でwcに渡すことで、byte数を数えることができます。
※ただこれは、全て出力してから数える作業をしてるので、大きいファイルでは時間がかかってしまいます...
例）
$ gzip -dc foo.tar.gz | wc -c
471224320
2.Better編
より良いのは、-l(--list)オプション！
gzip -l foo.tar.gz
-l (--list) ： 圧縮された個々のファイルについて、以下（例）のフィールドを列挙する
例）
$ gzip -l foo.tar.gz
compressed uncompressed ratio uncompressed_name
412408872 471224320 12.5% foo.tar
恐らくどこかで情報を持ってるのか、これは即時に返ってくる。
ここのuncompressedでも解凍後の容量分かる！
やはり知ってるだけで楽になる知識ってありますね！
豆知識
tar.gzとは
tarもgzも圧縮だと思ってる人がいましたが、tarとgzで役割が違います。
tar ： 複数のファイルを1つにまとめた“アーカイブファイル”を作成
gz ： 圧縮
➡️1つのディレクトリに纏めてから圧縮する。
というイメージです。こうすることで圧縮率も上がります。
これが分かってるとtar.gzに慣れてる人がtar.bz2とか見ても驚かなくなる？
参考
[Linux] mkdir時にアクセス権を指定する方法
【悩み】
mkdir → chmodに疲れた！
悩み詳細
mkdirでディレクトリ作成しても、デフォルトでは設定したい権限ではないことが多い...
そのため、直後にchmodを打つことが多いのですが、手間！！
せっかくPCを使用しているなら少しでも楽をしていく考え方をしないと。
※この考え方大事
（このくらい頑張ればいいじゃんのスタンスでは成長無いし、いつか溢れてしまいます）
解決方法
そこで -m (--mode) オプション！
デフォルトと比較した実行結果が下記です。
※因みに
-v (--verbose)オプションはコマンド結果を出力するためのものです。
多くのコマンドに付いていて、付けないと（特に成功した場合は）何も返ってきません。
$ ls -l
合計 0
#オプション無でdefaultディレクトリ作成
$ mkdir -v default
mkdir: created directory `default'
#-m付けてmode_rwxディレクトリ作成
$ mkdir -v -m 777 mode_rwx
mkdir: created directory `mode_rwx'
#赤字のアクセス権を表示する箇所に違いが！
$ ls -l
合計 8
drwxrwxr-x 2 works works 4096 11月 15 21:35 2019 default
drwxrwxrwx 2 works works 4096 11月 15 21:36 2019 mode_rwx
豆知識
-mオプション付けない時、ディレクトリのアクセス権はどう決まるのでしょう？
複数の環境触った方だと、各環境で違うと感じたことがあるかもしれないです。
その秘密は マスク値 です。
マスク値の最大（ディレクトリでは777） からマスク値を引いた数字がデフォルトのアクセス権になります。
マスク値はumaskで確認できます。
上の例の環境で実行してみましょう。
$ umask
0002
マスク値は002なので、
777-002=775=rwxrwxr-x
となり、デフォルトディレクトリと同じアクセス権となっています。
参考
[Linux] grepの検索対象に色を付ける方法
【悩み】
grepした時、1行が長いと対象の文字列がどこにあるか見つけるのに時間がかかる！
悩み詳細
CentOS6系以下では、デフォルトではgrepしても色がつかない。
このくらいの検索ならいいですが...
$ cat /etc/redhat-release | grep release
CentOS release 6.5 (Final)
こんな風になると、どこで引っかかってるかよく見ないと分からない。。。
（nどこー）
$ cat test.txt | grep n
aiueokakikukekosasisusesotatitutetonaninunenohahihuhehomamimumemoyayuyowawon
※上記は例ですが実際でも、、、
log解析や起動時のコマンドライン引数で長くなった文字列grepなどは大変です。
解決方法
そこでcolorオプション！
何も指定しないと赤色になります。
$ cat test.txt | grep n --color=auto aiueokakikukekosasisusesotatitutetonaninunenohahihuhehomamimumemoyayuyowawon
見やすいですね。一目でnの在処が分かります。
豆知識
実は、CentOS7ではデフォルトでもオプション無しで色がつきます。何故でしょう？
その秘密はaliasです。
下記の設定が入っており、grepを実行すると、自動でcolor=autoオプションが付くようになっています。
$ alias | grep -w grep
alias grep='grep --color=auto'
$ cat /etc/redhat-release | grep Linux
CentOS Linux release 7.6.1810 (Core)
参考
