サマリ
動機
アルゴリズムの基礎を理解する。PythonはComputer Science,Data Scienceと相性がいいから。
感想
- 人間がコンピュータにやらせたい仕事は何なのか？手動で行うことの困難さは何なのか？を考えると、なぜこの形式で運用しているのかが理解できるようになる。
- 最初の方を読み返すと、「コンピュータは何が得意で何が苦手かを学ぶ」ことが目的と書いてある。CSの入門として良い問いの立て方だなと思う。
学んだこと
はじめに
さらっと書いてあるけど、本当にそう。
現代において情報科学の基礎は必須の教養となっているが、〜
Pythonは始める敷居が低いので、「アルゴリズムを学ぶためにプログラミングを学ぶ」目的に合った言語。
- 開発環境の整備（Macにそもそも入っている、Anacondaの存在）
- とっつきやすいJupyter
- 最低限のプログラミングを動かすための覚えるべき記述が少ない
この人の考え方としては、英語のように日常で使っていなくても社会全体の多くがそれによって動いている基礎的な要素は教養として知っておくべきだと。なぜなら直接的に英語を話す機会がなかったとしても、英語を使う仕事に関わっている人とのやりとりを円滑にするという意味では、多くの人に当てはまることになるから。
プログラミングも1つの語学であり、語学のように学ぶことができる。
コンピュータが何が得意で何が苦手か理解していない人がRPAとか言っているのは危険だなと思う。
プログラミングを構成する基本的な要素は「変数、関数、配列、繰り返し、条件分岐」の5つ。確かにこの5つがわかっていれば、だいたいの操作はその組み合わせに過ぎない。
使ってみる
ごく小さい数字を扱う時の表記はeの前までの数字*10のe以降の数字乗したもの。
1.0000000000000005e-08
べき乗は掛け算・割り算よりも優先度が高い
/による割り算は整数同士であっても答えは小数表示になる。
10/1
roundは第二引数に小数点以下の桁を取れる（マイナスなら整数部分）
round(6.00,1) # 6.0
変数を使うメリット - 何の計算をしているのか確認しやすい - 再利用しやすい - 値の変更をしやすい
プログラムに限らず、自然言語であっても、「言葉に落とし込むことで、人は概念を認識できる」
プログラムを作ろう
- 「同じ処理をなんども行いたい」*は人間がコンピュータを使う主目的の一つ。
この式の結果は、2が出力されるが、TypeErrorになる。画面出力と計算結果は別物であることが分かる。（ちなみに、print(1*2の評価はNoneになる。関数にreturnがない場合はRubyと違いNoneになるため）
返り値と、出力結果は別の概念であることは初心者の引っ掛かりポイントだと思う。
print(1*2)*2
Pythonはendをつけない代わりに、インデントでブロックを表現する。この仕様は、Pythonは誰が書いても読みやすいコードになると言われる1つの大きな理由なんだろうな。
データ処理の基本
- 「大量のデータを一気に扱いたい」もコンピュータを使う主目的の一つ。
計算に関してはテストをかけるだけではなく、どの操作によって時間が変動するかを理論的に求めるのが有効。そうする事で、実行速度の差の原因を把握する事ができる
分散の定義は「平均からの差の二乗」の平均 https://mathtrain.jp/variance
演算子の優先順位。**は四則演算より優先され、notはandやorより優先される https://www.javadrive.jp/python/num/index3.html
not 1 or 1 # 1 not 1はFalseになる。 not 0 # True Pythonだと0がFalse判定のため。
stringの""と''は特に大きな違いはないが、文中に"を使うなら'の方が読みやすい、くらいのイメージ。（いくつか記事を見たがどれも同じ） http://www.koikikukan.com/archives/2019/03/13-000300.php
Pythonだと文字列の途中を変更することはできない。
x = "ggfgaa" x[1] = "b" # TypeError: 'str' object does not support item assignment
forでインデクスも同時に取得したい時はenumerate()が便利。 https://uxmilk.jp/8680
for の中外で、変数のスコープは同じなので、変数は保持される。
a = 100
for i in range(10):
a += 1
print(a) # 110
データを可視化することは、それ自体に価値があるってことを押さえておきたい。人間は視覚で情報を処理するので数字の羅列よりも処理の負荷が小さいんだろうな。
ライフゲーム
内包表記で２次元配列を作る
x = [[0 for x in range(4)] for i in range(4)] x # [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]
ちなみに、*を利用して配列を増やすと同じ配列が参照されてしまう。
x =[[0]*4]*4 x # [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]] x[0][0] = 5 x # [[5, 0, 0, 0], [5, 0, 0, 0], [5, 0, 0, 0], [5, 0, 0, 0]]
複数の数値のチェックにはin演算子が便利。
https://note.nkmk.me/python-in-basic/
シミュレーションをするときに、1個メタ的に軸を取っておくことで、状態の変化が観れる。
def lifegame(data, steps):
results = ita.array.make1d(steps)
for i in range(0,steps):
results[i] = data
data = lifegame_step(data)
return results
list index out of rangeはリストの数以上の範囲を操作しようとしていないか、チェック。
https://techacademy.jp/magazine/24167
配列の足し算は、各要素の足し算ではなく、配列をくっつけることだから注意。
[1,2,3]+[4,5,6]
appendは破壊的な変更なので注意が必要。
a = [1,2,3] a.append(4) a
listにintを+することはできない。行うならappendか、単体のlistにして+する。
y = [1, 2, 3] y + 10 # can only concatenate list (not "int") to list y + [10] # [1, 2, 3, 10]
また、strはイミュータブルなので、破壊的な変更をするappendは使えない。（+で別の文字列として加えることはできる）
"abc".append("d") # AttributeError
リスト内包は直接新しい配列が作れて便利。書き方覚える。
a = [i*2 for i in range(10) if i%2==0] a # [0, 4, 8, 12, 16]
参照元が同じになる浅いコピーを避けるには、copyライブラリを使用する。
import copy x = [0,0,0] y = [copy.copy(x), copy.copy(x)] y[0][0] = 1
さらに、通常のcopyだと配列の中身は共通の参照になってしまうので、全てcopyするにはdeepcopyを使用する。
import copy x = [0,0,0] y = [copy.copy(x),copy.copy(x)] z = copy.deepcopy(y) z[0][0] = 1 print(y,z) # [[0, 0, 0], [0, 0, 0]] [[1, 0, 0], [0, 0, 0]]
*参照元を共通にしないコピーを行うことは、時間がかかるため、明確にコピーしたい時には明示する仕様になっている。
リスト内包表記によるリストの初期化
l_2d_ok = [[0] * 4 for i in range(3)]
https://note.nkmk.me/python-list-initialize/
放物線運動
現実の現象のかなりの部分は連立微分方程式で表現される。そのため、そのシミュレーションのためには、連立微分方程式をどうプログラミングに落とし込むかを知る必要があるのだ。
厳密な結果でテストを行えれば一番だが、そもそもそれがわからないからシミュレーションをする場合が多い。可視化は動きを見て明らかにおかしな挙動がないかをチェックするのに有効な手段。
コンピュータの凄いところは、それが表している状態をプログラムすれば計算が複雑になっても対応できるところ。
オブジェクト指向的なモジュール化では、動作の主体が何なのか、何の型なのかを考える。動作の主体の型が操作を規定する考え方のため。
ステップ幅をかませて逆順にしたい時は、大きい方を先に書くのね。
list(range(10, 3, -2))
https://note.nkmk.me/python-range-usage/
テストとデバッグ
テストを行うときには以下のようなコーナーケースをサンプルに入れることで検証の精度をあげる
- 条件分岐のtrue,false両方のケース
- 比較する場合、左右が一致するケース
- 整数なら0や負の数のケース
p値の計算
p値は「ある仮説を確認しようとして実験をしたとき、その仮説が間違いであったとしても同等以上の結果が得られる確率」
p値が小さいことそのものは、その効果が偶然とは考えづらいことを表すだけで、完全な証拠そのものになるものではない。またp値自体もハックしようと思えば出来てしまうので、注視することが必要。
再帰関数での計算は、実行速度が指数関数的にかかるため、回数が増えるにつれ爆発的に時間がかかるようになる。
「プログラム」という具体的なものではなく、「本質的にどのような方法で問題を解決しているか」を考えなければ適切な比較はできない。 なのでアルゴリズムの勉強が必要
再帰関数は1.漸化式 2.小さい時の値をそのまま関数にぶち込む。
アルゴリズムの計算量は入力値によって異なるので、通常入力に対する関数として表す。
もっと言えば、明白な性能差を議論するために端数を削除した漸近最悪計算量を使用する。
モンテカルロ法の強みは「どんな複雑な形状であっても、形状の内外を判断できれば面積が求まる」点。これは確かにすごいことで、手計算だとちょっと式が複雑になる（次数が増える、定数項がつく）だけで計算がかなり煩雑になることもあるのに、それをものともしない。
大規模データの探索
アルゴリズムの計算量は最大に時間がかかるケースで見積もる。線形探索の場合、最大データ量に比例する時間がかかることになる。（だから線形って言うのかな）
二分探索自体は高速だが、そもそも配列を整列するのに線形探索以上の時間がかかる。同じデータを何度も検索する場合や最初から整列している場合に使う。
ソートの違い。.sort()はxオブジェクトに対するメソッドなのでxに影響を与えるイメージ。
x = [5,25,6,3] y = sorted(x) # 元のxはソートされない print(x,y) x.sort() # 元のxがソートされる print(x)
小さい数字から入れ替えることでソートをかけるような方法は遅い。が、追加の配列を用意する必要がないので、使うメモリの量が少なくて済むメリットがある。
単純な実行にかかる時間の計算量を「時間計算量」、メモリの使用量を「空間計算量」という。
items()は辞書型に対して、keyとvalueを同時に取得
https://note.nkmk.me/python-dict-keys-values-items/
n-gram法は文章から特定の文字数だけを順番に取り出して、当てはまりを調べる方法
whileの繰り返しを行なった場合、falseの場合は、そのあとの処理は行われない＝直前の状態で変数の値は止まっていることに注意する。
データからの情報抽出
最小2乗法の目的は、実際に得られたデータから係数を推測すること
複雑な処理をする時はモジュール化を前提に、先に全体の処理の流れを書いてしまうと実装すべきことの見通しが立つ。
def fe(a):
"""前進消去"""
for i in range(len(a)):
# i番目の式のi番目の係数を1にする
for j in range(i+1, len(a)):
# j番目の式のi番目の変数を削除
小数の計算で注意すべきは「仮数部が有限桁しかないため、それより下は四捨五入される」こと
丸め誤差が大きな影響を持つ2つのケース - 小さな誤差も許されない計算（条件分岐など） - 誤差が拡大するケース（近い値の引き算など）
桁落ち誤差は50%前後の誤差を生むことがあるので、単体の計算結果が小さかったとしても誤差で終わらせることができない差を生む可能性がある
高度な検索
抽象的な問いを考えるときは、まず問題を精緻化する。
このような問題を考える際には、まず問題を精緻化しなければならない。「豊富に含む」とはどういうことだろうか。
Python言語の簡易ガイド
Pythonのプログラムは基本「文」からなる。文の一部をなす重要な構成要素として「式」がある
文：プログラムの動きを表すもの。代入や関数定義、ifやwhileなど
式：評価結果として値を生むもの。「12」などの直接的な値も式（リテラル）
これが面白かった。Rubyだと文も評価結果を持つから、実質式である。 https://magazine.rubyist.net/articles/0039/0039-ExpressionAndStatement.html
関数内で変数を定義した時、関数内部では参照・更新が可能だが、外部からは参照も更新もできない
参照はできる例。（a += 10にするとエラーになる）
a = 100
def print_a():
b = 10 + a
print(b)
print_a() # 110
Pythonだと、0も条件分岐で偽として扱われる
