如何保持Javascript数组排序,而不对其进行排序

Question

我有一个Node.js应用程序,我必须经常做以下事情: - 检查特定数组是否已包含某些元素 - 如果元素确实存在,请更新它 - 如果元素不存在,则将其推送到数组然后对其进行排序使用下划线_.sortBy

为了检查元素中是否已经存在元素,我使用这个二进制搜索函数:http: //oli.me.uk/2013/06/08/searching-javascript-arrays-with-a-binary-search/

这样,当数组的大小增加时,排序变得越来越慢.我假设数组大小可能会增加到每个用户最多20 000个项目.最终会有成千上万的用户.数组按键排序,这是一个很短的字符串.如果需要,它可以转换为整数.

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

所以,我的问题是,我应该如何/可以编辑我使用的二进制搜索算法,使我能够获得应该放置新元素的数组索引,如果它不存在于数组中？或者有什么其他可能性来实现这一目标.当然,我可以使用某种从头开始并经过数组的循环,直到它找到新元素的位置.

所有数据都存储在MongoDB中.

换句话说,我想保持数组排序,而不是每次推送新元素时对其进行排序.

Answer 1

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

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

所以,现在它返回如下对象:

{found: false, index: 4}

where index是找到的元素的索引,或下一个元素的索引.

所以,现在插入一个新元素将如下所示:

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

现在,您可以添加binaryFind到Array.prototype一些帮手沿着添加新元素:

Array.prototype.binaryFind = binaryFind;

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

Answer 2

如果您的数组已经排序并且您想要插入一个元素，为了保持它的排序，您需要将其插入到数组中的特定位置。幸运的是，数组有一个方法可以做到这一点： Array.prototype.splice

因此，一旦获得需要插入的索引（您应该通过对二分搜索进行简单修改来获得），您可以执行以下操作：

myArr.splice(myIndex,0,myObj);
// myArr your sorted array
// myIndex the index of the first item larger than the one you want to insert
// myObj the item you want to insert

编辑：二分搜索代码的作者有相同的想法：

因此，如果您想插入一个值并想知道应该将其放在哪里，您可以运行该函数并使用返回的数字将该值拼接到数组中。 来源