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