我有一个Node.js应用程序,我必须经常做以下事情：
– 检查特定阵列是否已包含某些元素
– 如果元素确实存在,请更新它
– 如果元素不存在,则将其推送到数组,然后使用下划线_.sortBy对其进行排序
– 检查特定阵列是否已包含某些元素
– 如果元素确实存在,请更新它
– 如果元素不存在,则将其推送到数组,然后使用下划线_.sortBy对其进行排序
为了检查元素是否已存在于数组中,我使用此二进制搜索函数：
http://oli.me.uk/2013/06/08/searching-javascript-arrays-with-a-binary-search/
这样,当数组的大小增加时,排序变得越来越慢.
我假设数组大小可能会增加到每个用户最多20 000个项目.最终会有成千上万的用户.数组按键排序,这是一个很短的字符串.如果需要,它可以转换为整数.
所以,我需要一种更好的方法来保持数组排序,
每当新元素被推到它上时,而不是对它进行排序.
所以,我的问题是,我应该如何/可以编辑我使用的二进制搜索算法,以使我能够
获取应放置新元素的数组索引(如果数组中尚不存在)？
或者有什么其他可能性来实现这一目标.当然,我可以使用某种从头开始并经过数组的循环,直到它找到新元素的位置.
所有数据都存储在MongoDB中.
换句话说,我想保持数组排序,而不是每次推送新元素时对其进行排序.
解决方法
当找不到匹配项时,很容易修改这个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}
其中index是找到的元素或下一个元素的索引.
所以,现在插入一个新元素将如下所示：
var res = binaryFind.call(arr,element); if (!res.found) arr.splice(res.index,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,element);
}
