Uniform Binary Search(一定二分探索)解説

Uniform binary search - Wikipediaというページを発見しました。二分探索の改良版とのことです。

改良点

二分探索では通常、上限と下限を更新しながら探索していきます。この更新には加算とビットシフト(2での割り算)を行います。

それに対し、Uniform Binary Search(以下UBS)ではテーブルを参照することで更新を行います。テーブルには次の更新で用いるべき差分が格納されています。

テーブルを参照するほうがビットシフトより早く、また通常、探索は同じ配列に対して行われることが多いためテーブルを一度作ってしまえば使いまわせるということが根拠のようです。

コード

ほぼwikiのコードと同じです

const unisearch = (arr, key, delta) => {
    let i = delta[0] - 1, d = 0;
    while (true) {
        if (key === arr[i]) return i;
        if (delta[d] === 0) return -1; // 上限と下限の差がない=探索終了
        d = 0 | d + 1;
        if (key < arr[i]) i = 0 | i - delta[d]; // 上限の更新にあたる
        else i = 0 | i + delta[d]; // 下限の更新にあたる
    }
}
const makeTable = arr => {
    const table = [];
    const N = arr.length;
    let d = 0, power = 1;
    do {
        table[d] = 0 | (N + power) / (power <<= 1);
    } while (table[d++] != 0);
    return table;
}
const arr = [1, 3, 5, 6, 7, 9, 14, 15, 17, 19];
const table = makeTable(arr);
unisearch(arr, 10, table);

解説

二分探索では探索範囲が1/2ずつになっていきます。makeTable()はこの探索範囲(=上限と下限の差分)を格納した配列を返します。差分更新のときに計算をせず、配列から参照することがUniform(一定)の由来だと思います。

備考

実際にNode v8.5.0にて二分探索との比較実験を行ったところ、通常の二分探索のほうが約5倍早いという結果が出ました。検証に使ったのは下のコードです。

const unisearch = (arr, key, delta) => {
    let i = delta[0] - 1, d = 0;
    while (true) {
        if (key === arr[i]) return i;
        if (delta[d] === 0) return -1; // 上限と下限の差がない=探索終了
        d = 0 | d + 1;
        if (key < arr[i]) i = 0 | i - delta[d]; // 上限の更新にあたる
        else i = 0 | i + delta[d]; // 下限の更新にあたる
    }
}
const makeTable = arr => {
    const table = [];
    const N = arr.length;
    let d = 0, power = 1;
    do {
        table[d] = 0 | (N + power) / (power <<= 1);
    } while (table[d++] != 0);
    return table;
}
const binarysearch = (arr, key) => {
    let start = 0, end = arr.length;
    while (start <= end) {
        const mid = start + (end - start >> 1);
        if (key === arr[mid]) return mid;
        if (key < arr[mid]) end = mid - 1;
        else start = mid + 1;
    }
    return -1;
}
const arr = [1, 3, 5, 6, 7, 9, 14, 15, 17, 19];
const table = makeTable(arr);
const f = () => {
    for (let i = 0; i < 20; i++) {
        unisearch(arr, i, table);
    }
}
const g = () => {
    for (let i = 0; i < 20; i++) {
        binarysearch(arr, i);
    }
}
const timer = f => {
    console.time();
    for (let i = 0; i < 50000; i++) f();
    console.timeEnd();
}
timer(f);
timer(g);

ArrayBufferを活用するなどして高速にしようと頑張ってみましたが、どうやっても勝てませんでした。最適化によって通常の二分探索のほうが早かったのかもしれません。