0 
function binarySearch(value)
{
    var startIndex = 0,
        stopIndex = words.length - 1,
        middle = Math.floor((stopIndex + startIndex) / 2);

    while (words[middle] != value && startIndex < stopIndex) {
        // adjust search area
        if (value < words[middle]) {
            stopIndex = middle - 1;
        } else if (value > words[middle]) {
            startIndex = middle + 1;
        }

        // recalculate middle
        middle = Math.floor((stopIndex + startIndex) / 2);
    }
}

私は配列の形式で単語​​の大きなリストを作成しています：

例えば["a","ab","abc","b"]

アルファベット順。私が抱えている問題は、バイナリ検索アルゴリズムを変更して、単語を正しい場所に追加してから更新することです。

順序付けられた配列に単語を追加するためのパフォーマンス面での最良の方法は何ですか？そして、なぜそれが最善の方法なのですか？

4

2 に答える 2

5

効率的なバイナリ検索の挿入のために、文字列が見つからない場合に文字列が配列のどこに属するかを示すものをバイナリ検索で返すようにする必要があります。

他の言語でこれを行うために受け入れられている方法は、文字列が属するインデックスのビット単位の補数を返すことです。0のビット単位の補数は-1、1のビット単位の補数は-2、2は-3などです。JavaScriptで数値のビット単位の補数を取得するには、~演算子を使用します。

コード例：

/* 
    target: the object to search for in the array
    comparator: (optional) a method for comparing the target object type
    return value: index of a matching item in the array if one exists, otherwise the bitwise complement of the index where the item belongs
*/
Array.prototype.binarySearch = function (target, comparator) {
    var l = 0,
        h = this.length - 1,
        m, comparison;
    comparator = comparator || function (a, b) {
        return (a < b ? -1 : (a > b ? 1 : 0)); /* default comparison method if one was not provided */
    };
    while (l <= h) {
        m = (l + h) >>> 1; /* equivalent to Math.floor((l + h) / 2) but faster */
        comparison = comparator(this[m], target);
        if (comparison < 0) {
            l = m + 1;
        } else if (comparison > 0) {
            h = m - 1;
        } else {
            return m;
        }
    }
    return~l;
};

次に、binarySearchメソッドを使用して、独自のbinaryInsert関数を記述できます。

/*
    target: the object to insert into the array
    duplicate: (optional) whether to insert the object into the array even if a matching object already exists in the array (false by default)
    comparator: (optional) a method for comparing the target object type
    return value: the index where the object was inserted into the array, or the index of a matching object in the array if a match was found and the duplicate parameter was false 
*/
Array.prototype.binaryInsert = function (target, duplicate, comparator) {
    var i = this.binarySearch(target, comparator);
    if (i >= 0) { /* if the binarySearch return value was zero or positive, a matching object was found */
        if (!duplicate) {
            return i;
        }
    } else { /* if the return value was negative, the bitwise complement of the return value is the correct index for this object */
        i = ~i;
    }
    this.splice(i, 0, target);
    return i;
};

これらのメソッドが配列オブジェクトにプロトタイプ化されると、次のように直接使用できます。

var arr = [];
arr.binaryInsert("Zebra");
arr.binaryInsert("Aardvark");
arr.binaryInsert("Mongoose");
alert(arr);
/* [ "Aardvark", "Mongoose", "Zebra" ] */

アイテムの数が増えると、これは電話をかけるよりも大幅に速くなりますArray.sort()

アレイプロパティキーの汚染

上記のコードのようにArrayオブジェクトにメソッドをプロトタイピングすると、メソッドが配列の列挙可能なプロパティとして表示され、for(var i in arr)ループ内のすべてのプロパティを列挙しているロジックに干渉する可能性があることに注意してください。の形式で記述されたループは、for(var i=0; i<arr.length; i++)引き続き設計どおりに機能します。

Internet Explorer 8以下をサポートする必要がない場合は、Array.prototype直接呼び出すことを避け、代わりObject.definePropertyに以下の例のように使用できます。

Object.defineProperty(Array.prototype, "binarySearch", {
value: function (target, comparator) {
    var l = 0,
        h = this.length - 1,
        m, comparison;
    comparator = comparator || function (a, b) {
        return (a < b ? -1 : (a > b ? 1 : 0));
    };
    while (l <= h) {
        m = (l + h) >>> 1;
        comparison = comparator(this[m], target);
        if (comparison < 0) {
            l = m + 1;
        } else if (comparison > 0) {
            h = m - 1;
        } else {
            return m;
        }
    }
    return~l;
}
});

Object.defineProperty(Array.prototype, "binaryInsert", {
value: function (target, duplicate, comparator) {
    var i = this.binarySearch(target, comparator);
    if (i >= 0) {
        if (!duplicate) {
            return i;
        }
    } else {
        i = ~i;
    }
    this.splice(i, 0, target);
    return i;
}
});

このアプローチにより、列挙可能なキーの汚染が回避されるため、for(var i in arr)ループは引き続き期待どおりに機能します。

于 2015-02-26T23:56:49.423 に答える
1

配列の場合、このような操作は線形アルゴリズムの複雑さを持つ可能性が高いため、代わりにツリーを使用するのが最善の方法です。

配列を使い続けたい場合は、挿入にスプライスメソッドを使用することをお勧めします。

于 2012-09-11T12:43:07.687 に答える