ウェブサイト検索

javascript - 整列された数値の配列に数値を効率的に挿入する方法は？

私はソートされたJavaScriptの配列を持っており、結果として配列がソートされたままになるように、もう1つのアイテムを配列に挿入したいです。もちろん、簡単なクイックソート風の挿入関数を実装することもできます。

var array = [1,2,3,4,5,6,7,8,9];
var element = 3.5;
function insert(element, array) {
  array.splice(locationOf(element, array) + 1, 0, element);
  return array;
}

function locationOf(element, array, start, end) {
  start = start || 0;
  end = end || array.length;
  var pivot = parseInt(start + (end - start) / 2, 10);
  if (end-start <= 1 || array[pivot] === element) return pivot;
  if (array[pivot] < element) {
    return locationOf(element, array, pivot, end);
  } else {
    return locationOf(element, array, start, pivot);
  }
}

console.log(insert(element, array));

[警告] このコードには配列の先頭に挿入しようとするとバグがあります。例：insert(2, [3, 7, 9]) は誤って [3, 2, 7, 9] を生成します。

しかし、Array.sort 関数の実装がこれを私の代わりに行う可能性があること、そしてネイティブで行われることに気付きました。

var array = [1,2,3,4,5,6,7,8,9];
var element = 3.5;
function insert(element, array) {
  array.push(element);
  array.sort(function(a, b) {
    return a - b;
  });
  return array;
}

console.log(insert(element, array));

第一の実装を第二の実装より選ぶ正当な理由はありますか？

編集: 一般的な場合については、O(log(n)) の挿入（最初の例で実装されたもの）は汎用のソートアルゴリズムよりも高速になりますが、特に JavaScript では必ずしもそうとは限りません。注意すべき点は次の通りです:

  • いくつかの挿入アルゴリズムの最良の場合は O(n) であり、これは O(log(n)) とは依然として大きく異なりますが、下記で言及されている O(n log(n)) ほど悪くはありません。どのソートアルゴリズムを使用するかによって結論が変わるでしょう（Javascript の Array.sort 実装を参照？）
  • JavaScriptのsortメソッドはネイティブ関数であるため、潜在的に大きな利点を実現できます――巨大な係数を伴うO(log(n))でも、適度なサイズのデータセットに対してはO(n)よりもはるかに悪くなる可能性があります。

回答 #1

シンプル（デモ）：

function sortedIndex(array, value) {
    var low = 0,
        high = array.length;

    while (low < high) {
        var mid = (low + high) >>> 1;
        if (array[mid] < value) low = mid + 1;
        else high = mid;
    }
    return low;
}

回答 #2

ちょうど一つのデータポイントとして、試しに、Chromeを使ってWindows 7上で、2つの方法を使って10万個の事前にソートされた数値の配列に1000個のランダムな要素を挿入してみました:

First Method:
~54 milliseconds
Second Method:
~57 seconds

つまり、少なくともこの設定では、ネイティブの方法ではそれを補うことはできません。これは、小さなデータセット、例えば1000の配列に100個の要素を挿入する場合でも当てはまります:

First Method:
1 milliseconds
Second Method:
34 milliseconds

回答 #3

非常に良く、注目すべき質問で、とても興味深い議論ですね！私も、数千のオブジェクトを持つ配列に単一の要素を追加した後で、Array.sort() 関数を使用していました。

複雑なオブジェクトを扱う必要があったため、Array.sort() のような比較関数が必要になり、私の目的のために locationOf 関数を拡張する必要がありました:

function locationOf(element, array, comparer, start, end) {
    if (array.length === 0)
        return -1;

    start = start || 0;
    end = end || array.length;
    var pivot = (start + end) >> 1;  // should be faster than dividing by 2

    var c = comparer(element, array[pivot]);
    if (end - start <= 1) return c == -1 ? pivot - 1 : pivot;

    switch (c) {
        case -1: return locationOf(element, array, comparer, start, pivot);
        case 0: return pivot;
        case 1: return locationOf(element, array, comparer, pivot, end);
    };
};

// sample for objects like {lastName: 'Miller', ...}
var patientCompare = function (a, b) {
    if (a.lastName < b.lastName) return -1;
    if (a.lastName > b.lastName) return 1;
    return 0;
};

回答 #4

あなたのコードにバグがあります。次のように読むべきです:

function locationOf(element, array, start, end) {
  start = start || 0;
  end = end || array.length;
  var pivot = parseInt(start + (end - start) / 2, 10);
  if (array[pivot] === element) return pivot;
  if (end - start <= 1)
    return array[pivot] > element ? pivot - 1 : pivot;
  if (array[pivot] < element) {
    return locationOf(element, array, pivot, end);
  } else {
    return locationOf(element, array, start, pivot);
  }
}

この修正がなければ、コードは配列の先頭に要素を挿入することができません。

回答 #5

これはすでに答えがある古い質問であり、他にもいくつかまともな答えがあるのはわかっています。O(log n)で正しい挿入インデックスを調べることでこの問題を解決できると提案する回答もありますが、確かに調べることはできますが、その時間で挿入することはできません。配列のスペースを作るために部分的にコピーする必要があるからです。

結論：もし本当にソートされた配列への O(log n) の挿入と削除が必要であれば、配列ではなく別のデータ構造が必要です。Bツリーを使用すべきです。大規模なデータセットでBツリーを使用することで得られるパフォーマンス向上は、ここで提供されるどの改善よりもはるかに大きいでしょう。

もし配列を使用しなければならない場合、挿入ソートに基づいた次のコードを提案します。これは、配列がすでにソートされている場合に限り動作します。これは、挿入ごとに再ソートする必要がある場合に便利です:

function addAndSort(arr, val) {
    arr.push(val);
    for (i = arr.length - 1; i > 0 && arr[i] < arr[i-1]; i--) {
        var tmp = arr[i];
        arr[i] = arr[i-1];
        arr[i-1] = tmp;
    }
    return arr;
}

それは O(n) で動作するべきで、これが最善だと思います。JavaScript が複数の代入をサポートしてくれればもっと良いのですが。ここに試すための例があります:

更新：

これの方が速いかもしれません:

function addAndSort2(arr, val) {
    arr.push(val);
    i = arr.length - 1;
    item = arr[i];
    while (i > 0 && item < arr[i-1]) {
        arr[i] = arr[i-1];
        i -= 1;
    }
    arr[i] = item;
    return arr;
}

アップデート 2

@terrymorse はコメントで、JavaScript の Array.splice メソッドはとても高速で、時間計算量の改善だけではないと指摘しました。どうやらいくつかのリンクリストのマジックが使われているようです。つまり、単純な配列とは異なるデータ構造がまだ必要ですが、JavaScript の配列はその異なるデータ構造をネイティブに提供している可能性があるということです。

更新された JS Bin リンク

回答 #6

あなたの挿入関数は、与えられた配列がソートされていると仮定しており、新しい要素を挿入できる位置を直接検索します。通常、配列内のいくつかの要素を見ただけで判断します。

配列の一般的なソート関数は、これらの近道を取ることはできません。明らかに、それは少なくとも配列内のすべての要素を調べて、すでに正しい順序になっているかどうかを確認する必要があります。この事実だけでも、一般的なソートは挿入関数よりも遅くなります。

一般的なソートアルゴリズムは通常平均でO(n ⋅ log(n))であり、実装によっては配列がすでにソートされている場合に最悪ケースとなり、O(n2)の複雑さになることもあります。代わりに挿入位置を直接検索する場合は、複雑さはO(log(n))だけなので、常にはるかに高速です。

関連記事