4

仅供参考：我已经在使用 Web Workers 进行此操作，并且效果很好，但我只是在探索使用 process.nextTick 可以做什么和不能做什么。

所以我有一个包含一百万个元素的数组，我在 Node.JS 中进行排序。我希望 Node 在执行此操作时能够响应其他请求。

有没有办法让 Array.prototype.sort() 不阻塞其他进程？由于这是一个核心函数，我不能插入任何 process.nextTick()。

我可以手动实现快速排序，但我看不出你如何以连续传递风格有效地做到这一点，这似乎是 process.nextTick() 所必需的。我可以修改一个 for 循环来做到这一点，但 sort() 似乎是不可能的。

4

3 回答 3

2

虽然不可能以某种方式使其Array.prototype.sort本身以某种方式异步运行，但异步排序绝对是可能的，正如这个排序演示所示，它展示了 setImmediate (shim) 相对于 setTimeout 的速度优势。

不幸的是，源代码似乎没有任何许可证。在https://github.com/jphpsf/setImmediate-shim-demo上用于演示的 Github 存储库将Jason Weber 命名为作者。您可能想问他是否要使用（部分）代码。

我认为如果您使用 setImmediate（自 Node 0.10 起可用），单个排序操作将有效地与 I/O 回调交错。对于如此大量的工作，我不推荐 process.nextTick （如果它确实有效，因为有 1000 maxTickDepth 限制）。请参阅setImmediate vs. nextTick了解一些背景。

使用 setImmediate 而不是简单的“同步”处理总体上肯定会更慢，因此您可以选择在每个“tick”处理一批单独的排序操作以加快处理速度，但代价是 Node 在此期间没有响应。我认为只有通过实验才能找到速度和 I/O 响应能力之间的正确平衡。

一个更简单的选择是更像网络工作者：生成一个子进程并在那里进行排序。您面临的最大问题是将排序的数据传输回您的主进程（大概是为了生成某种输出）。AFAIK 没有什么比 Node.js的可转移对象更好的了。缓冲排序后的数组后，您可以将结果流式传输到子进程 stdout 并在主进程中解析数据，或者更简单；使用子进程消息传递。

您可能没有空闲的 cpu 核心，因此子进程会占用其他进程的 cpu 时间。为避免排序过程损害您的其他进程，您可能需要为其分配低优先级。使用 Node 本身似乎不可能做到这一点，但您可以尝试使用nice，如下所述：https ://groups.google.com/forum/#!topic/nodejs/9O-2gLJzmcQ 。我没有这方面的经验。

于 2013-05-22T19:55:22.200 回答
0

好吧，我最初认为您可以使用async.sortBy，但经过仔细检查，它似乎不会像您需要的那样运行。有关类似问题，请参阅Array.sort 和 Node.js，尽管目前还没有公认的答案。

于 2013-04-13T21:03:42.033 回答
0

我知道这是一个相当古老的问题，但我遇到了类似的情况，仍然没有找到简单的解决方案。

我修改了一个现有的快速排序并发布了一个包，它定期在此处放弃对事件循环的执行： https ://www.npmjs.com/package/qsort-async

如果您熟悉传统的快速排序，我唯一的修改是对执行分区的初始函数。基本上，该函数仍然在原地修改数组，但现在返回一个承诺。如果它试图在一次迭代中处理太多元素，它会停止执行 eventloop 中的其他事情。（我相信我指定的默认大小是 10000）。

注意：在这里使用 setImmedate 而不是 process.nextTick 或 setTimeout 很重要。nextTick 实际上会将您的执行放在进程 IO 之前，并且您在响应与 IO 相关的其他请求时仍然会遇到问题。setTimeout 太慢了（我相信其他答案之一链接了一个演示）。

注意 2：如果像合并排序这样的东西更符合您的风格，您可以在排序的“合并”功能中执行相同的逻辑。

const immediate = require('util').promisify(setImmediate);

async function quickSort(items, compare, left, right, size) {
  let index;
  if (items.length > 1) {
    index = partition(items, compare, left, right);
    if (Math.abs(left - right) > size) {
      await immediate();
    }
    if (left < index - 1) {
      await quickSort(items, compare, left, index - 1, size);
    }
    if (index < right) {
      await quickSort(items, compare, index, right, size);
    }
  }
  return items;
}

完整代码在这里：https ://github.com/Mudrekh/qsort-async/blob/master/lib/quicksort.js

于 2019-08-19T16:12:29.160 回答