医学生わくばの欲張り技術ブログ

〜E資格を取りに行く!〜

今日のアルゴリズム(JS実装)〜Bucket Sort〜

 どうも、わくばです!

 

 今日はBucket Sortを勉強しました。バケツを用いた分割統治アルゴリズムで、Counting Sort の一般化と考えられます。実際、バケツサイズを1とすると同じ値のものだけが同じバケツに集約されていくので、Couting Sortと同様の処理になります。

 バケツに分割して、それぞれのバケツでソートを実行し、統合するという典型的な仕組みです。

 

コードはこんな感じです。 

//bucketSize : バケット一個あたりの要素数
const bucketSort = (array, bucketSize = 5) => { 
    if (array.length < 2) {
        return array;
    }

    //以前記事にしたinsertionSort参照
    const insertionSort = array => {
        for (let i = 1; i < array.length; i++) { 
            let j = i; 
            let temp = array[i]; 
            while (j > 0 && array[j - 1]> temp)  { 
                array[j] = array[j - 1]; 
                j--;
            }
            array[j] = temp; 
        }
        return array;
    };

    //バケットを作成
    const createBuckets = (array, bucketSize) => {
        const minVal = Math.min(...array);
        const maxVal = Math.max(...array);
        //バケット数を計算
        const bucketCount = Math.floor(
            (maxVal - minVal) / bucketSize
            ) + 1; 
        const buckets = [];
        for (let i = 0; i < bucketCount; i++) { 
            buckets[i] = [];
        }
        for (let i = 0; i < array.length; i++) { 
            //ある要素を何個目のバケットに入れるか計算
            const bucketIndex = Math.floor(
                (array[i] - minVal) / bucketSize
                ); 
            buckets[bucketIndex].push(array[i]); 
        }
        return buckets;
    }

    const sortBuckets = buckets => {
        //バケット内をソート
        return buckets.reduce((acc,cur)=>{
            if (cur != null) {
                insertionSort(cur); 
                acc.push(...cur);
            }
            return acc;
        },[])
    }

    //createBucketsを実行
    const buckets = createBuckets(array, bucketSize); 
    //sortBucketsを実行
    return sortBuckets(buckets); 
}

const array = [1,3,6,78,9,65,4,3,2,5,7,7,5,5,3,9,3]
console.log(bucketSort(array));

>>>[
1, 2, 3, 3, 3, 3, 4,
5, 5, 5, 6, 7, 7, 9,
9, 65, 78

 Complexityは結構複雑で、いろいろ調べた結果Wikiが一番わかりやすかったので引用させていただきます。

 以下はAverage Complexityの部分の引用です。

Consider the case that the input is uniformly distributed. The first step, which is initialize the buckets and find the maximum key value in the array, can be done in  time. If division and multiplication can be done in constant time, then scattering each element to its bucket also costs . Assume insertion sort is used to sort each bucket, then the third step costs , where  is the length of the bucket indexed . Since we are concerning the average time, the expectation  has to be evaluated instead. Let  be the random variable that is  if element  is placed in bucket , and  otherwise. We have . Therefore,

The last line separates the summation into the case  and the case . Since the chance of an object distributed to bucket  is  is 1 with probability  and 0 otherwise.

With the summation, it would be

Finally, the complexity would be .

The last step of bucket sort, which is concatenating all the sorted objects in each buckets, requires  time. Therefore, the total complexity is . Note that if k is chosen to be , then bucket sort runs in  average time, given a uniformly distributed input.[1]

  はバケットのサイズのことで、はバケットサイズの二乗を平均しています。二乗なのはInsertion Sortを用いているためです。なのでは、k個のバケットのComplexityを合計したものです。

 最後の結合も計算に入れて最終的にはと算出されています。

 

 

 今日は以上です。

 

 では。

今日のアルゴリズム(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)\)よりもっと上に吹っ飛んでる感じですかね。なんとなくわかります笑

 

 数式の表現もあったのでこちらも紹介します。

f:id:PYEcracker99:20210120071306p:plain

・Complexityの数式による定義

 個人的にこっちの方がわかりやすいと感じました。特に\(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を考えようと思います

 

 では。 

 

参考:

What is Big O Notation Explained: Space and Time Complexity

Complexity and Big-O Notation


pages.cs.wisc.edu

今日のアルゴリズム(JS実装)〜Quick Sort〜

 どうも、わくばです!

 

 E資格の申し込みを完了しました。2万は高いなあww

 もともとなんでE資格を受けようと思ったかというと、プログラミングの勉強を始めたとき背水の陣を敷くのが目的だったんですよね。挫折者多いですし。個人的に挫折する自信があったので笑

 当時、医学と親和性高いものってことで人工知能やデータサイエンスの領域に的を絞っていたので、E資格がもってこいだったんです。

 

 なんて消極的な受験動機なんだ(笑)

 

 勉強過程でアプリ開発の方に興味がそれまして、いまやE資格は「早く終わらせたいタスク」みたいな位置づけになってしまいました。10万近く使ったので、貧乏大学生としてはなんとしても意味あるものとして終えたいわけです(笑)

 

 無駄話はさておき今日のアルゴリズムはQuick Sortです。基本的にめっちゃ早いらしいです。

この動画がクイックソートの優秀さ見るのに非常に良いです: 

www.youtube.com

 

とりあえずコードはこんな感じになりました。

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
    ]
  分割して2群間比較を繰り返していくようです。再帰的な処理で実装してみました。再帰は変化を追いにくくて頭がこんがらがるので苦手です。時間かかりました。
 
 複雑性は\(O(n logn)\)です。二分割のようなBinaryな処理なのでlogになり、各分割でループ処理を実行するのでnが掛けられるということでしょうか。
 
 今日は以上です。とりあえずソート系を全部やってしまおうと思います。
 
 では。

今日のアルゴリズム(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()などを使ってパターンも考えたりしていますが、一個前のスワップが前提となる処理が多いので非破壊的なメソッドだとそもそも違うアルゴリズムになってしまうんですよね。当たり前ですけど(笑)

 

 今日は以上です。改善案や、おすすめの面白いアルゴリズムなどありましたら是非コメントください!

 

 では。