15

部分的なソートを行うための組み込みのJavaScript関数はありますか？そうでない場合、それを実装するための良い方法は何ですか？

N個の要素のソートされていない配列が与えられた場合、いくつかの重み関数に関して最小であるK個の要素を見つけたいと思います。KはNよりもはるかに小さいため、配列全体を並べ替えて最初のK要素を取得するのは非効率的です。

標準ではない、ブラウザに依存するものがあったとしても、私は幸せです。それでも、カスタムJavaScript実装にフォールバックできます。

PS：これは私の現在のカスタム実装です（重み関数を考慮せず、簡単にするために要素をそのまま並べ替えるだけです）：

function bisect(items, x, lo, hi) {
  var mid;
  if (typeof(lo) == 'undefined') lo = 0;
  if (typeof(hi) == 'undefined') hi = items.length;
  while (lo < hi) {
    mid = Math.floor((lo + hi) / 2);
    if (x < items[mid]) hi = mid;
    else lo = mid + 1;
  }
  return lo;
}

function insort(items, x) {
  items.splice(bisect(items, x), 0, x);
}

function partialSort(items, k) {
  var smallest = [];
  for (var i = 0, len = items.length; i < len; ++i) {
    var item = items[i];
    if (smallest.length < k || item < smallest[smallest.length - 1]) {
      insort(smallest, item);
      if (smallest.length > k)
        smallest.splice(k, 1);
    }
  }
  return smallest;
}

console.log(partialSort([5, 4, 3, 2, 1, 6, 7, 8, 1, 9], 3));

アルゴリズムは、指定された配列を1回ウォークスルーし、バイナリ検索を使用して新しい要素を挿入し、これまでにk個の最小アイテムのソートされたリストを追跡します。

より高速またはよりエレガントであると思われる場合は、代替ソリューションを投稿してください。タイミングは大歓迎です。

4

4 に答える 4

7

いいえ。完全な配列sortしかないため、独自の実装を使用する必要があります。

あなたのコードの少しの改善（私はまったく同じアルゴリズムを考えていました:-)）：

function partialSort(items, k) {
    var smallest = items.slice(0, k).sort(),
        max = smallest[k-1];
    for (var i = k, len = items.length; i < len; ++i) {
        var item = items[i];
        if (item < max) {
            insort(smallest, item);
            smallest.length = k;
            max = smallest[k-1];
        }
    }
    return smallest;
}

（少し速いようmaxですが、変数をキャッシュしているためだと思います）

于 2013-03-25T17:44:07.753 に答える
3

kが比較的小さい場合は、最大ヒープを実装する価値があります（JavaScriptにネイティブヒープがないため）。

  • 最初のk個の値の最大ヒープを作成します

  • 残りの値ごとに：

    • ヒープのルートよりも小さい場合は、ルートをこの値に置き換えます。それ以外の場合は、値を無視してください。ヒープのサイズは決して変更されないことに注意してください。

  • 最後に、ヒープをソートして返します。

これは実際には、最小ヒープを使用する別のアイデアの改善ですが、配列全体をヒープ化する必要があるため、実行速度は遅くなります。配列全体をヒープ化した後、そのヒープから値をk倍抽出し、それらの値を返します。

両方のソリューションをBergiのjsperf.comパフォーマンステストに追加しました（jsbench.meにコピー）。その特定のテスト（5000配列値、k = 10）の場合、最大ヒープソリューションの方が高速です。しかし、この利点は、kが増加するにつれて縮小します。

MaxHeapソリューションのコードは次のとおりです。

// A few Heap-functions that operate on an array
function maxSiftDown(arr, i=0, value=arr[i]) {
    if (i >= arr.length) return;
    while (true) {
        var j = i*2+1;
        if (j+1 < arr.length && arr[j] < arr[j+1]) j++;
        if (j >= arr.length || value >= arr[j]) break;
        arr[i] = arr[j];
        i = j;
    }
    arr[i] = value;
}

function maxHeapify(arr) {
    for (var i = arr.length>>1; i--; ) maxSiftDown(arr, i);
    return arr;
}

// The main algorithm
function partialSortWithMaxHeap(items, k) {
    var heap = maxHeapify(items.slice(0, k));
    for (var i = k, len = items.length; i < len; ++i) {
        var item = items[i];
        if (item < heap[0]) maxSiftDown(heap, 0, item);
    }
    return heap.sort((a,b) => a-b);
}

// Sample data & call
var arr = Array.from({length:5000}, () => Math.floor(Math.random() * 1e5));
   
console.log(partialSortWithMaxHeap(arr, 10));

于 2019-08-05T13:39:05.110 に答える
2

ネイティブの部分ソート関数はありません。必要なものに最も近いのはArray.filterです。

function isSmallEnough(element, index, array) {
  return (element <= 10);
}
var filtered = [12, 5, 8, 130, 44].filter(isSmallEnough);
// filtered is [5, 8]

この例は、上記のリンクから借用（およびわずかに変更）されています。

于 2013-03-25T17:50:09.887 に答える
0

Array.sort（f）のようなオブジェクトで動作するバージョンを作成しました。

function partialSort(items, k,f) {
    function bisect(items, x, lo, hi) {
        var mid;
        if (typeof(lo) == 'undefined') lo = 0;
        if (typeof(hi) == 'undefined') hi = items.length;
        while (lo < hi) {
        mid = Math.floor((lo + hi) / 2);
        if (0>f(x,items[mid])) hi = mid;
        else lo = mid + 1;
        }
        return lo;
    }

    function insort(items, x) {
        items.splice(bisect(items, x), 0, x);
    }

    var smallest = items.slice(0, k).sort(f),
        max = smallest[k-1];
    for (var i = k, len = items.length; i < len; ++i) {
        var item = items[i];
        if (0>f(item,max)) {
            insort(smallest, item);
            smallest.length = k;
            max = smallest[k-1];
        }
    }
    return smallest;
}

// [ { e: 1 }, { e: 1 }, { e: 2 } ]
console.log(partialSort([{e:4},{e:6},{e:1},{e:8},{e:3},{e:1},{e:6},{e:2}],3,(a,b)=>a.e-b.e))
console.log()
于 2019-08-16T09:03:21.590 に答える