読者です 読者をやめる 読者になる 読者になる

Panda Noir

JavaScript の限界を究めるブログです。

lower_boundとupper_boundをJavaScriptで実装してみた・リベンジ

JavaScript アルゴリズム プログラミング・パソコン

http://www.cplusplus.com/reference/algorithm/lower_bound/

ここの仕様を満たすように実装していきます。

lower_bound()とupper_bound()をJavaScriptで実装してみたのリベンジ記事です。今回は前回のような雑なテスト通して終わりではなく、きちんと論証しつつ実装します。

仕様

要約するとこの辺を満たせばよさそうです。

  • [first, last)の範囲で探索
  • 範囲内で最初のval以上の値を指すイテレータを返す。ただし、JavaScriptでは表現不可なので添字を返すとする。
  • [first, last)の値がすべてval未満の時はlastを指すイテレータを返す。ただし、これはJavaScriptで表現不可なので配列の長さを返すとする。
  • compは今回パスで。てか「STLとほぼ同じコード書くとこうだよ!」と言って書いてあるコードにすら存在してないし

線形探索による実装

まずは線形探索でlower_boundを実装します。いきなり二分探索を応用したコード書くと(僕が)混乱するので、まずは線形探索します。val以上の値が出てきたらその値を返して終了です。

function lower_bound(arr, first, last, val) {
    for (var i = first; i < last; i++) {
        if (arr[i] < val) continue;
        return i;
    }
    return i;
}

完成しました。テストを通すまでもないですね。

二分探索を応用した実装する

とりあえず線形探索では実装できました。あとはこれを崩さないように気をつけつつ二分探索に落とし込みます。

再帰関数で実装するのでまず最小ケースを考えます。この場合の最小ケースは[first, first + 1)です。この時、firstが指す値がval以上ならば、範囲内の値すべてがval以上となるので仕様に従いfirst + 1を返します。firstが指す値がval未満の場合、仕様に従いfirstを返します。

さて、最小ケースができたので、あとは最小ケースに向かっていくように再帰関数を考えます。

firstとlastの中間値を利用して範囲を絞っていけばよさそうです。しかし、範囲は本当にどんどん小さくなっていくでしょうか?どこかで範囲が変わらなくなり無限ループにならないでしょうか?僕が書く二分探索はだいたい無限ループになり止まるので不安になります。

ちょっと寄り道: 無限ループにならない証明

このままでは(僕が)不安なので「midはかならずfirst以上last未満となる」ことを簡単にですが証明しましょう。last = first + d(d > 0)とします。mid = floor((first + last) / 2) = floor(first + d / 2)であるので、first <= mid < last です。以上で証明されました。

コード

どんどん範囲が条件を満たしつつ小さくなっていくことが保証されました。だから、再帰をしていけば必ず最小ケースとなります。

以上を踏まえてコードを書き上げます。

function lower_bound(arr, first, last, val) {
    var mid = Math.floor((first + last) / 2);
    if (last - first === 1 ) {
        if (arr[first] < val) return last;
        else return first;
    }
    if (arr[mid] < val) {
        return lower_bound(arr, mid, last, val);
    } else {
        return lower_bound(arr, first, mid, val);
    }
}

上の議論を満たしています。

再帰関数をループに書き直す

最後に再帰関数をループに落とし込めば完成です。二分探索なのでスタックオーバーフローすることもないので上で一応完成しています。しかし、パフォーマンス考えるとやはりループに展開したほうが得です。

function lower_bound(arr, first, last, val) {
    var mid;
    while (last - first > 1) {
        mid = Math.floor((first + last) / 2);
        if (arr[mid] < val) {
            first = mid;
        } else {
            last = mid;
        }
    }
    if (arr[first] < val) return last;
    else return first;
}

これで本当に完成です。

最適化を施す

最適化までほどこしたコードも一応貼っておきます。インデント削除以外はかなり圧縮してます。

function lower_bound(arr, first, last, val) {
    var mid;
    while (last - first > 1)
        if (arr[mid = 0 | (first + last) / 2] < val) first = mid;
        else last = mid;
    return arr[first] < val ? last : first;
}

Closure Compilerによるさらなる圧縮後

function lower_bound(d,a,b,e){for(var c;1<b-a;)d[c=0|(a+b)/2]<e?a=c:b=c;return d[a]<e?b:a};

きちんと動きますが、これは読めませんね。というか読みたくないですね。実際使うときはこれを貼り付けるのが一番簡単です。なんと91バイト! 関数名をlbとかにすればさらに削れます。

upper_boundを実装する

ここまで分かれば簡単にupper_boundも実装できます。

function upper_bound(arr, first, last, val) {
    var mid;
    while (last - first > 1) {
        mid = Math.floor((first + last) / 2);
        if (arr[mid] <= val) {
            first = mid;
        } else {
            last = mid;
        }
    }
    if (arr[first] <= val) return last;
    else return first;
}

圧縮後

function upper_bound(d,a,b,e){for(var c;1<b-a;)d[c=0|(a+b)/2]<=e?a=c:b=c;return d[a]<=e?b:a};

開始位置を関数の引数から指定できるので、lower_boundとupper_boundを使った配列内の任意の値の数え上げをより効率的にできます。

lo = lower_bound(arr, first, last, val);
up = upper_bound(arr, lo, last, val); // ここでfirstをloにしているところがポイント。upとなる値はloより後ろにあることは確定しているので。
console.log(up - lo); // 配列内にあるvalの個数が表示されます。

firstとlastを取らない場合よりも高速に動作します。まあ、O(log N)なのでほとんど変わりませんが。

終わりに

始めに線形探索で書き、それを崩さないように実装していきました。線形探索で混乱が生じることはまずないのでコードの正確性を保証できます。

つまり線形探索で書いたものと返り値が同じならば正常な返り値という証明になります。このように、テスト用関数を作ることで作業しやすくなることが多々あります。

巷でよく見る実装とはまた少し違った実装となりましたが、論証はしてるので大丈夫です。