如何保持Javascript数组排序而不对其进行排序 [英] How to keep Javascript array sorted, without sorting it

问题描述

我有一个Node.js应用程序，在其中我经常需要执行以下操作: -检查特定数组是否已包含某些元素 -如果元素确实存在，请对其进行更新 -如果元素不存在，则将其推入数组，然后使用下划线_.sortBy

I have a Node.js application where I have to very often do following things: - check if particular array already contains certain element - if element does exist, update it - if element do not exist, push it to the array and then sort it using underscore _.sortBy

为检查元素是否已存在于数组中，我使用了此二进制搜索功能: http://oli.me. uk/2013/06/08/searching-javascript-arrays-with-a-binary-search/

For checking if the element already exists in the array, I use this binary search function: http://oli.me.uk/2013/06/08/searching-javascript-arrays-with-a-binary-search/

以这种方式，当数组的大小增加时，排序变得越来越慢. 我假设数组大小可能会增加到每个用户20000个项目.最终将有成千上万的用户.该数组由一个很短的字符串的键排序.如果需要，可以将其转换为整数.

In this way, when the size of the array grows, the sorting becomes slower and slower. I assume that the array size might grow to max 20 000 items per user. And eventually there will be thousands of users. The array is sorted by a key, which is quite a short string. It can be converted into integer if needed.

因此，我需要一种更好的方法来使数组保持排序， 而不是每次将新元素推入时对其进行排序.

So, I would require a better way to keep the array sorted, in stead of sorting it every time new element is pushed onto it.

所以，我的问题是，我应该/应该如何编辑我使用的二进制搜索算法，以使我能够 获取新元素应该放置在哪里的数组索引(如果数组中尚不存在)? 或者还有其他可能实现这一目标的可能性.当然，我可以使用某种循环，该循环从头开始并遍历数组，直到找到新元素的位置为止.

So, my question is, how should/could I edit the binary search algorithm I use, to enable me to get the array index where the new element should be placed, if it doesn't already exist in the array? Or what other possibilities there would be to achieve this. Of course, I could use some kind of loop that would start from the beginning and go through the array until it would find the place for the new element.

所有数据都存储在MongoDB中.

All the data is stored in MongoDB.

换句话说，我希望在每次推送新元素时不对数组进行排序而对数组进行排序.

In other words, I would like to keep the array sorted without sorting it every time a new element is pushed.

推荐答案

很容易修改此binaryIndexOf函数以在找不到匹配项时返回下一个元素的索引:

It's easy to modify this binaryIndexOf function to return an index of the next element when no matches found:

function binaryFind(searchElement) {
  'use strict';

  var minIndex = 0;
  var maxIndex = this.length - 1;
  var currentIndex;
  var currentElement;

  while (minIndex <= maxIndex) {
    currentIndex = (minIndex + maxIndex) / 2 | 0;
    currentElement = this[currentIndex];

    if (currentElement < searchElement) {
      minIndex = currentIndex + 1;
    }
    else if (currentElement > searchElement) {
      maxIndex = currentIndex - 1;
    }
    else {
      return { // Modification
        found: true,
        index: currentIndex
      };
    }
  }      

  return { // Modification
    found: false,
    index: currentElement < searchElement ? currentIndex + 1 : currentIndex
  };
}

因此，现在返回的对象如下:

So, now it returns objects like:

{found: false, index: 4}

其中index是找到的元素或下一个元素的索引.

where index is an index of the found element, or the next one.

因此，现在插入一个新元素将如下所示:

So, now insertion of a new element will look like:

var res = binaryFind.call(arr, element);
if (!res.found) arr.splice(res.index, 0, element);

现在，您可以将binaryFind添加到Array.prototype以及一些用于添加新元素的助手:

Now you may add binaryFind to Array.prototype along with some helper for adding new elements:

Array.prototype.binaryFind = binaryFind;

Array.prototype.addSorted = function(element) {
  var res = this.binaryFind(element);
  if (!res.found) this.splice(res.index, 0, element);
}

这篇关于如何保持Javascript数组排序而不对其进行排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！