在不使用 for 循环的情况下迭代 JavaScript 数组的更快方法

Question

这是我尝试解析的JSON数据的示例。

{
"tags": [{
"name": "SQOP_SPD",
"results": [{
},
"values": [
[1499771383876, 0, 0],
[1499771384800, 0, 0],
[1499771385885, 10, 0],
[1499771386893, 0, 0],
[1499771388867, 0, 0],
[1499771389879, 10, 0],
[1499771390878, 0, 0],
[1499771391787, 0, 0],
[1499771392870, 0, 0],
[1499771394015, 0, 0],
[1499771394955, 0, 0],
[1499771395800, 0, 0],
[1499771396882, 0, 0],
[1499771397904, 0, 0],
[1499771399906, 0, 0]
],
"attributes": {
"VId": ["9499"],
}
}],
"stats": {
"rawCount": 15
}
}
}

我正在使用for loop遍历values数组并检查是否存在特定的时间戳。

var items = dataa['tags'][j]['results'][0]['values'];
for (var k = 0; k < items.length; k++) {
if (items[k] == sortedTimeStampList[i]) {
// some code
}
}

当 values 数组中有大约 10000000 个条目时，页面开始挂起。

有没有更快的方法来检查values数组中的时间戳。

Answer 1

老实说，Javascript 中最快的循环形式是for循环，就像你目前一样有一个缓存索引。您的性能会有很大差异，具体取决于您使用的浏览器和计算机上的可用资源。

我相信您的应用程序中存在架构缺陷。您是否需要一次所有 10000000 个条目？二叉搜索将帮助您找到所需的内容(正如其他人所建议的那样(，但我认为可能不需要像您尝试的那样加载和循环所有条目。

考虑根据需要延迟加载条目，而不是一次加载所有条目。在需要时加载数据，根据需要。听起来您目前正在遇到内存限制，10000000 个条目是大量数据(特别是如果您有复杂对象的数组(。

我建议研究 Service Workers，它们是为在与浏览器不同的线程中运行的更多计算/繁重任务而制作的，但它们目前还没有得到很好的支持，所以如果你正在创建一个前端应用程序，你可能不是一个选择，你不控制哪些浏览器访问它。

Answer 2

一种可能性是迭代速度较慢(这样它就不会挂起(：

function find(callback,value,start=0){
for (var k = 0; k+start < items.length; k++) {
if (items[k+start][0] === value) {
callback(items[k+start]);
}
if(k==100){
setTimeout(find,0,callback,value,start+k);
break;
}
}

用例：

find(console.log,512627172);

或者，如果您只想获取某个时间戳，则可以使用地图：

var map=new Map(items.map(el=>[el[0],el.slice(1)]));
console.log(map.get(5293842838));

如果你只是想检查某个时间戳的存在，你也可以在你的数组中创建一个 Set(关于查找的性能更好(：

var set=new Set(items.map(el=>el[0]));
set.has(5293842838);

Answer 3

这是一个本机解决方案。在循环访问单个数据集时，我会得到大约150ms。

var obj = {
"tags": [{
"name": "SQOP_SPD",
"results": [{
"values": [],
"attributes": {
"VId": ["9499"]
}
}],
"stats": {
"rawCount": 15
}
}]
};
//Date for timing
var d = Date.now();
//Add 10000000 rows
while (obj.tags[0].results[0].values.length < 10000000) {
obj.tags[0].results[0].values.push([1499771383876 + obj.tags[0].results[0].values.length, 0, 0]);
}
console.log("spent " + (Date.now() - d) + "ms on adding rows");
//Native model for comparison
d = Date.now();
//Target is number 100 from the end
var target = obj.tags[0].results[0].values[obj.tags[0].results[0].values.length - 7];
//Find index
var iAmNative = obj.tags[0].results[0].values.
findIndex(function(a) {
return a[0] == target[0];
});
//Log output
console.log("spent " + (Date.now() - d) + "ms on succeeding natively, result:", obj.tags[0].results[0].values[iAmNative], " index:", iAmNative);
obj = null;

使用二进制搜索方法甚至更快：

var obj = {
"tags": [{
"name": "SQOP_SPD",
"results": [{
"values": [],
"attributes": {
"VId": ["9499"]
}
}],
"stats": {
"rawCount": 15
}
}]
};
//Date for timing
var d = Date.now();
//Add 10000000 rows
while (obj.tags[0].results[0].values.length < 10000000) {
obj.tags[0].results[0].values.push([1499771383876 + obj.tags[0].results[0].values.length, 0, 0]);
}
console.log("spent " + (Date.now() - d) + "ms on adding rows");
//The binary search algorithm
var binarySearch = (function() {
/**
* compare_complex
*
* @param {(number | string)} a
* @param {(number | string)} b
* @returns {number}
*/
function compare_complex(a, b) {
return a.toString().localeCompare(b.toString());
}
/**
* compare_number
*
* @param {number} a
* @param {number} b
* @returns {number}
*/
function compare_number(a, b) {
return a - b;
}
/**
* binarySearch
*
* @param {IBinarySearch} [args={ list: [], target: '' }]
* @returns {number}
*/
function binarySearch(args) {
if (args === void 0) {
args = {
list: [],
target: ''
};
}
var params = {
list: [],
key: null,
target: '',
threshold: 10,
complex: true
};
for (var key in args) {
if (args.hasOwnProperty(key) && params.hasOwnProperty(key)) {
params[key] = args[key];
}
}
var max = params.list.length - 1;
var maxKey = (params.key == null ? params.list[max] : params.list[max][params.key]);
var min = 0;
var minKey = (params.key == null ? params.list[min] : params.list[min][params.key]);
if (minKey == params.target) {
return min;
}
if (maxKey == params.target) {
return max;
}
var compare = (params.complex === true ? compare_complex : compare_number);
while (max - min >= params.threshold) {
var diff = max - Math.floor((max - min) / 2);
var diffKey = (params.key == null ? params.list[diff] : params.list[diff][params.key]);
var cmp = compare(diffKey, params.target);
if (cmp == 0) {
return diff;
} else if (cmp < 0) {
min = diff;
} else {
max = diff;
}
}
if (params.key != void 0) {
var index = params.list.slice(min, max).map(function(m) {
return m[params.key];
}).indexOf(params.target);
} else {
var index = params.list.slice(min, max).indexOf(params.target);
}
if (index >= 0) {
return index + min;
}
return index;
}
return binarySearch;
})();
//Binary model for comparison
d = Date.now();
//Target is number 100 from the end
var target = obj.tags[0].results[0].values[obj.tags[0].results[0].values.length - 7][0];
//Find index
var iAmBinary = binarySearch({
list: obj.tags[0].results[0].values,
target: target,
key: 0
});
//Log output
console.log("spent " + (Date.now() - d) + "ms on searching binarily, result:", obj.tags[0].results[0].values[iAmBinary], "index:", iAmBinary);
//Release memory
obj = null;

使用二进制方法，我的搜索时间一直少于10ms。