『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]
『Pythonで体験してわかるアルゴリズムとデータ構造』メモその4/バケットソートの制約を知ろう
『Pythonで体験してわかるアルゴリズムとデータ構造』を読みながらアルゴリズムについて勉強する。
- 作者: 西澤弘毅,森田光
- 出版社/メーカー: 近代科学社
- 発売日: 2018/06/30
- メディア: 単行本
- この商品を含むブログを見る
第4章にちょろっと書いてあったバケットソートについて書いていく。
バケットソートについて
バケツ数 k 個使った場合、オーダーはO(n + k)となり、ソートする要素数nとk を無関係にできる場合線形時間ソートとなるが、要素間の全順序関係を用いるソートとは異なり、キーの取りうる値がk種類である、という入力により強い制限を要求するソートである。
バケットソート - Wikipedia
ここでいうバケットとはバケツのこと。ビンソートともいう
事前に用意したバケツに数字を置いていくというのが特徴。
用意したバケツの番号へ同じ番号のデータを順番に渡してあげるため、最良計算量はO(n)。
数字同士の比較が存在しないため、その分処理が速いため早いソートになるが、制約が多め。
事前にバケツを用意する、つまり最初に渡される数字分の要素を用意してあげる必要性があるため、その時点でまずメモリを使用する。
そのため要素数が多すぎるとメモリを使い切ってしまう可能性がある。
また、特徴上渡す値は整数である必要があり、数字の重複が許されない。
数字の重複を許すバケットソートが分布数え上げソート。
バケットソートのイメージは以下
実装
分布数え上げソートで実装。
def bucket_sort(lst): bucket = [None for _ in range(max(lst)+1)] print(bucket) # バケットにデータを格納していく # input側で重複した値を存在した時は加算する for i in lst: if bucket[i] == None: bucket[i] = i else: bucket[i] += i print(bucket) # 書き戻し作業 j = 0 for bucket_num, lst_num in enumerate(bucket): if lst_num == None: continue if lst_num == 0: lst[j] = lst_num j += 1 continue print("要素番号, データ", bucket_num, lst_num) for k in range(lst_num // bucket_num): # 要素番号よりも格納データのデータが大きい場合、重複したデータのためバケットの番号をセット if lst_num > bucket_num: lst_num = bucket_num lst[j] = lst_num print(lst) j += 1 lst = [1, 2, 3, 4, 5, 3, 2, 1, 7, 0] print("処理前", lst) print() bucket_sort(lst) print() print("処理後", lst)
処理前 [1, 2, 3, 4, 5, 3, 2, 1, 7, 0] [None, None, None, None, None, None, None, None] [0, 2, 4, 6, 4, 5, None, 7] 要素番号, データ 1 2 [0, 1, 3, 4, 5, 3, 2, 1, 7, 0] [0, 1, 1, 4, 5, 3, 2, 1, 7, 0] 要素番号, データ 2 4 [0, 1, 1, 2, 5, 3, 2, 1, 7, 0] [0, 1, 1, 2, 2, 3, 2, 1, 7, 0] 要素番号, データ 3 6 [0, 1, 1, 2, 2, 3, 2, 1, 7, 0] [0, 1, 1, 2, 2, 3, 3, 1, 7, 0] 要素番号, データ 4 4 [0, 1, 1, 2, 2, 3, 3, 4, 7, 0] 要素番号, データ 5 5 [0, 1, 1, 2, 2, 3, 3, 4, 5, 0] 要素番号, データ 7 7 [0, 1, 1, 2, 2, 3, 3, 4, 5, 7] 処理後 [0, 1, 1, 2, 2, 3, 3, 4, 5, 7]
参照
『Pythonで体験してわかるアルゴリズムとデータ構造』メモその3/挿入ソートのイメージをつかむ
『Pythonで体験してわかるアルゴリズムとデータ構造』を読みながらアルゴリズムについて勉強する。
- 作者: 西澤弘毅,森田光
- 出版社/メーカー: 近代科学社
- 発売日: 2018/06/30
- メディア: 単行本
- この商品を含むブログを見る
第4章 アルゴリズムを思い受ける方法
書籍中では挿入ソートをベースに説明されている。
この章のゴールは 自分でアルゴリズムを思いつくためにはどのようなものを参考にすればよいか
挿入ソートについて
整列してある配列に追加要素を適切な場所に挿入すること。平均計算時間・最悪計算時間がともにO(n2)と遅いが、アルゴリズムが単純で実装が容易なため、しばしば用いられる。安定な内部ソート。基本挿入法ともいう。
バブルソートと比較すると、「交換回数」は等しくなる。しかし、「比較回数」は、バブルソートでは必ずn(n-1) / 2回必要だったが、挿入ソートはこれ以下で済むため、挿入ソートの方が高速である。また、ほとんど整列済みのデータに対しては高速という特徴を持っている。
挿入ソート - Wikipedia
挿入ソートのイメージは以下
実装
def insertion_sort(array): n = len(array) for i in range(1, n): print("{}回目処理".format(str(i))) tmp = array[i] print("処理対象：", tmp) if tmp < array[i-1]: # 挿入する位置までずらしていく j = i while True: array[j] = array[j-1] print("{}を{}番目に移動：{}".format(array[j-1], j+1, array)) j -= 1 # 配列の先頭に到達するか、前の配列値が小さい場合、次の処理へ if j == 0 or tmp >= array[j-1]: break array[j] = tmp print("{}を{}番目に移動：{}".format(tmp, j+1, array)) print("確定：", array) print("") array = [1,2,3,4,5,3,2,1,3,0] print("処理前：", array) print("") insertion_sort(array) print("処理後 ", array)
処理前： [1, 2, 3, 4, 5, 3, 2, 1, 3, 0] 1回目処理 処理対象： 2 確定： [1, 2, 3, 4, 5, 3, 2, 1, 3, 0] 2回目処理 処理対象： 3 確定： [1, 2, 3, 4, 5, 3, 2, 1, 3, 0] 3回目処理 処理対象： 4 確定： [1, 2, 3, 4, 5, 3, 2, 1, 3, 0] 4回目処理 処理対象： 5 確定： [1, 2, 3, 4, 5, 3, 2, 1, 3, 0] 5回目処理 処理対象： 3 5を6番目に移動：[1, 2, 3, 4, 5, 5, 2, 1, 3, 0] 4を5番目に移動：[1, 2, 3, 4, 4, 5, 2, 1, 3, 0] 3を4番目に移動：[1, 2, 3, 3, 4, 5, 2, 1, 3, 0] 確定： [1, 2, 3, 3, 4, 5, 2, 1, 3, 0] 6回目処理 処理対象： 2 5を7番目に移動：[1, 2, 3, 3, 4, 5, 5, 1, 3, 0] 4を6番目に移動：[1, 2, 3, 3, 4, 4, 5, 1, 3, 0] 3を5番目に移動：[1, 2, 3, 3, 3, 4, 5, 1, 3, 0] 3を4番目に移動：[1, 2, 3, 3, 3, 4, 5, 1, 3, 0] 2を3番目に移動：[1, 2, 2, 3, 3, 4, 5, 1, 3, 0] 確定： [1, 2, 2, 3, 3, 4, 5, 1, 3, 0] 7回目処理 処理対象： 1 5を8番目に移動：[1, 2, 2, 3, 3, 4, 5, 5, 3, 0] 4を7番目に移動：[1, 2, 2, 3, 3, 4, 4, 5, 3, 0] 3を6番目に移動：[1, 2, 2, 3, 3, 3, 4, 5, 3, 0] 3を5番目に移動：[1, 2, 2, 3, 3, 3, 4, 5, 3, 0] 2を4番目に移動：[1, 2, 2, 2, 3, 3, 4, 5, 3, 0] 2を3番目に移動：[1, 2, 2, 2, 3, 3, 4, 5, 3, 0] 1を2番目に移動：[1, 1, 2, 2, 3, 3, 4, 5, 3, 0] 確定： [1, 1, 2, 2, 3, 3, 4, 5, 3, 0] 8回目処理 処理対象： 3 5を9番目に移動：[1, 1, 2, 2, 3, 3, 4, 5, 5, 0] 4を8番目に移動：[1, 1, 2, 2, 3, 3, 4, 4, 5, 0] 3を7番目に移動：[1, 1, 2, 2, 3, 3, 3, 4, 5, 0] 確定： [1, 1, 2, 2, 3, 3, 3, 4, 5, 0] 9回目処理 処理対象： 0 5を10番目に移動：[1, 1, 2, 2, 3, 3, 3, 4, 5, 5] 4を9番目に移動：[1, 1, 2, 2, 3, 3, 3, 4, 4, 5] 3を8番目に移動：[1, 1, 2, 2, 3, 3, 3, 3, 4, 5] 3を7番目に移動：[1, 1, 2, 2, 3, 3, 3, 3, 4, 5] 3を6番目に移動：[1, 1, 2, 2, 3, 3, 3, 3, 4, 5] 2を5番目に移動：[1, 1, 2, 2, 2, 3, 3, 3, 4, 5] 2を4番目に移動：[1, 1, 2, 2, 2, 3, 3, 3, 4, 5] 1を3番目に移動：[1, 1, 1, 2, 2, 3, 3, 3, 4, 5] 1を2番目に移動：[1, 1, 1, 2, 2, 3, 3, 3, 4, 5] 0を1番目に移動：[0, 1, 1, 2, 2, 3, 3, 3, 4, 5] 確定： [0, 1, 1, 2, 2, 3, 3, 3, 4, 5] 処理後 [0, 1, 1, 2, 2, 3, 3, 3, 4, 5]
『Pythonで体験してわかるアルゴリズムとデータ構造』メモその2/選択ソートで値の交換をイメージする
『Pythonで体験してわかるアルゴリズムとデータ構造』を読みながらアルゴリズムについて勉強する。
- 作者: 西澤弘毅,森田光
- 出版社/メーカー: 近代科学社
- 発売日: 2018/06/30
- メディア: 単行本
- この商品を含むブログを見る
※第2章はループの話だったので割愛。
第3章 アルゴリズムを比べる方法
書籍中では選択ソートをベースに説明されている。
この章のゴールは 入力の内容によって計算回数の大小が変化する場合の数値の比較について説明できるようになる
選択ソートについて
配列された要素から、最大値やまたは最小値を探索し配列最後の要素と入れ替えをおこなうこと。最悪計算時間がO(n2)と遅いが、アルゴリズムが単純で実装が容易なため、しばしば用いられる。内部ソート。後述するように、安定ソートではない。
「比較回数」は、n(n-1)/2回。「交換回数」は、各ループで最大1回なので、全体では多くともn-1回。バブルソートと比較すると、「比較回数」は同じだが「交換回数」が少ないので、選択ソートの方が高速である。
選択ソートのイメージは以下。
比較回数がなぜn(n-1)/2回なのか
何回比較したのかをn(n-1)/2で算出するのだが、なぜそうしているのか。
1からNまでの和を算出するときと同様に解いていく。
今回は配列数10なので、10マス×10マスを用意する。
選択ソートのイメージと同じように色付けしていく。
(黄色：処理対象値・橙色：処理対象と比較するデータ・青色：確定値)
そのうえでこの図を見たときに、橙色と青色が同じマス数であることが分かる（当たり前だけど）
なので、単純に「縦×横÷2」の三角形を求める公式で出せば、回答が導き出せる。
わけじゃない。
その場合 10×10÷2=50 となるのだが、マスを数えてみると45なので、結果が違う。
その5の差が黄色の考慮になる。
値が合わないのは、50の中には処理対象のデータが存在するため。
そいつらは交換元のデータなので、省いてやる必要がある。
上の図で見た通り、1行に黄色ハイライトされているマスはひとつ。
今回10マスなので、実際に考えなければいけないのは9マス。
そのため、n(n-1)/2で算出する。
交換回数がなぜn-1回なのか
上の図の通り、10処理目は交換する対象が存在しないので、交換をする必要なく確定するので、nではなく、n-1となる。
実装
def selection_sort(array): n = len(array) for i in range(0, n-1): print("{}回目処理".format(str(i+1))) min = i print("処理対象：", array[min]) print("比較対象：", array[min+1:]) for j in range(i+1, n): if array[min] > array[j]: min = j tmp = array[min] print("移動する値：", tmp) # 処理対象値を入れ替える配列要素に移動 array[min], array[i] = array[i], tmp print("{}を{}番目に移動：{}".format(array[i], min+1, array)) print("{}を{}番目に移動し確定：{}".format(tmp, i, array)) print("") array = [1,2,3,4,5,3,2,1,3,0] print("処理前：", array) print("") selection_sort(array) print("処理後 ", array)
処理前： [1, 2, 3, 4, 5, 3, 2, 1, 3, 0] 1回目処理 処理対象： 1 比較対象： [2, 3, 4, 5, 3, 2, 1, 3, 0] 移動する値： 0 0を10番目に移動：[0, 2, 3, 4, 5, 3, 2, 1, 3, 1] 0を0番目に移動し確定：[0, 2, 3, 4, 5, 3, 2, 1, 3, 1] 2回目処理 処理対象： 2 比較対象： [3, 4, 5, 3, 2, 1, 3, 1] 移動する値： 1 1を8番目に移動：[0, 1, 3, 4, 5, 3, 2, 2, 3, 1] 1を1番目に移動し確定：[0, 1, 3, 4, 5, 3, 2, 2, 3, 1] 3回目処理 処理対象： 3 比較対象： [4, 5, 3, 2, 2, 3, 1] 移動する値： 1 1を10番目に移動：[0, 1, 1, 4, 5, 3, 2, 2, 3, 3] 1を2番目に移動し確定：[0, 1, 1, 4, 5, 3, 2, 2, 3, 3] 4回目処理 処理対象： 4 比較対象： [5, 3, 2, 2, 3, 3] 移動する値： 2 2を7番目に移動：[0, 1, 1, 2, 5, 3, 4, 2, 3, 3] 2を3番目に移動し確定：[0, 1, 1, 2, 5, 3, 4, 2, 3, 3] 5回目処理 処理対象： 5 比較対象： [3, 4, 2, 3, 3] 移動する値： 2 2を8番目に移動：[0, 1, 1, 2, 2, 3, 4, 5, 3, 3] 2を4番目に移動し確定：[0, 1, 1, 2, 2, 3, 4, 5, 3, 3] 6回目処理 処理対象： 3 比較対象： [4, 5, 3, 3] 移動する値： 3 3を6番目に移動：[0, 1, 1, 2, 2, 3, 4, 5, 3, 3] 3を5番目に移動し確定：[0, 1, 1, 2, 2, 3, 4, 5, 3, 3] 7回目処理 処理対象： 4 比較対象： [5, 3, 3] 移動する値： 3 3を9番目に移動：[0, 1, 1, 2, 2, 3, 3, 5, 4, 3] 3を6番目に移動し確定：[0, 1, 1, 2, 2, 3, 3, 5, 4, 3] 8回目処理 処理対象： 5 比較対象： [4, 3] 移動する値： 3 3を10番目に移動：[0, 1, 1, 2, 2, 3, 3, 3, 4, 5] 3を7番目に移動し確定：[0, 1, 1, 2, 2, 3, 3, 3, 4, 5] 9回目処理 処理対象： 4 比較対象： [5] 移動する値： 4 4を9番目に移動：[0, 1, 1, 2, 2, 3, 3, 3, 4, 5] 4を8番目に移動し確定：[0, 1, 1, 2, 2, 3, 3, 3, 4, 5] 処理後 [0, 1, 1, 2, 2, 3, 3, 3, 4, 5]
