JavaScript中的部分排序 [英] Partial sort in JavaScript

问题描述

是否有内置的JavaScript函数来执行部分排序？如果没有，实现它的好方法是什么？

Is there any built-in JavaScript function to do a partial sort? If not, what is a good way to implement it?

给定 N 元素的未排序数组，我想找到 K 元素相对于某些加权函数而言是最小的。 K 远小于 N ，因此对整个数组进行排序并获取第一个 K 元素效率不高。

Given an unsorted array of N elements, I would like to find K elements that are minimal with respect to some weighting function. K is much smaller than N, so it would be inefficient to sort the whole array and take the first K elements.

即使存在非标准的，依赖于浏览器的东西，我也会很高兴。我仍然可以回退到自定义JavaScript实现。

I would be happy even if there was something non-standard, browser-dependent. I could still fallback to the custom JavaScript implementation.

PS：这是我当前的自定义实现（没有考虑加权函数，只是对元素进行排序）简单）：

PS: This is my current custom implementation (without taking a weighting function into account, just sorting the elements as they are for simplicity):

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 目前为止最小的项目，使用二进制搜索来插入新元素。

The algorithm walks through the given array one single time, keeping track of a sorted list of the k smallest items so far, using binary search to insert new elements.

如果您认为可能更快或更优雅，请发布替代解决方案。非常欢迎时间。

Please post alternative solutions if you think they might be faster or more elegant. Timings are very welcome.

推荐答案

没有。只有完整数组排序 ，因此您需要使用自己的实现。

No. There's only the full array sort, so you will need to use your own implementation.

您的代码几乎没有改进（我想到了完全相同的算法） ： - ））：

Little improvement on your code (I had thought of exactly the same algorithm :-)):

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 变量）

(Even seems to be a little faster, I guess due to caching the max variable)

这篇关于JavaScript中的部分排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！