【アルゴリズム(JS実装)】Counting Sort
どうも、わくばです！
先日。E資格に申し込んだと言ったのですが、試験会場が都心しか空いていないことと、その他大学の実習の都合などいろいろ加味した結果、キャンセルして見送ることにしました。
JDLA認定は二年間有効なので、また機を見て受験しようと思います。
一応報告でした。
さて今日勉強したのは、Counting Sortです。まず出現回数をカウントし、その情報を回数と値がペアになるように別の配列に保持しておきます。今回は出現回数をvalue、何の値かをindexとして配列を作成しています。値をindexとすることで自然にソートされます。
以下がコードです。
const countingSort = array => { if (array.length < 2) { return array; } //数え上げるための配列 const counts = [];
/** まず配列の最大値の数だけメモリを確保する ここからはcounts配列のインデックスが出力時の valueに相当する **/ for(let i=0; i<=Math.max(...array); i++){ counts.push(0); } /** 出現した回数をカウント 6が二回出現したとするとcounts配列の 6番目に2が入る **/ array.forEach(x => { counts[x]++; }); /** accumulationをresnlt, currentをcount, indexをidxとしている。 countがなくなるでpushする。 例えばcounts配列の6番目に2が入っていたら 6を2回pushする **/ return resultArray = counts.reduce((result, count, idx) => { while (count > 0) { result.push(idx); count--; } return result; },[]); } let array = [22,3,5,4,27,8,9,5,4,33,7,8,9,4,2,22] console.log(countingSort(array);
>>>[
2, 3, 4, 4, 4, 5,
5, 7, 8, 8, 9, 9,
22, 22, 27, 33
]
今回はreduceを使ってみました。ちょっとスッキリするかと思います。
Complexity
入ってきた配列の長さをn、配列の中の最大値をkとすると、まずcounts配列が完成しきるまでで\(O(n+k)\)になります。
そのあとcountsにreduceをかけるので\(O(k)\)、中のwhileはnの長さの配列を作るためreduceの一回一回を跨いで合計すると\(O(n)\)必要になります。単純に合わせて\(O(nk)\)と考えてしまいたくなりますが、このときのnとkは依存せず、かつk回の処理のうち何もしない時もあるので、nとkは掛け算ではなく足し算で考えるほうが正確です。全部見に行く処理でk回かかり、countのvalueに応じてwhileが実行されます。つまり、結果としてreduceの部分は\(O(n+k)\)と捉えられます。
以上から\(O(2(n+k))\)で、係数を無視して\(O(n+k)\)と言えます。
【アルゴリズム(JS実装)】Shell Sort
どうも、わくばです！
今日はShell Sortを学びました。これはInsertion Sort の応用なのでコードを見てイマイチピントこなかった方は以前書いたInsertion Sortをぜひ参考にしてみてください*1
Shell Sortは飛び飛びでグループを形成し、グループごとにInsertion Sortを繰り返していくソートです。由来に関しては諸説あり、飛び飛びの間隔が徐々に狭まっていく様子が、貝殻のすぼまっていく形状を想起させるという説と、シンプルに「ドナルド=シェル」という方が考案したからという説がありました。
コードはこんな感じです。
const shellSort = array => { //間隔を指定 let gap = Math.floor(array.length / 2); //間隔が1になるまで繰り返す while(gap>0) { //insertion sortを行う for (var i = gap; i < array.length; i++) { var temp = array[i]; let j = i; while (j >= gap && array[j - gap] > temp ) { array[j] = array[j - gap]; j -= gap } array[j] = temp } //間隔を狭める gap = Math.floor(gap / 2); } return array; } var array = [8,3,5,9,1,5,9,2,3,8,4,1,5,6,8,4,7,9,5,3,2,6,8,0,4] console.log(shellSort(array)
>>>[
0, 1, 1, 2, 2, 3, 3, 3,
4, 4, 4, 5, 5, 5, 5, 6,
6, 7, 8, 8, 8, 8, 9, 9,
9
]
学んできたことが活きている感じがあっていいですね！笑
Complexityは、ギャップが二分割されていくので\(O(logn)\)を考慮し、その中でInsertion Sortが実行されると考えて議論する必要があります。
Worst-caseでは分割統治でInsertion SortのWorst-caseが実行されるので\(O(n^2logn)\)です。\(logn\)は\(n^2\)と比較すると無限のスケールでは無視できるので\(0(n^2)\)と表記できます。
Best-caseでは分割統治でInsertion SortのBest-caseが実行されると考えるので\(O(n(logn)^2)\)と表現できます。\(O((logn)^2)\)は増加が緩やかになっていくという性質を表現するだけなら\(O(logn)\)としてしまって、全体で\(O(nlogn)\)と表記することができます。
Average-caseはギャップ内でいくつスワップが必要になるかに依存しますが、一般に\(O(nlogn)\)と言われます。
今日は以上です。ソート全部やってしまおうとか言いましたが、ソートが思った以上に多種あったので驚愕しています。
では。
Big O notation の計算原理について調べてみた
どうも、わくばです！
アルゴリズムをいくつか勉強しているうちにBig O notationに関してだいぶ適当だったと感じてのでちゃんと調べてみました。が、結局わりと適当でオッケーみたいですね笑
MITのサイトや各種プログラミング学習サイトから引用しながら地味&&ラフに説明させていただきます。
まず気になっていたのが、\(\Theta()\)とか\(\Omega()\)とかの記号です。\(O()\)しか見聞きしたことなかったので一旦調べてみました。
freeCodeCampの記事では以下のようにありました。
- Big O: “f(n) is O(g(n))” iff for some constants c and N₀, f(N) ≤ cg(N) for all N > N₀
- Omega: “f(n) is Ω(g(n))” iff for some constants c and N₀, f(N) ≥ cg(N) for all N > N₀
- Theta: “f(n) is Θ(g(n))” iff f(n) is O(g(n)) and f(n) is Ω(g(n))
- Little O: “f(n) is o(g(n))” iff f(n) is O(g(n)) and f(n) is not Θ(g(n))
ラフに解釈すると\(O(n)\)は上界、\(\Omega(n)\)は下界、\(\Theta(n)\)はジャスト、\(o(n)\)は\(O(n)\)よりもっと上に吹っ飛んでる感じですかね。なんとなくわかります笑
数式の表現もあったのでこちらも紹介します。
個人的にこっちの方がわかりやすいと感じました。特に\(o(n)\)や\(\Theta(n)\)とかはこちらのほうが明解ですよね。\(o(n)\)は0に収束させ、\(\Theta(n)\)は実数値に収束する(無限のスケールで等価)。
対して\(O(n)\)は発散さえしなければ良いというわけですから、結構雑です。結局極限の話なので雑でいいわけですが(数学屋に怒られそう)。
ただ、あんまり厳密な使い方をされることは少ないようで、\(O(n)\)という表現は多くの場合\(\Theta(n)\)を意味したいたりするようです。
僕の記事ではもう\(O(n)\)だけでいいかなと思っています。
計算の仕方
Big O notationなどは時間計算量と表現されることもありますが、定義からもわかる通り計算値と言うよりあくまで定性的な概念であって「カテゴリー」という解釈が適切です。したがって計算の仕方といっても型があり、コード1行1行の型を考えればBig O notationはわかるようになっています。
型は調べた限り6つくらいでした。一つ一つ説明していきます。
・Sequence of statement
Statementというのは要するにコード1行のことです。JavaScriptだとセミコロンやブロック単位ですかね。これらの合計が定数なら\(O(1)\)(constantと呼ぶ)に該当し、無限スケールではほぼ無視できます
・If - Then - Else
これらがあるとプログラムの分岐が生じるので、Worst-caseを考えるのであれば、分岐で生じるパスのうち、より長い方を採用することになります。
・Loop
ループの中に例えば5つStatementがあるとするとそれがn回ループするので5nの計算量になります。これは単に直線的に増加しているのであって、その点だけわかれば良いので定数係数の5は省いて\(O(n)\)と表現します。ちなみにアルゴリズムの数学的な議論ではwhileループはforループとして考えるそうです。
・Nested loops
Complexityに一番大きな影響を持つ構造です。パターンとしては内側のループが外側のループに依存しないタイプと、依存するタイプがあります。
2つのループが依存しない場合例えば外側がN回、内側がM回とすると合計\(O(N*M)\)の計算量になります。NやMはarrayの長さなどに依存することが多いので、これは無限のスケールで考えるとおおよそ\(O(n^2)\)にカテゴライズできます
2つのループが依存する場合は以前投稿したInsertion Sortがわかりやすいので添付します。
function selectionSort(array, size){ const { length } = array; for (let i=0; i< length; i++){ let minIdx = i; for(let j =i+1; j < length; j++){ if(array[i]>array[j]){ minIdx = j; } } [array[i], array[minIdx]] = [array[minIdx], array[i]]; } return array; }
forがネストされていますが、内側の j が外側の i に依存していることがわかるでしょうか。したがって内側のループが徐々に減っていくことになりますが、おおよそ\(O(\dfrac{n(n+1)}{2})\)と同じ計算量になるので結局\(O(n^2)\)と考えられます。
総じてネストされたるループは\(O(n^2)\)でオッケーです。
・Statements with function/ procedure call
これはあんまり気にしなくて良いと思います。サブルーチンがある場合、その呼び出し元のComplexityちゃんと考慮しましょうという意味ですね。
・Divide and conquer
これは分割統治アルゴリズムの際に登場します。分割を繰り返す場合、 分割が進むごとに、2の累乗単位で残りの分割回数が減っていくので結果的に\(O(logn)\)になります。
以上です。誤った解釈をしている点などありましたぜひコメントください！
今後は今日学んだことをもとにBig O notationを考えようと思います
では。
参考:
【アルゴリズム(JS実装)】Quick Sort
どうも、わくばです！
E資格の申し込みを完了しました。2万は高いなあww
もともとなんでE資格を受けようと思ったかというと、プログラミングの勉強を始めたとき背水の陣を敷くのが目的だったんですよね。挫折者多いですし。個人的に挫折する自信があったので笑
当時、医学と親和性高いものってことで人工知能やデータサイエンスの領域に的を絞っていたので、E資格がもってこいだったんです。
なんて消極的な受験動機なんだ(笑)
勉強過程でアプリ開発の方に興味がそれまして、いまやE資格は「早く終わらせたいタスク」みたいな位置づけになってしまいました。10万近く使ったので、貧乏大学生としてはなんとしても意味あるものとして終えたいわけです(笑)
無駄話はさておき今日のアルゴリズムはQuick Sortです。基本的にめっちゃ早いらしいです。
この動画がクイックソートの優秀さ見るのに非常に良いです:
とりあえずコードはこんな感じになりました。
const quickSort = array => { //一つの区画内でピボットを中心に大小を振り分ける関数 const partition = (array, left, right ) => { //今回はピボットを中央地で定める。基準は何でも良い。 const pivot = array[Math.floor((right + left) / 2)]; let i = left; let j = right; while (i <= j) { //左からスタートしてピボットより大きい値を探す while (array[i]< pivot) { i++; } //右からスタートしてピボットより小さい値を探す while (array[j]> pivot) { j--; } //iとjがすれ違っていなければスワップ。 if (i <= j) { [array[i],array[j]] = [array[j],array[i]]; i++; j--; } } /** ここで返しているのは次の分割をどこで区切るかという話。 i,jは交換不要になった地点で止まるので iだろうがjだろうがpivotとの大小関係は正しい 故に返すのはぶっちゃけjでも可。 **/ return i; } //partition関数を再帰的に繰り返す関数 const quick = (array, left, right ) => { let index; if (array.length > 1) { //次の分割の基点 index = partition(array, left, right); if (left < index - 1) { //左分割で再帰処理 quick(array, left, index - 1 ); } if (index < right) { //右分割でも再帰処理 quick(array, index, right ); } } return array; }; return quick(array, 0, array.length - 1 ); }; let array = [5,4,3,6,7,8,22,7,8,99,0,7,8,0,2,7,266,8,90,5,344,2,34,5,6778,7] console.log(quickSort(array)) >>>[ 0, 0, 2, 2, 3, 4, 5, 5, 5, 6, 7, 7, 7, 7, 7, 8, 8, 8, 8, 22, 34, 90, 99, 266, 344, 6778 ]
ピボットの決め方は何でも良いです。ある分割が要素一個になったら、もうその要素はそこでお終いなので、適当に決めても問題なく実行できるからですかね。
決め方の例としては以下のようなものがあります。
- ランダムに決める
- 左端、真ん中、右端をピックアップしそれらの中央値をピボットにする(全部の中央地にすると処理が増えるから)
- 左端か右端をピボットして用いる
今回は右の左の平均をとっています。
Big O notationに関してですが、分割の処理でlog、各分割でのpartition処理でおよそn必要なので\(O(nlogn)\)と考えられます。
Big O notationが思ったより深い概念で、ちょっと理論に追いつけなくなってきたので、機会を見てちゃんと勉強しようと思いました。
おすすめの記事とかあればぜひ教えて下さい(人∀・)
では。
【アルゴリズム(JS実装)】Merge Sort
どうも、わくばです！
今日はJDLA認定講座の最後の試験でした。無事合格しましたので、これでやっとE資格試験を受験できます。
なんでこんなにめんどくさいのだ（笑）
機械学習は統計的な処理もしっかり含まれていて、医学でも役立つので何れにせよ頑張りきろうと思います。
さて今日のアルゴリズムですが、Merge Sortです。いくつかアルゴリズムをコードに起こしてきましたが、アルゴリズムのぱっと見の印象では意外と複雑さの検討がつきにくいですね。
ソート系は難易度低い印象ですがBubble Sortや今回のMerge Sortなど、所見でコードを書こうとするとなかなかしんどいです（笑）
Merge Sortはこんな感じになりました。
const mergeSort = array => { const merge = (left, right ) => { //分割した左のインデックス let i = 0; //分割した右のインデックス let j = 0; const result = []; while (i < left.length && j < right.length) { //左と右で小さい方をresultに追加 if(left[i]< right[j]){ result.push(left[i]); i++; }else{ result.push(right[j]); j++; } } //残ったものをくっつける return result.concat(i < left.length ? left.slice(i) : right.slice(j)); } if (array.length > 1) { const { length } = array; const middle = Math.floor(length / 2); //分割後ひたすら再帰的に繰り返す const left = mergeSort(array.slice(0, middle )); const right = mergeSort(array.slice(middle, length)); //最後にくっつける array = merge(left, right ); } return array; } let arr = [5,4,3,7,6,5,1,8,7,6,9,33,5,7,89] console.log(mergeSort(arr)) >>>[ 1, 3, 4, 5, 5, 5, 6, 6, 7, 7, 7, 8, 9, 33, 89 ]
【アルゴリズム(JS実装)】Insertion Sort
どうも、わくばです！
今日はInsertion Sortです。自分より前の要素を比較していって、自分より小さいものが現れたらその後ろに挿入するというアルゴリズムです。
コードは以下のような感じです。
const insertionSort = array => { for (let i = 1; i < array.length; i++) { //jの位置から比較しながら前に戻っていく let j = i; let temp = array[i]; //tempより小さいものがでてくるまでループ while (j > 0 && array[j - 1]> temp) { //自分より大きければ比較対象を後ろにずらす array[j] = array[j - 1]; j--; } //insert位置が決まったらtempをそこまで移動する array[j] = temp; } return array; }; array = [4,5,6,3,2,7,12,1]; console.log(insertionSort(array))
結果
[1,2,3,4,5,6,7,12]
tempに最終的に移動させようとしている変数(array[i])を保持しておき、whileでtempより前の要素を比較していきます。比較対象がtempより大きいものである間は、その比較対象を後ろに一歩ずらし、小さいものが現れた時点でwhileを抜けてその位置にtempを代入するといった流れです。これをforによって各要素で実行していきます。
Big O notationは\(O(n^2)\)と考えられます。最初から昇順に並んでいれば、各要素のチェックだけで入れ替えはないので\(O(n)\)で済み、逆に降順であればおおよそ\(\dfrac{n(n+1)}{2}\)必要になるので\(O(n^2)\)になります。
もっとJSの良さを活かしたいなーと、非破壊的なmap()やreduce()などを使ってパターンも考えたりしていますが、一個前のスワップが前提となる処理が多いので非破壊的なメソッドだとそもそも違うアルゴリズムになってしまうんですよね。当たり前ですけど（笑）
今日は以上です。改善案や、おすすめの面白いアルゴリズムなどありましたら是非コメントください！
では。
【アルゴリズム(JS実装)】Selection Sort
どうも、わくばです！
今日はSelection Sort を学びました。今回はシンプルです。
アルゴリズムの説明はこのサイトが非常にわかりやすいのでぜひ：Selection Sort - InterviewBit
コードはこんな感じになりました。
function selectionSort(array, size){ const { length } = array; for (let i=0; i< length; i++){ let minIdx = i; for(let j =i+1; j < length; j++){ if(array[i]>array[j]){ minIdx = j; } } [array[i], array[minIdx]] = [array[minIdx], array[i]]; } return array; }
実行してみると
let data = [-2, 45, 0, 11, -9] selectionSort(data, data.length)
[-9, -2, 0, 11, 45]
機能しています。
Complexityはスワップし終えたものは比較対象から減っていくので
$$(n-1)+(n-2)+...+2+1=\dfrac{n(n-2)}{2}$$
これは概算すると\(O(n^2)\)になります。ループが二重なので直感的にも納得です。(Big O notationを知らない方のために一応コメントしておくと、Big O notationはあくまで複雑性の指標であって正確な計算値ではありません。処理の複雑さ的に\(O(n^2)\)とすると定性的に理解できて良いですね、というものです。)
今日は以上です。E資格の勉強引き続き頑張ります。あ、あと医学も！(笑)
では。
