『Pythonで体験してわかるアルゴリズムとデータ構造』メモその10/そのグラフは同型か？ 隣接行列は何か
『Pythonで体験してわかるアルゴリズムとデータ構造』を読みながらアルゴリズムについて勉強する。
- 作者: 西澤弘毅,森田光
- 出版社/メーカー: 近代科学社
- 発売日: 2018/06/30
- メディア: 単行本
- この商品を含むブログを見る
第10章データ構造はなぜ重要か
この章からアルゴリズムからデータ構造の話となる。
この章のゴールは
- データ構造はなぜ重要、例を挙げて説明できるようになる。
この章では探索と木構造について説明しているが、その前にさらっと書いてあるグラフ理論について記載する。
グラフについて
そもそもグラフとはどいうものを指すのか。
グラフ理論におけるグラフ （Graph）とは、頂点(node)と辺(edge)により構成された図形のことである。 グラフ理論 - Wikipedia
つまりこんな感じ。
グラフには大きく分けて以下2つに分類される 。
- 無向グラフ (辺が向きを持たないグラフ)
- 有向グラフ (辺が向きを持つグラフ)
無向グラフは辺が向きを持たないとあるので、矢印のないパターン。
有向グラフは矢印のあるパターン。
また頂点（絵の図だとA～E）の集合をV、辺の集合をEと仮定して、あるグラフをあらわす公式が という。
この公式の考え方で、この2つを考えたとき同じなのかという話だと。同じ。
頂点の数がA～Eの5つで、辺は曲がりくねってても頂点同士をつないでいれば1と考えるので、辺の数は5。
頂点の数と、辺がどこにつながっているかを公式に当てはめると、
G = ({A,B,C,D,E}, {A-B, A-C, B-D, C-E, D-E})
となる。
じゃあ以下も同じかというと、同じではない。
頂点の数がA～Eの5つで、辺の数も5で同じなのにどうしてということだけど、頂点を通っている辺が違う。
公式に当てはめると、
G = ({A,B,C,D,E}, {A-B, A-C, B-D, C-D, D-E})
となる。
Cから通っている先がEなのか、Dなのかが違っている。
その図形が同じ形であるというのは、頂点の数も、頂点から辺に行く数とどの頂点を通っているのかも同じでないといけない。
これをグラフの同型という。
応用情報でよく出てくるどれが同型かという問題はこの考え方を理解できていると突破できる。
隣接行列
上で説明したものを数字だけで表したものを隣接行列という。 wikipediaのほうが詳しく載っている。 隣接行列 - Wikipedia
上でできている無向グラフを隣接行列に置き換えると以下のようになる。
|A|B|C|D|E
A|0|1|1|0|0
B|1|0|0|1|0
C|1|0|0|0|1
D|0|1|0|0|1
E|0|0|1|1|0
単純につながっていれば1、つながってなければ0というように表しているだけ。
上の有向グラフを隣接行列に置き換えると以下のようになる。
| A| B| C| D| E
A| 0| 1| 1| 0| 0
B|-1| 0| 0| 1| 0
C|-1| 0| 0| 1| 1
D| 0|-1|-1| 0|-1
E| 0| 0|-1|-1| 0
無向グラフに矢印の向き先を考慮させて図になる。
始点である場合1、終点である場合-1で表している。
これをプログラミングして実行したときに記憶容量（メモリ）を使用するのかという評価として領域計算量を考える。
上記のようなグラフの場合、領域計算量は、つまり縦と横の大きさによるということになる。
そりゃそうだよなって話だけども。
参考
http://www.dais.is.tohoku.ac.jp/~shioura/teaching/ad11/ad11-09.pdf
https://ocw.hokudai.ac.jp/wp-content/uploads/2016/01/GraphTheory-2007-Note-all.pdf
『Pythonで体験してわかるアルゴリズムとデータ構造』メモその9/クイックソートの早さを知ろう
『Pythonで体験してわかるアルゴリズムとデータ構造』を読みながらアルゴリズムについて勉強する。
- 作者: 西澤弘毅,森田光
- 出版社/メーカー: 近代科学社
- 発売日: 2018/06/30
- メディア: 単行本
- この商品を含むブログを見る
第9章分割統治法によるソートの分類
この章のゴールは
クイックソートとは
1960年にアントニー・ホーアが開発したソートのアルゴリズム。分割統治法の一種。
n個のデータをソートする際の最良計算量および平均計算量はO(n\log n)である。
他のソート法と比べて、一般的に最も高速だといわれているが対象のデータの並びやデータの数によっては必ずしも速いわけではなく、最悪の計算量はO(n^{2})である。また数々の変種がある。 安定ソートではない。
クイックソート - Wikipedia
クイックソートのやり方としては、適当な数（ピボット）を要素からとってきて、そのピボットよりも大きいか小さいかでまず大きく分割する。
分割を行うと、「ピボットよりも小さい値」「ピボット」「ピボットよりも大きい値」の3種類できる。
イメージとしては以下。
クイックソートの平均計算時間は となっている。
今までのソートよりも早いのだが、それはなぜか。
クイックソートは必ず上の3パターンとなる。 それが要素が1になるまで繰り返されるソートになる。
早く要素が1になってしまえば、それだけ比較回数を抑えることができる。
この場合、桁数が7に対して処理回数が3回で交換回数が10回。 普通にバブルソートで交換するよりも断トツで早いのが分かる。
逆に最悪計算時間は
ピボットに対して大きい小さいの種類が片方に寄ってしまっている場合に遭遇する。ソート済みの状態で実施すると大体こうなる。
これを見ると分かるように普通にバブルソートしているのと変わらなくなってしまう。
実装
def sort(A): if len(A) < 2: return A p = A[0] print("ピボットは{}".format(p)) X, Y = divide(p, A[1:]) print() print(X, Y, "をそれぞれ同じようにソート") return sort(X) + [p] + sort(Y) def divide(p, A): if len(A) < 1: return ([],[]) print("0番目の要素を{}を取り出す".format(A[0]),A[1:]) X, Y = divide(p, A[1:]) a = A[0] print("{}より{}が小さいか".format(p, a)) if a < p: print([a] + X, Y) return ([a] + X, Y) else: print(X, [a] + Y) return (X, [a] + Y) sort([4, 2, 3, 5, 1, 3, 2, 1, 7])
ピボットは4 0番目の要素を2を取り出す [3, 5, 1, 3, 2, 1, 7] 0番目の要素を3を取り出す [5, 1, 3, 2, 1, 7] 0番目の要素を5を取り出す [1, 3, 2, 1, 7] 0番目の要素を1を取り出す [3, 2, 1, 7] 0番目の要素を3を取り出す [2, 1, 7] 0番目の要素を2を取り出す [1, 7] 0番目の要素を1を取り出す [7] 0番目の要素を7を取り出す [] 4より7が小さいか [] [7] 4より1が小さいか [1] [7] 4より2が小さいか [2, 1] [7] 4より3が小さいか [3, 2, 1] [7] 4より1が小さいか [1, 3, 2, 1] [7] 4より5が小さいか [1, 3, 2, 1] [5, 7] 4より3が小さいか [3, 1, 3, 2, 1] [5, 7] 4より2が小さいか [2, 3, 1, 3, 2, 1] [5, 7] [2, 3, 1, 3, 2, 1] [5, 7] をそれぞれ同じようにソート ピボットは2 0番目の要素を3を取り出す [1, 3, 2, 1] 0番目の要素を1を取り出す [3, 2, 1] 0番目の要素を3を取り出す [2, 1] 0番目の要素を2を取り出す [1] 0番目の要素を1を取り出す [] 2より1が小さいか [1] [] 2より2が小さいか [1] [2] 2より3が小さいか [1] [3, 2] 2より1が小さいか [1, 1] [3, 2] 2より3が小さいか [1, 1] [3, 3, 2] [1, 1] [3, 3, 2] をそれぞれ同じようにソート ピボットは1 0番目の要素を1を取り出す [] 1より1が小さいか [] [1] [] [1] をそれぞれ同じようにソート ピボットは3 0番目の要素を3を取り出す [2] 0番目の要素を2を取り出す [] 3より2が小さいか [2] [] 3より3が小さいか [2] [3] [2] [3] をそれぞれ同じようにソート ピボットは5 0番目の要素を7を取り出す [] 5より7が小さいか [] [7] [] [7] をそれぞれ同じようにソート [1, 1, 2, 2, 3, 3, 4, 5, 7]
トップ20からわかるアイカツ！アイドル総選挙最終結果
『アイカツオンパレード！』開始を記念したアイドル総選挙の最終結果が発表されましたね。
データカードダス アイドル総選挙最終結果発表✨見事、1位に輝いたアイドルは…
— アイカツ！データカードダス公式 (@aikatsu_dcd) September 30, 2019
👑1位 七倉小春ちゃん
です！小春ちゃんの新しいプレミアムレアドレスがアイカツ！カードになるよ💖たくさんの投票ありがとう✨
1〜20位まではHPでチェック！https://t.co/OTwggrRLbI#aikatsu #小春ちゃんおめでとう pic.twitter.com/DdW57DvTfa
1位は七倉小春！
中間では藤堂ユリカ様に次ぐ2位だったが、結果は2,000票差をつけての1位。
1位になったので新しいプレミアムドレスのカードが登場することに。
七倉小春ファンの人おめでとうございます！
物語的にも割と裏方の役が多かった小春ちゃんがプレミアムドレスを着れるというのはファン冥利に尽きると思います。
結果を見ると1位から3位と4位の差が約14,000票差で、かなり開いていたのが驚き。
4位が星宮いちごなので、根強いファン層がいるような気がしていたけど新規ドレスが確定しているから票が入りにくかったというのもあるのかなーと。
最終結果のトップ20の情報から分かること
上のサイトの最終結果に情報を付け加えたリストがこれです。
順位の変動はあるものの、中間結果でランクインされている20人がそのままランクインされた形となった感じ。
10位以下は得票数の公開はされていないが、20位以下はひっくり返すには票差があまりについている状況だったのでは？と推測。
ランクインされているキャラクターの傾向については以前書いたので、そちらを参照ください。
この投票に関する数字
2019/8/19から2019/9/17の29日間の投票期間で、投票総数が309,459だったので、単純に一日平均10,671票が投じられていたと思われる。
投票数が判明しているトップ10の得票総数が185,552票なので、全体の約60パーセントがトップ10のキャラクターで占めらえていることになる。
投票可能キャラクターが56人だったので、46人が残りの40パーセントの中にいることになるんだけど、じゃあその46人がそれぞれどのくらいのパーセンテージだったのかって話。
これはあくまで俺の想像でしかないけど、おそらく20位までは大体1～2パーセント未満くらいで、約3,000～6,000票の範囲であろうと推測される。
20位以下は1パーセント未満～1パーセントくらい、おそらく約3,000票を切っているのではと。
おそらく50位以下は1,000票も獲得していないのではないかと思う。
ただ、これだけは言わなきゃいけないなっていうのは、得票数が少ない＝そのアイドル自体がダメとかいいとかそういう優劣の話ではないよってこと。
自分にとって推しだと思ったアイドルがトップ20に来なくても、俺が推していて俺はできる限り投票した、それでいいじゃないって話。
あんなむちゃくちゃ可愛い双葉アリアがトップ20に来ないのはおかしいじゃん。
各シリーズ単位のランクイン数
各シリーズ単位でのランクイン数も見てみる。
『アイカツ!』が最も多い10人。
『アイカツ!』キャラは根強い人気があるのがここで見て取れる。
逆に『アイカツフレンズ!』キャラは3人と、投票期間時の現行シリーズの割には少ない印象を受ける。
やっぱり個よりはフレンズ（複数）がメインだったから票が入りにくかったのかもしれないなー。
属性別のランクイン数
次に属性単位でのランクイン数を見てみる。
トップはクールで、7人。全体の約35パーセント。
ランクインを見る限り7位から11位までを独占しているような形になっている。
この辺りのクールキャラは氷上スミレ然り、騎咲レイ然り女性人気がかなり高そうなので、上位に入ってきたのかなと。
俺の推しの霧矢あおいも中間から順位を下げたものの、7位でゴール。
ランキング系をウォッチしていると、だいたいトップ10だけど7位とかそういう何とも微妙なところにいるなっていうのは正直ある。
頑張って上にあげてあげたい。
ポップキャラが3人というのがちょっと少なかったかなってという印象。
有栖川おとめがランクインしていないのもかなり意外だったかな。
藤堂ユリカ様vs七倉小春
これは完全に推測の話。
藤堂ユリカ様vs七倉小春の戦いの流れを想像してみる。
2019/9/4の中間発表時点では藤堂ユリカ様が1位。
それから2019/9/13時点でもう一度中間発表があった時点では七倉小春が1位になっているので、11日間の間で追い抜かしていることになる。
また中間発表から投票終了日までの14日間で票差を2,000票つけている。
そこから考えるに七倉小春票は、1日「ユリカ様の投票数と同数＋140票」程度投票されていたと考えられる。
140票差、つまり140プレイで14,000円なので、1日最低でも七倉小春のために14,000円が動いているのでは？？？（あくまで推測）
これを考えると、諭吉を注げば逆転はいつでも可能ということになりますね。
『Pythonで体験してわかるアルゴリズムとデータ構造』メモその8/動的計画法で最短距離を求める
『Pythonで体験してわかるアルゴリズムとデータ構造』を読みながらアルゴリズムについて勉強する。
- 作者: 西澤弘毅,森田光
- 出版社/メーカー: 近代科学社
- 発売日: 2018/06/30
- メディア: 単行本
- この商品を含むブログを見る
第7章 問題に適した設計法とは
前回のハノイの塔問題に引き続き、今回は最短経路の数え上げ問題を考える。
最短経路の数え上げ問題について
高校数学で出てくる問題ひとつ。
格子状の道があったとして、スタートからゴールまでの最短経路は何パターンあるかという問題。
格子状の道の中には通過することができない箇所も存在する。
この問題のイメージ、数学的な解き方については以下動画が詳しい。
動画上では階乗を使用した商を出して最短距離も求めていたが、動的計画法を用いて解いていくのがこの章の考え方なので、 以下サイトの書き込み方式の考え方で解いていく。
ルールとしては、
- 左上にスタート、右下がゴールとして設定
- どのように追加してもよいが、上下作用で移動すること。斜め移動はNG
- 最短距離を目指すので、迂回はしない
- 通過することができないマスが存在する
このような5×6の格子状の道があったとした場合、最短距離で行くのであれば右上から左下にいくという前提があるので、赤字（Ⅰの行と1の列）は1回しか通ることができない。
では、青文字のⅡ-2ところは何回通るかというと、緑の赤字Ⅰ-2とオレンジの赤字Ⅱ-1から通ることになる。
つまりⅡ-2は2通り通る方法があるということになる。
更にここから分かるのは、求めたいマスの上のマスと左のマスの値を合算することで、そのマスを通過するのは何通りか特定することができる。
ルールにある「通過できないマス」についても基本的な考えは変わらない。
通れないマスは、そこに行くパターンはない（通過できないので）ので、行くパターンは0通り。
事前に0埋めしておくことでⅢ-3を計算したいときに 3 + 0 =3 となる。
実装
def counting(a, b, X): # 格子状の道のイメージを表現する。リスト型の制限で不要な0番目が生成される。 A = [[-1 for j in range(b + 1)] for i in range(a+1)] print(A) print() #格子状の道の0番目列は不要なので、0埋めする。 for i in range(a+1): A[i][0] = 0 print(A) print() #格子状の道の0番目行は不要なので、0埋めする。 for j in range(b+1): A[0][j] = 0 print(A) print() # 通過できないところを事前に0で埋めておく for (i,j) in X: A[i][j] = 0 print(A) print() #スタートは必ず通り、1通りなので1をセットしておく A[1][1] = 1 for i in range(1, a+1): for j in range(1, b+1): if A[i][j] == -1: A[i][j] = A[i-1][j] + A[i][j-1] print("{}-{}番目を通過するのは{}+{}で{}通り".format(i, j, A[i-1][j], A[i][j-1], A[i][j])) return A[a][b] counting(5,6,[(2,3),(4,5)])
[[-1, -1, -1, -1, -1, -1, -1], [-1, -1, -1, -1, -1, -1, -1], [-1, -1, -1, -1, -1, -1, -1], [-1, -1, -1, -1, -1, -1, -1], [-1, -1, -1, -1, -1, -1, -1], [-1, -1, -1, -1, -1, -1, -1]] [[0, -1, -1, -1, -1, -1, -1], [0, -1, -1, -1, -1, -1, -1], [0, -1, -1, -1, -1, -1, -1], [0, -1, -1, -1, -1, -1, -1], [0, -1, -1, -1, -1, -1, -1], [0, -1, -1, -1, -1, -1, -1]] [[0, 0, 0, 0, 0, 0, 0], [0, -1, -1, -1, -1, -1, -1], [0, -1, -1, -1, -1, -1, -1], [0, -1, -1, -1, -1, -1, -1], [0, -1, -1, -1, -1, -1, -1], [0, -1, -1, -1, -1, -1, -1]] [[0, 0, 0, 0, 0, 0, 0], [0, -1, -1, -1, -1, -1, -1], [0, -1, -1, 0, -1, -1, -1], [0, -1, -1, -1, -1, -1, -1], [0, -1, -1, -1, -1, 0, -1], [0, -1, -1, -1, -1, -1, -1]] 1-2番目を通過するのは0+1で1通り 1-3番目を通過するのは0+1で1通り 1-4番目を通過するのは0+1で1通り 1-5番目を通過するのは0+1で1通り 1-6番目を通過するのは0+1で1通り 2-1番目を通過するのは1+0で1通り 2-2番目を通過するのは1+1で2通り 2-4番目を通過するのは1+0で1通り 2-5番目を通過するのは1+1で2通り 2-6番目を通過するのは1+2で3通り 3-1番目を通過するのは1+0で1通り 3-2番目を通過するのは2+1で3通り 3-3番目を通過するのは0+3で3通り 3-4番目を通過するのは1+3で4通り 3-5番目を通過するのは2+4で6通り 3-6番目を通過するのは3+6で9通り 4-1番目を通過するのは1+0で1通り 4-2番目を通過するのは3+1で4通り 4-3番目を通過するのは3+4で7通り 4-4番目を通過するのは4+7で11通り 4-6番目を通過するのは9+0で9通り 5-1番目を通過するのは1+0で1通り 5-2番目を通過するのは4+1で5通り 5-3番目を通過するのは7+5で12通り 5-4番目を通過するのは11+12で23通り 5-5番目を通過するのは0+23で23通り 5-6番目を通過するのは9+23で32通り
『Pythonで体験してわかるアルゴリズムとデータ構造』メモその7/ハノイの崇高なる力を経験する
『Pythonで体験してわかるアルゴリズムとデータ構造』を読みながらアルゴリズムについて勉強する。
- 作者: 西澤弘毅,森田光
- 出版社/メーカー: 近代科学社
- 発売日: 2018/06/30
- メディア: 単行本
- この商品を含むブログを見る
第7章 問題に適した設計法とは
この章のゴールは 与えられた問題に、分割統治法と、動的計画法のどちらが向いているかを判断できるようになる
書籍中ではハノイの塔問題、最短経路の数え上げ問題を例にとって説明している。
ハノイの塔について
以下のルールに従ってすべての円盤を右端の杭に移動させられれば完成。
3本の杭と、中央に穴の開いた大きさの異なる複数の円盤から構成される。
最初はすべての円盤が左端の杭に小さいものが上になるように順に積み重ねられている。
円盤を一回に一枚ずつどれかの杭に移動させることができるが、小さな円盤の上に大きな円盤を乗せることはできない。n枚の円盤すべてを移動させるには最低 2n − 1 回の手数がかかる。 解法に再帰的アルゴリズムが有効な問題として有名であり、プログラミングにおける再帰的呼出しの例題としてもよく用いられる。ただし支配数がメルセンヌ数なので、同じく再帰の例題として多用されるフィボナッチ数同様、再帰をストレートに実装するととんでもない事態を生む例でもある。 ハノイの塔 - Wikipedia
パズルのひとつで、動画で見ると分かりやすい。
www.youtube.com
こんな感じで、必ず大-中-小（大-小）の順番で並ばなければならないゲーム。
遊戯王プレイヤーはおそらくこのワードを聞くと
(C)高橋和希 スタジオ・ダイス／集英社・テレビ東京・ＮＡＳ
これを思い出すのかなと。
俺はもうこのイメージしかない。
今回はミラフォの話でも、王宮のお触れの話でもなく、アルゴリズムの話。
何故最低2n -1なのか
以下動画を見るとイメージがつかみやすい。
円盤が3個あるとして、大きく「1と2の固まり」と「3個目」で分割する。
「1と2の固まり」は3回移動することで1個目の下に2個目が来ることが分かっているので、それに加えて3個目として1回移動させてあげればよい。
ただそれだと、1個目の下に2個目、2個目の下に3個目が来ないので、「1と2の固まり」をもう一度移動してあげる必要がある。
3回＋1回＋3回＝7回。7回移動すると1個目の下に2個目、2個目の下に3個目が来ることになる。
漸化式で考えると、
「1と2の固まり」をn、「3個目」をn+1とした場合 [tex:a_{n+1} = 2a_{n+1}] （3個移動したいのであれば、2×3+1） [tex: a_{1} = 1]とした場合に、漸化式を解くと、 [tex: a_{n+1} + 1 = 2( a_{n+1} )] となる。
数列 [tex: a_{n+1} = 1] は、初稿がa1=2、公比が2の等比数列なので、2n - 1になる。
なんだか難しいことを書いていて正直俺もそんなによくわかってないが、重要なのは上の大きく「1と2の固まり」と「3個目」で分けてしまうということ。
実装
ハノイの塔は、再帰の典型的なパターンとのことで、再帰といえば分割統治法。
ということで分割統治法の考え方のトップダウンから考えた場合の処理を書いてみる。
def move(k,start,yobi,end): print("") print("今{}の処理だよ".format(k)) if k >= 2: print("{}のa処理に入るよ".format(k-1)) move(k-1, start, end, yobi) print("") print("今{}の処理だよ".format(k)) print("{}を{}から{}軸へ移動".format(k,start, end)) if k >= 2: print("b処理に入るよ") move(k-1, yobi,start, end) move(3,1,2,3)
今3の処理だよ 2のa処理に入るよ 今2の処理だよ 1のa処理に入るよ 今1の処理だよ 今1の処理だよ 1を1から3軸へ移動 今2の処理だよ 2を1から2軸へ移動 b処理に入るよ 今1の処理だよ 今1の処理だよ 1を3から2軸へ移動 今3の処理だよ 3を1から3軸へ移動 b処理に入るよ 今2の処理だよ 1のa処理に入るよ 今1の処理だよ 今1の処理だよ 1を2から1軸へ移動 今2の処理だよ 2を2から3軸へ移動 b処理に入るよ 今1の処理だよ 今1の処理だよ 1を1から3軸へ移動
『Pythonで体験してわかるアルゴリズムとデータ構造』メモその6/分割統治法と動的計画法を知る
『Pythonで体験してわかるアルゴリズムとデータ構造』を読みながらアルゴリズムについて勉強する。
- 作者: 西澤弘毅,森田光
- 出版社/メーカー: 近代科学社
- 発売日: 2018/06/30
- メディア: 単行本
- この商品を含むブログを見る
第6章 アルゴリズムを設計する方法
この章のゴールは 複雑な問題を解く際にアルゴリズムをどのような方針で設計したらよいか、説明できるようになる
書籍中ではフィボナッチ数列を例にとって説明している。
フィボナッチ数列について
「フィボナッチ数列」とは，「前の２つの数を加えると次の数になる」という数列です。 ただし，１番目と２番目の数は両方とも１です。
フィボナッチ数列と中学入試問題 - すぐる学習会
どういうことかというと、
0, 1, 1, 2, 3, 5, 8, 12, 21, 34 …
上のような何かのルールにのっとっている数字の列をフィボナッチ数列という。 *1
そのルールが上の「前の２つの数を加えると次の数になる」。
基本的に0番目は0、1番目は１出ることがこの数列のルールになる。
3番目の結果は、0番目＋1番目＝1。
4番目の結果は、2番目＋3番目＝2。
というようにルールに合わせると結果が求められる。
フィボナッチ数列は、自然界にあふれていて枝の数や、ひまわりの種の数、カタツムリの殻の形などはフィボナッチ数列でできている。
上の話を漸化式で考えると
じゃあこれをどのように実装するのかというところで、アルゴリズムを考えていく上での解き方を考える。
分割統治法
そのままでは解決できない大きな問題を小さな問題に分割し、その全てを解決することで、最終的に最初の問題全体を解決する、という問題解決の手法である。
分割統治法 - Wikipedia
与えられた課題大きな回答を出すときに、力づくで解くのではなく、ある程度小さく区切って処理をしてしまおうという考え方。
小さく区切る＝再帰呼び出しを行って、自身を何度も呼び出すことで小さい処理を行っていく。
ただし、再起呼び出しするので、同じ処理を何度も繰り返すために、無駄な処理を繰り返しメモリ領域をひっ迫する可能性がある。
実装
6という大きな数字を分割し続けて、回答を出していく
def fib(n): print("{}の処理".format(n)) if n < 2: return n else: print("{}のa処理へ".format(n-1)) print() a = fib(n-1) print() print("{}のb処理へ".format(n-2)) b = fib(n-2) c=a+b print("{}={}+{}".format(c,a,b)) return c ans = fib(6) print() print("結果", ans)
6の処理 5のa処理へ 5の処理 4のa処理へ 4の処理 3のa処理へ 3の処理 2のa処理へ 2の処理 1のa処理へ 1の処理 0のb処理へ 0の処理 1=1+0 1のb処理へ 1の処理 2=1+1 2のb処理へ 2の処理 1のa処理へ 1の処理 0のb処理へ 0の処理 1=1+0 3=2+1 3のb処理へ 3の処理 2のa処理へ 2の処理 1のa処理へ 1の処理 0のb処理へ 0の処理 1=1+0 1のb処理へ 1の処理 2=1+1 5=3+2 4のb処理へ 4の処理 3のa処理へ 3の処理 2のa処理へ 2の処理 1のa処理へ 1の処理 0のb処理へ 0の処理 1=1+0 1のb処理へ 1の処理 2=1+1 2のb処理へ 2の処理 1のa処理へ 1の処理 0のb処理へ 0の処理 1=1+0 3=2+1 8=5+3 結果 8
やっぱり再帰的定義で実装するといまいちよくわからなくなるよなあ。
動的計画法
分割統治法の計算は無駄なので、計算結果を保存しておいて再利用していけば無駄なメモリを使わなくてよいのでは？というのが動的計画法。
フィボナッチ数列で考えるのであれば、配列の0番目から順番に計算することで、配列にすでに突っ込んだデータを流用できるよねという考え方。
人間が純粋にイメージするような計算手法。
欠点は小問題が多い場合、使用頻度の低いデータがメモリに残りっぱなしになること。
フィボナッチ数列だと、要素6番目まではいいけど1000番目のときに、0番目の要素って全然使ってないから無駄にメモリ食ってない？ってこと。
実装
def fib(n): A = [None] * (n+1) print(A) A[0] = 0 A[1] = 1 print(A) for i in range(2, n+1): A[i] = A[i-1] + A[i-2] print(A) return A[n] ans = fib(6) print() print("結果", ans)
[None, None, None, None, None, None, None] [0, 1, None, None, None, None, None] [0, 1, 1, None, None, None, None] [0, 1, 1, 2, None, None, None] [0, 1, 1, 2, 3, None, None] [0, 1, 1, 2, 3, 5, None] [0, 1, 1, 2, 3, 5, 8]
その他参考
*1:数列なので、先頭の0は1番目ではなく0番目
『Pythonで体験してわかるアルゴリズムとデータ構造』メモその5/バブルソートを改良しよう
『Pythonで体験してわかるアルゴリズムとデータ構造』を読みながらアルゴリズムについて勉強する。
- 作者: 西澤弘毅,森田光
- 出版社/メーカー: 近代科学社
- 発売日: 2018/06/30
- メディア: 単行本
- この商品を含むブログを見る
第5章 アルゴリズムを改良するコツ
この章のゴールは アルゴリズムを改良するには、どこに着目すればよいか
書籍中ではバブルソートを例にとって説明している。
バブルソートについて
バブルソート
ソートのアルゴリズムの一つ。隣り合う要素の大小を比較しながら整列させること。最悪計算時間がO(n2)と遅いが、アルゴリズムが単純で実装が容易なため、また並列処理との親和性が高いことから、しばしば用いられる。安定な内部ソート。基本交換法、隣接交換法ともいう。（単に交換法と言う場合もある）
バブルソート - Wikipedia
この動画を見るとどういう処理か分かりやすい。
要は背比べを順番にやっていくだけのソート。
全要素について確認を行っていくため最良計算時間はO(n)、平均計算時間はO(n2)。
平均計算時間がO(n2)なので、以下にもある通り、値の比較をn-1回を続けるため。
イメージは以下となる。
実装
def bubble_sort(array): n = len(array) for i in range(0, n-1): print("{}回目処理".format(str(i+1))) for j in range(0, n-1): print("処理対象{}・比較対象{}".format(array[j],array[j+1])) if array[j+1] < array[j]: array[j+1], array[j] = array[j], array[j+1] print(array) print("{}回目処理終了".format(str(i+1))) print() array = [1,2,3,4,5,3,2,1,7,0] print("処理前：", array) print("") bubble_sort(array) print("処理後 ", array)
処理前： [1, 2, 3, 4, 5, 3, 2, 1, 7, 0] 1回目処理 処理対象1・比較対象2 [1, 2, 3, 4, 5, 3, 2, 1, 7, 0] 処理対象2・比較対象3 [1, 2, 3, 4, 5, 3, 2, 1, 7, 0] 処理対象3・比較対象4 [1, 2, 3, 4, 5, 3, 2, 1, 7, 0] 処理対象4・比較対象5 [1, 2, 3, 4, 5, 3, 2, 1, 7, 0] 処理対象5・比較対象3 [1, 2, 3, 4, 3, 5, 2, 1, 7, 0] 処理対象5・比較対象2 [1, 2, 3, 4, 3, 2, 5, 1, 7, 0] 処理対象5・比較対象1 [1, 2, 3, 4, 3, 2, 1, 5, 7, 0] 処理対象5・比較対象7 [1, 2, 3, 4, 3, 2, 1, 5, 7, 0] 処理対象7・比較対象0 [1, 2, 3, 4, 3, 2, 1, 5, 0, 7] 1回目処理終了 2回目処理 処理対象1・比較対象2 [1, 2, 3, 4, 3, 2, 1, 5, 0, 7] 処理対象2・比較対象3 [1, 2, 3, 4, 3, 2, 1, 5, 0, 7] 処理対象3・比較対象4 [1, 2, 3, 4, 3, 2, 1, 5, 0, 7] 処理対象4・比較対象3 [1, 2, 3, 3, 4, 2, 1, 5, 0, 7] 処理対象4・比較対象2 [1, 2, 3, 3, 2, 4, 1, 5, 0, 7] 処理対象4・比較対象1 [1, 2, 3, 3, 2, 1, 4, 5, 0, 7] 処理対象4・比較対象5 [1, 2, 3, 3, 2, 1, 4, 5, 0, 7] 処理対象5・比較対象0 [1, 2, 3, 3, 2, 1, 4, 0, 5, 7] 処理対象5・比較対象7 [1, 2, 3, 3, 2, 1, 4, 0, 5, 7] 2回目処理終了 3回目処理 処理対象1・比較対象2 [1, 2, 3, 3, 2, 1, 4, 0, 5, 7] 処理対象2・比較対象3 [1, 2, 3, 3, 2, 1, 4, 0, 5, 7] 処理対象3・比較対象3 [1, 2, 3, 3, 2, 1, 4, 0, 5, 7] 処理対象3・比較対象2 [1, 2, 3, 2, 3, 1, 4, 0, 5, 7] 処理対象3・比較対象1 [1, 2, 3, 2, 1, 3, 4, 0, 5, 7] 処理対象3・比較対象4 [1, 2, 3, 2, 1, 3, 4, 0, 5, 7] 処理対象4・比較対象0 [1, 2, 3, 2, 1, 3, 0, 4, 5, 7] 処理対象4・比較対象5 [1, 2, 3, 2, 1, 3, 0, 4, 5, 7] 処理対象5・比較対象7 [1, 2, 3, 2, 1, 3, 0, 4, 5, 7] 3回目処理終了 4回目処理 処理対象1・比較対象2 [1, 2, 3, 2, 1, 3, 0, 4, 5, 7] 処理対象2・比較対象3 [1, 2, 3, 2, 1, 3, 0, 4, 5, 7] 処理対象3・比較対象2 [1, 2, 2, 3, 1, 3, 0, 4, 5, 7] 処理対象3・比較対象1 [1, 2, 2, 1, 3, 3, 0, 4, 5, 7] 処理対象3・比較対象3 [1, 2, 2, 1, 3, 3, 0, 4, 5, 7] 処理対象3・比較対象0 [1, 2, 2, 1, 3, 0, 3, 4, 5, 7] 処理対象3・比較対象4 [1, 2, 2, 1, 3, 0, 3, 4, 5, 7] 処理対象4・比較対象5 [1, 2, 2, 1, 3, 0, 3, 4, 5, 7] 処理対象5・比較対象7 [1, 2, 2, 1, 3, 0, 3, 4, 5, 7] 4回目処理終了 5回目処理 処理対象1・比較対象2 [1, 2, 2, 1, 3, 0, 3, 4, 5, 7] 処理対象2・比較対象2 [1, 2, 2, 1, 3, 0, 3, 4, 5, 7] 処理対象2・比較対象1 [1, 2, 1, 2, 3, 0, 3, 4, 5, 7] 処理対象2・比較対象3 [1, 2, 1, 2, 3, 0, 3, 4, 5, 7] 処理対象3・比較対象0 [1, 2, 1, 2, 0, 3, 3, 4, 5, 7] 処理対象3・比較対象3 [1, 2, 1, 2, 0, 3, 3, 4, 5, 7] 処理対象3・比較対象4 [1, 2, 1, 2, 0, 3, 3, 4, 5, 7] 処理対象4・比較対象5 [1, 2, 1, 2, 0, 3, 3, 4, 5, 7] 処理対象5・比較対象7 [1, 2, 1, 2, 0, 3, 3, 4, 5, 7] 5回目処理終了 6回目処理 処理対象1・比較対象2 [1, 2, 1, 2, 0, 3, 3, 4, 5, 7] 処理対象2・比較対象1 [1, 1, 2, 2, 0, 3, 3, 4, 5, 7] 処理対象2・比較対象2 [1, 1, 2, 2, 0, 3, 3, 4, 5, 7] 処理対象2・比較対象0 [1, 1, 2, 0, 2, 3, 3, 4, 5, 7] 処理対象2・比較対象3 [1, 1, 2, 0, 2, 3, 3, 4, 5, 7] 処理対象3・比較対象3 [1, 1, 2, 0, 2, 3, 3, 4, 5, 7] 処理対象3・比較対象4 [1, 1, 2, 0, 2, 3, 3, 4, 5, 7] 処理対象4・比較対象5 [1, 1, 2, 0, 2, 3, 3, 4, 5, 7] 処理対象5・比較対象7 [1, 1, 2, 0, 2, 3, 3, 4, 5, 7] 6回目処理終了 7回目処理 処理対象1・比較対象1 [1, 1, 2, 0, 2, 3, 3, 4, 5, 7] 処理対象1・比較対象2 [1, 1, 2, 0, 2, 3, 3, 4, 5, 7] 処理対象2・比較対象0 [1, 1, 0, 2, 2, 3, 3, 4, 5, 7] 処理対象2・比較対象2 [1, 1, 0, 2, 2, 3, 3, 4, 5, 7] 処理対象2・比較対象3 [1, 1, 0, 2, 2, 3, 3, 4, 5, 7] 処理対象3・比較対象3 [1, 1, 0, 2, 2, 3, 3, 4, 5, 7] 処理対象3・比較対象4 [1, 1, 0, 2, 2, 3, 3, 4, 5, 7] 処理対象4・比較対象5 [1, 1, 0, 2, 2, 3, 3, 4, 5, 7] 処理対象5・比較対象7 [1, 1, 0, 2, 2, 3, 3, 4, 5, 7] 7回目処理終了 8回目処理 処理対象1・比較対象1 [1, 1, 0, 2, 2, 3, 3, 4, 5, 7] 処理対象1・比較対象0 [1, 0, 1, 2, 2, 3, 3, 4, 5, 7] 処理対象1・比較対象2 [1, 0, 1, 2, 2, 3, 3, 4, 5, 7] 処理対象2・比較対象2 [1, 0, 1, 2, 2, 3, 3, 4, 5, 7] 処理対象2・比較対象3 [1, 0, 1, 2, 2, 3, 3, 4, 5, 7] 処理対象3・比較対象3 [1, 0, 1, 2, 2, 3, 3, 4, 5, 7] 処理対象3・比較対象4 [1, 0, 1, 2, 2, 3, 3, 4, 5, 7] 処理対象4・比較対象5 [1, 0, 1, 2, 2, 3, 3, 4, 5, 7] 処理対象5・比較対象7 [1, 0, 1, 2, 2, 3, 3, 4, 5, 7] 8回目処理終了 9回目処理 処理対象1・比較対象0 [0, 1, 1, 2, 2, 3, 3, 4, 5, 7] 処理対象1・比較対象1 [0, 1, 1, 2, 2, 3, 3, 4, 5, 7] 処理対象1・比較対象2 [0, 1, 1, 2, 2, 3, 3, 4, 5, 7] 処理対象2・比較対象2 [0, 1, 1, 2, 2, 3, 3, 4, 5, 7] 処理対象2・比較対象3 [0, 1, 1, 2, 2, 3, 3, 4, 5, 7] 処理対象3・比較対象3 [0, 1, 1, 2, 2, 3, 3, 4, 5, 7] 処理対象3・比較対象4 [0, 1, 1, 2, 2, 3, 3, 4, 5, 7] 処理対象4・比較対象5 [0, 1, 1, 2, 2, 3, 3, 4, 5, 7] 処理対象5・比較対象7 [0, 1, 1, 2, 2, 3, 3, 4, 5, 7] 9回目処理終了 処理後 [0, 1, 1, 2, 2, 3, 3, 4, 5, 7]
アルゴリズムを改良する
実装したバブルソートは、すでに確定してしまっている桁数に対してももう一度交換してしまっている。
これは無駄な処理なので、確定済については処理しないように実装する。
def bubble_sort(array): n = len(array) end_exchenge=n for i in range(0, n-1): print("{}回目処理".format(str(i+1))) for j in range(0, n-1): # すでに確定してしまった処理はスキップする if end_exchenge == j: break; print("処理対象{}・比較対象{}".format(array[j],array[j+1])) if array[j+1] < array[j]: array[j+1], array[j] = array[j], array[j+1] print(array) end_exchenge -= 1 print("{}回目処理終了".format(str(i+1))) print() array = [1,2,3,4,5,3,2,1,7,0] print("処理前：", array) print("") bubble_sort(array) print("処理後 ", array)
処理前： [1, 2, 3, 4, 5, 3, 2, 1, 7, 0] 1回目処理 処理対象1・比較対象2 [1, 2, 3, 4, 5, 3, 2, 1, 7, 0] 処理対象2・比較対象3 [1, 2, 3, 4, 5, 3, 2, 1, 7, 0] 処理対象3・比較対象4 [1, 2, 3, 4, 5, 3, 2, 1, 7, 0] 処理対象4・比較対象5 [1, 2, 3, 4, 5, 3, 2, 1, 7, 0] 処理対象5・比較対象3 [1, 2, 3, 4, 3, 5, 2, 1, 7, 0] 処理対象5・比較対象2 [1, 2, 3, 4, 3, 2, 5, 1, 7, 0] 処理対象5・比較対象1 [1, 2, 3, 4, 3, 2, 1, 5, 7, 0] 処理対象5・比較対象7 [1, 2, 3, 4, 3, 2, 1, 5, 7, 0] 処理対象7・比較対象0 [1, 2, 3, 4, 3, 2, 1, 5, 0, 7] 1回目処理終了 2回目処理 処理対象1・比較対象2 [1, 2, 3, 4, 3, 2, 1, 5, 0, 7] 処理対象2・比較対象3 [1, 2, 3, 4, 3, 2, 1, 5, 0, 7] 処理対象3・比較対象4 [1, 2, 3, 4, 3, 2, 1, 5, 0, 7] 処理対象4・比較対象3 [1, 2, 3, 3, 4, 2, 1, 5, 0, 7] 処理対象4・比較対象2 [1, 2, 3, 3, 2, 4, 1, 5, 0, 7] 処理対象4・比較対象1 [1, 2, 3, 3, 2, 1, 4, 5, 0, 7] 処理対象4・比較対象5 [1, 2, 3, 3, 2, 1, 4, 5, 0, 7] 処理対象5・比較対象0 [1, 2, 3, 3, 2, 1, 4, 0, 5, 7] 処理対象5・比較対象7 [1, 2, 3, 3, 2, 1, 4, 0, 5, 7] 2回目処理終了 3回目処理 処理対象1・比較対象2 [1, 2, 3, 3, 2, 1, 4, 0, 5, 7] 処理対象2・比較対象3 [1, 2, 3, 3, 2, 1, 4, 0, 5, 7] 処理対象3・比較対象3 [1, 2, 3, 3, 2, 1, 4, 0, 5, 7] 処理対象3・比較対象2 [1, 2, 3, 2, 3, 1, 4, 0, 5, 7] 処理対象3・比較対象1 [1, 2, 3, 2, 1, 3, 4, 0, 5, 7] 処理対象3・比較対象4 [1, 2, 3, 2, 1, 3, 4, 0, 5, 7] 処理対象4・比較対象0 [1, 2, 3, 2, 1, 3, 0, 4, 5, 7] 処理対象4・比較対象5 [1, 2, 3, 2, 1, 3, 0, 4, 5, 7] 3回目処理終了 4回目処理 処理対象1・比較対象2 [1, 2, 3, 2, 1, 3, 0, 4, 5, 7] 処理対象2・比較対象3 [1, 2, 3, 2, 1, 3, 0, 4, 5, 7] 処理対象3・比較対象2 [1, 2, 2, 3, 1, 3, 0, 4, 5, 7] 処理対象3・比較対象1 [1, 2, 2, 1, 3, 3, 0, 4, 5, 7] 処理対象3・比較対象3 [1, 2, 2, 1, 3, 3, 0, 4, 5, 7] 処理対象3・比較対象0 [1, 2, 2, 1, 3, 0, 3, 4, 5, 7] 処理対象3・比較対象4 [1, 2, 2, 1, 3, 0, 3, 4, 5, 7] 4回目処理終了 5回目処理 処理対象1・比較対象2 [1, 2, 2, 1, 3, 0, 3, 4, 5, 7] 処理対象2・比較対象2 [1, 2, 2, 1, 3, 0, 3, 4, 5, 7] 処理対象2・比較対象1 [1, 2, 1, 2, 3, 0, 3, 4, 5, 7] 処理対象2・比較対象3 [1, 2, 1, 2, 3, 0, 3, 4, 5, 7] 処理対象3・比較対象0 [1, 2, 1, 2, 0, 3, 3, 4, 5, 7] 処理対象3・比較対象3 [1, 2, 1, 2, 0, 3, 3, 4, 5, 7] 5回目処理終了 6回目処理 処理対象1・比較対象2 [1, 2, 1, 2, 0, 3, 3, 4, 5, 7] 処理対象2・比較対象1 [1, 1, 2, 2, 0, 3, 3, 4, 5, 7] 処理対象2・比較対象2 [1, 1, 2, 2, 0, 3, 3, 4, 5, 7] 処理対象2・比較対象0 [1, 1, 2, 0, 2, 3, 3, 4, 5, 7] 処理対象2・比較対象3 [1, 1, 2, 0, 2, 3, 3, 4, 5, 7] 6回目処理終了 7回目処理 処理対象1・比較対象1 [1, 1, 2, 0, 2, 3, 3, 4, 5, 7] 処理対象1・比較対象2 [1, 1, 2, 0, 2, 3, 3, 4, 5, 7] 処理対象2・比較対象0 [1, 1, 0, 2, 2, 3, 3, 4, 5, 7] 処理対象2・比較対象2 [1, 1, 0, 2, 2, 3, 3, 4, 5, 7] 7回目処理終了 8回目処理 処理対象1・比較対象1 [1, 1, 0, 2, 2, 3, 3, 4, 5, 7] 処理対象1・比較対象0 [1, 0, 1, 2, 2, 3, 3, 4, 5, 7] 処理対象1・比較対象2 [1, 0, 1, 2, 2, 3, 3, 4, 5, 7] 8回目処理終了 9回目処理 処理対象1・比較対象0 [0, 1, 1, 2, 2, 3, 3, 4, 5, 7] 処理対象1・比較対象1 [0, 1, 1, 2, 2, 3, 3, 4, 5, 7] 9回目処理終了 処理後 [0, 1, 1, 2, 2, 3, 3, 4, 5, 7]
