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));

该算法遍历给定数组一次，跟踪到目前为止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，实现 Max Heap 是值得的（由于 JavaScript 中缺少原生堆）：

  • 创建前k个值的最大堆

  • 对于每个剩余值：

    • 如果它小于堆的根，则将根替换为该值。否则忽略该值。请注意，堆的大小永远不会改变。

  • 最后对堆进行排序并返回。

这实际上是对使用Min Heap 的另一个想法的改进，但是需要堆化整个数组，因此不会运行得那么快。在堆化整个数组之后，您只需从该堆中提取k次值，然后返回这些值。

我已将这两种解决方案添加到Bergi 的 jsperf.com 性能测试（复制到jsbench.me）。对于该特定测试（5000 个数组值，k = 10），最大堆解决方案更快。但是这个优势会随着k的增加而缩小。

这是 Max Heap 解决方案的代码：

// 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 回答