2021-02-01

【アルゴリズム(JS実装)】Exponential Search

どうも、わくばです！

　今日はExponential Searchです。Exponentialといのは指数関数的という意味です。理系学生は$e^x$や$exp(x)$でおなじみですよね。

　このアルゴリズムは名前の通りで、指数関数的なインターバルを用いて飛び飛びに探索していくアルゴリズムです。Jump Searchと発想は近いと思いますが、Exponential Searchdでは最終的にBinary Searchを用いるので速いです。

　以前記事にしたBinary Searchを添付しておきますので参考にしてみてください。

pyecracker99.hatenablog.com

　以下がコードです。

//まずbinarySearchを定義
const binarySearch = (array, low, high, value) => {

    while (low <= high) {
        const mid = Math.floor((low + high) / 2);
        if (array[mid] === value) {
            return mid;
        } else if (array[mid] < value) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return -1;
}


const exponentialSearch = (array, value) => {
    const { length } = array;

    if (array[0] == value) {
        return 0;
    }

    //valueを超えるタイミングを2の塁乗で探していく
    //1,2,4,8,16,32と増加していく
    let i = 1;
    while (i < length && array[i] < value) {
        i *= 2;
    }

    /**
    iは最初にvalueを通り過ぎた地点なので,
    iはvlaueがある区画の終端で、i\2は始端を表す。
    したがって、binarySearchのlowはi/2を入れる。
    iにしていまうとvalueを通り過ぎたところから右へ
    探索することになるので一生見つからない。
    **/
    return binarySearch(array, i/2, Math.min(i, length-1), value)
}

const array = [12,14,5,1,2,3,4,6,8,0,144,166];

console.log(exponentialSearch(array, 167));
console.log(exponentialSearch(array, 144));
>>>-1
>>>10

　$i = 2^j$である区画$2^{j-1}\sim$2^jの間)にvalueが存在した場合、$j$が処理回数ですから

$$ i = 2^j $$

$$ log(i) = log2^j $$

$$ j = log(i)$$

よってBinary Searchの前までが正確に$O(logi)$かかったと言えます。

　Binary Searchは$2^{j-1}\sim2^j$の間で実行され、これは$$2^{logi}-2^{logi-1} =2^{logi}(2-1)=2^{logi-1} $$よりサイズ$2^{logi-1} $の配列において実行されることになる。

　Binary Searchはサイズｎの配列において$O(logn)$かかるので、$O(log(2^{logi-1})) \approx O(logi)$

　全体で$O(logi)+O(logi)=O(logi)$になります。

　今日は以上です。

　では。

2021-01-31

【アルゴリズム(JS実装) 】Interpolation Search

アルゴリズム

　どうも、わくばです！

　今日はInterpolation Searchです。このアルゴリズムはBinary Searchの改造版で基本的な考え方は同じです。したがってソート済みの配列に適用する点は同じです。では何が違うのかというと、Binaryでは真ん中で半分にしていましたが、Interpolationでは分割点をもっと正確に計算しているという点です。確かに、何も考えずに真ん中で分けるのはあまりスマートではないですよね。せっかくソート済みなんだからもう少し絞れるだろ、というわけです。「あいさつ」という言葉を国語辞典で調べる場合、真ん中を開くことはしませんよね。あ行のように明らかに近いところを開くはずです。これと同じ発想です。

　ではその分割点はどう決めるのかというと以下の式で決めます。

$position(x) = low + \dfrac{x-array[low]}{array[high]-array[low]}(high-low) $

　ちょっとわかりにくいかもしれませんが言ってることは単純で、$\dfrac{x-array[low]}{array[high]-array[low]}$の部分で$x$を0〜1の縮尺に圧縮して、$(high-low)$をかけてインデックスに変換しています。

以下がコードです。

const interpolationSearch = (array, value) => {
    const { length } = array;
    let low = 0;
    let high = length - 1;
    let position;
    let delta;
    while (
        low <= high &&
        value >= array[low] &&
        value <= array[high]
    ) {
        //valueを圧縮
        delta = (value - array[low]) / (array[high] - array[low]); 
        //positionを計算
        position = low + Math.floor((high - low) * delta); 
        //ぴったり賞ならそれを返す
        if (array[position] == value) { 
            return position;
        }
        //positionが目的のvalueの位置より左にあれば右に詰める
        if (array[position] < value) { 
            low = position + 1;
        } else {
        //positionが目的のvalueの位置より右にあれば左に詰める
            high = position - 1;
        }
    }
    return -1;
}

const array = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19];
interpolationSearch(array, 16)

　時間計算量は平均で$O(log(logn))$になるようです。理由についてですが、かなり調べましたが正直シャープな説明はありませんでした。唯一以下の論文を見つけたのですが、ちょっと難しくて完全には負いきれませんでした(笑)

https://www.cadmo.ethz.ch/education/lectures/HS18/SAADS/reports/17.pdf

　ただ論文に目を通した感じ、$n=z^{2^k}$として仮定して上から抑える形で算出していたので、$O(log(logn))$のうち片方はBinary処理によるもんですが、もう一方は仮定によって生まれているものだと思います。

　Binary Searchよりも処理が少ないってことがわかれば良いのかな、、、すんません(汗)

　今日は以上です。では。

2021-01-30

【アルゴリズム(JS実装)】Jump Search

アルゴリズム

　どうも、わくばです！

　今日は Jump Searchです。こちらもソート済みの配列を検索するアルゴリズムです。単純に言うとLinear Searchを端折った感じです。まず決まったintervalで飛び飛びに進んで探索をします。どのintervalにあるかわかったらその中でLinear Searchをして終わりです。

コードは以下のようになりました。

const jumpSearch = (array, value) =>     {

    let { length } = array

    let interval = Math.floor(Math.sqrt(length));

    //これらは区画の両端。上限と下限
    let blockFloor = 0, blockCeil= interval;

    //区画の両端の更新しながら、value以上の上限を持つ区画を探す
    while (array[Math.min(blockCeil, length) - 1] < value)
    {
        //以下2行は区画の更新
        //前回の上限を、今回の下限にする 
        blockFloor = blockCeil;
        //前回の上限にintervalを足して今回の上限にする
        blockCeil += interval;
        
        //最後までなかったらそもそもなかった    
        if (blockFloor >= length)
            return -1;
    }

    //LinearSearch
    /**
     以前僕の記事で紹介した方法は複数マッチを拾うため配列を作って返したが
     今回は一個で良いので、whileで一個見つかるまでループしている
     **/ 
    while (array[blockFloor] < value)
    {
        blockFloor++;

        if (blockFloor == Math.min(blockCeil, length))
            return -1;
    }

    return array[blockFloor] == value ? blockFloor : -1;
}

let array = [1,2,4,6,8,9,90];
console.log(jumpSearch(array,6))
>>>3

　時間計算量は$O(\sqrt{n})$です。飛び飛びLinear Searchなので単にルートを取るだけです。Counting Sortのような、配列サイズに依存するメモリの使い方はせず、有限で住むので空間計算量は$O(1)$です。

　最近Whileの使い方がなれてきて、すごい便利だなと感じるようになりました。forとifの組み合わせ+必要最低限のループっていう使い方ができるので無駄がありません。

　今日は以上です。

　では。

2021-01-29

【アルゴリズム(JS実装)】Binary Search

アルゴリズム

　どうも、わくばです！

　今日はBinary Searchです。ソートが前提の処理ですが、前回のLinear searchより速いと思います。

　仕組みはこんな感じ

基準値を決める
基準値と探している値を比べる
基準値より大きければその基準値より上に的を絞る
基準値より小さければその基準値より下に的を絞る
一個になったらそれが答え

半分ちょを繰り返して探していくってことですね。

const binarySearch = (array, value) => {

    //まずソート。以前の記事を参照
    const sortedArray = quickSort(array);

    //上限と下限を定義する
    //ここからこの2つの範囲を狭めていきvalueを探す
    let low = 0;
    let high = sortedArray.length - 1;

    //lowとhighが重なるまで実行
    while (low <= high) {
        const mid = Math.floor((low + high) / 2);
        //基準ともし同じならそいつを返す
        if (sortedArray[mid] === value) {
            return mid;
        } else if (sortedArray[mid] < value) {
            //基準より大きければ、その基準より下はいらないのでlowを上げる
            low = mid + 1;
        } else {
            //小さければ上がいらないのでhighを下げる
            high = mid - 1;
        }
    }
    return -1;
}

const array = [12,14,5,1,2,3,4,6,8,0,144,166];

console.log(binarySearch(array, 144))

>>>10

　Big O notationについて、今までComplexityと言ったりオーダーと言ったりしていましたが、時間計算量という表現に統一します。時間計算量と空間計算量があるようで、C言語などメモリの扱いを自分で行わなければいけない場合は空間計算量も議論しながらやるようですね。

　今回の時間計算量は、予めソートしてあるとして、純粋にサーチの部分だけ考えると$O(logn)$になります。バイナリーで処理が進むイメージがつかめない人はこの動画が非常にわかりやすく説明してくれているので是非参考にしてください。おすすめです。

youtu.be

　以上です。疑問点や誤植などありましたら気軽にお願いします。

　では。

2021-01-27

【アルゴリズム(JS実装)】Linear Search

アルゴリズム

どうも、わくばです！

　Sortに関してはある程度有名なものをやり終えたので、Searchに入ろうと思います。

　今日はLinear Searchです。一番簡単なサーチだと思います。

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

function linearSearch(array, value){
    let results = []
    for(let i = 0; i < array.length; i++){
        if(arr[i] === value){
            results.push(i)
        }
    }
    return results ? results : -1
}

console.log(linearSearch([13,6,7,9,6,8,9,4,1,3], 9))
>>>[ 3, 6 ]

　9を探すテストを実行しています。9があるキーは3と6のようですね。あっています。

　オーダーは最もシンプルな$O(n)$ です。サーチの中でも効率の悪い方という記述がありましたが、他のもやってみないとイマイチピンときません。ソートで

勉強した経験からだと、二分するタイプなら$O(logn)$でいけそうなのでそれよりは確かに遅いかもしれませんね。

　ちなみにjavascriptのArrayオブジェクトに実装されているfilter() メソッドのソースコードを確認したら、どうやらあLinear Sortのアルゴリズムを用いているようでした。ただし返すのはキーではなくでそのままvalueという違いはありました。

　自分が普段使っているメソッドも、勉強したアルゴリズムで実装されているのを見るとかなり楽しいですね。

　では。

2021-01-26

【アルゴリズム(JS実装)】Radix Sort

アルゴリズム

　どうも、わくばです！

　今日はRadix Sortです。Bucket Sortに似てますね。Radixというのは基数とか根とか底とかいくつか訳がありますが、この例ではn進法のnのことです。

　 Radix Sortを簡単に説明すると、例えば10進法で考えるなら

０−９の計10個のバケットを準備する
配列を全部スキャンし、各要素の1桁目の値について０−９に分類してバケットに入れる(345という要素ならバケット5に入れる)
2を桁を上げて繰り返す。

といった感じです。比較ベースではないタイプのソートです。

コードはこんな感じになりました。

radixBaseはn進法のnのことです

const radixSort = (array, radixBase = 10) => {
    if (array.length < 2) {
        return array;
    }
    //有効数字がなくなるまで実行されるのでその範囲を知る必要がある
    const minVal = Math.min(...array);
    const maxVal = Math.max(...array);

    //以前僕が記事にしたcoutingSortとは少し違うので注意
    //Radixごとにソートするための関数
    const ctsForRadix = 
    (array, radixBase, significantDigit, minVal) => {
        //何個目のバケットか 
        let bcktIdx;

        //coutingSortのcounsに相当
        //要は出現回数をカウントする
        const counts = [];
        const mirror= [];

        //十進法であればradixBaseは10
        //10個のバケットを作る
        for (let i = 0; i < radixBase; i++) { 
            counts[i] = 0;
        }

        //各値がどのバケットに当たるかを計算しカウントする
        for (let i = 0; i < array.length; i++) { 
            bcktIdx = Math.floor((
                (array[i] - minVal) / significantDigit
                ) % radixBase); 
            counts[bcktIdx]++; 
        }

        /**
        ここからが僕の記事のcountingSortと少し違う
        以下の処理は各バケットの第一項が、
        出力する配列の何項目に当たるかを計算している
        **/
        for (let i = 1; i < radixBase; i++) { 
            counts[i] += counts[i - 1];
        }

        //カウント情報からソートを実行
        for (let i = array.length - 1; i >= 0; i--) { 
            bcktIdx = Math.floor((
                (array[i] - minVal) / significantDigit
                ) % radixBase ); 
            mirror[--counts[bcktIdx]] = array[i]; 
        }
        for (let i = 0; i < array.length; i++) { 
            array[i] = mirror[i];
        }
        return array;
    }


    //まずは１桁目でソート
    let significantDigit = 1; 
    while ((maxVal - minVal) / significantDigit >= 1) { 
        array = ctsForRadix(array, radixBase, significantDigit, minVal); 
        //桁を上げる
        significantDigit *= radixBase; 
    }
    return array;
}
console.log(radixSort([1,5888,25,438,0,9,6,5,44,7,8,44])

>>>[
      0,    1,  5,  6,  7,
      8,    9, 25, 44, 44,
    438, 5888
    ]

　オーダーとしては、サイズnの配列をk進数でソートすると、単純にk回分配するので$O(nk)$と考えられます。

　今日は以上です。

　誤っている点や質問などありましたらぜひコメントください。

　では。

2021-01-24

【アルゴリズム(JS実装)】Bucket Sort

アルゴリズム

　どうも、わくばです！

　今日はBucket Sortを勉強しました。バケツを用いた分割統治アルゴリズムで、Counting Sort の一般化と考えられます。実際、バケツサイズを１とすると同じ値のものだけが同じバケツに集約されていくので、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 $O(n)$ time. If division and multiplication can be done in constant time, then scattering each element to its bucket also costs $O(n)$ . Assume insertion sort is used to sort each bucket, then the third step costs $O(\textstyle \sum _{i=1}^{k}\displaystyle n_{i}^{2})$ , where $n_{i}$ is the length of the bucket indexed $i$ . Since we are concerning the average time, the expectation $E(n_{i}^{2})$ has to be evaluated instead. Let $X_{ij}$ be the random variable that is $1$ if element $j$ is placed in bucket $i$ , and $0$ otherwise. We have $n_{i}=\sum _{j=1}^{n}X_{ij}$ . Therefore,

${\begin{aligned}E(n_{i}^{2})&=E\left(\sum _{j=1}^{n}X_{ij}\sum _{k=1}^{n}X_{ik}\right)\\&=E\left(\sum _{j=1}^{n}\sum _{k=1}^{n}X_{ij}X_{ik}\right)\\&=E\left(\sum _{j=1}^{n}X_{ij}^{2}\right)+E\left(\sum _{1\leq j,k\leq n}\sum _{j\neq k}X_{ij}X_{ik}\right)\end{aligned}}$

The last line separates the summation into the case $j=k$ and the case $j\neq k$ . Since the chance of an object distributed to bucket $i$ is $1/k$ , $X_{ij}$ is 1 with probability $1/k$ and 0 otherwise.

$E(X_{ij}^{2})=1^{2}\cdot \left({\frac {1}{k}}\right)+0^{2}\cdot \left(1-{\frac {1}{k}}\right)={\frac {1}{k}}$

$E(X_{ij}X_{ik})=1\cdot \left({\frac {1}{k}}\right)\left({\frac {1}{k}}\right)={\frac {1}{k^{2}}}$

With the summation, it would be

$E\left(\sum _{j=1}^{n}X_{ij}^{2}\right)+E\left(\sum _{1\leq j,k\leq n}\sum _{j\neq k}X_{ij}X_{ik}\right)=n\cdot {\frac {1}{k}}+n(n-1)\cdot {\frac {1}{k^{2}}}={\frac {n^{2}+nk-n}{k^{2}}}$

Finally, the complexity would be $O\left(\sum _{i=1}^{k}E(n_{i}^{2})\right)=O\left(\sum _{i=1}^{k}{\frac {n^{2}+nk-n}{k^{2}}}\right)=O\left({\frac {n^{2}}{k}}+n\right)$ .

The last step of bucket sort, which is concatenating all the sorted objects in each buckets, requires $O(k)$ time. Therefore, the total complexity is $O\left(n+{\frac {n^{2}}{k}}+k\right)$ . Note that if k is chosen to be $k=\Theta (n)$ , then bucket sort runs in $O(n)$ average time, given a uniformly distributed input.^[1]