我无法解释为什么我的性能测试在2种不同类型的运行中返回显着不同的结果。process.hrtime()的执行时间返回完全不同的结果
步骤来重现问题:
- 从要点获取代码: https://gist.github.com/AVAVT/83685bfe5280efc7278465f90657b9ea
- 运行
node practice1.generator
- 运行
node practice1.performance-test
practice1.generator
应该产生一个test-data.json
文件,并登录一些搜索算法执行时间放入控制台。 之后,practice1.performance-test
从test-data.json
中读取,并对相同的数据执行完全相同的评估函数。
我的机器上输出始终与此类似:
> node practice1.generator
Generate time: 9,307,061,368 nanoseconds
Total time using indexOf : 7,005,750 nanoseconds
Total time using for loop : 7,463,967 nanoseconds
Total time using binary search : 1,741,822 nanoseconds
Total time using interpolation search: 915,532 nanoseconds
> node practice1.performance-test
Total time using indexOf : 11,574,993 nanoseconds
Total time using for loop : 8,765,902 nanoseconds
Total time using binary search : 2,365,598 nanoseconds
Total time using interpolation search: 771,005 nanoseconds
注意在indexOf
和binary search
相对于其他算法的情况下,在执行时间上的差异。
如果我反复运行node practice1.generator
或node practice1.performance-test
,但结果相当一致。
现在,这是如此令人不安,我找不到一种方法来找出哪个结果是可信的,以及为什么会出现这种差异。它是由生成的测试数组与JSON.parse-d测试数组之间的差异引起的吗?或者是由process.hrtime()
造成的;还是我不明白的原因?
更新:我已经查明indexOf
箱子原因是因为JSON.parse
。在practice1.generator
内部,tests
数组是原始生成的数组;而在practice1.performance-test
该数组是从json文件中读取的,并且可能与原始数组有所不同。
如果内practice1.generator
我不是JSON.parse()
从字符串的新数组:
var tests2 = JSON.parse(JSON.stringify(tests));
performanceUtil.performanceTest(tests2);
的indexOf
的执行时间是现在这两个文件是一致的。
> node practice1.generator
Generate time: 9,026,080,466 nanoseconds
Total time using indexOf : 11,016,420 nanoseconds
Total time using for loop : 8,534,540 nanoseconds
Total time using binary search : 1,586,780 nanoseconds
Total time using interpolation search: 742,460 nanoseconds
> node practice1.performance-test
Total time using indexOf : 11,423,556 nanoseconds
Total time using for loop : 8,509,602 nanoseconds
Total time using binary search : 2,303,099 nanoseconds
Total time using interpolation search: 718,723 nanoseconds
所以,至少我知道indexOf
运行原始阵列上,更好地差了JSON.parse
-d阵列上。 但我只知道原因,不知道为什么。
二进制搜索执行时间保持在2档不同,始终如一地服用〜1.7ms在practice1.generator
(使用JSON.parse
-d对象即使)和〜2.3ms在practice1.performance-test
。
以下是与要点相同的代码,供将来参考。
/*
* performance-utils.js
*/
'use strict';
const performanceTest = function(tests){
var tindexOf = process.hrtime();
tests.forEach(testcase => {
var result = testcase.input.indexOf(testcase.target);
if(result !== testcase.output) console.log("Errr", result, testcase.output);
});
tindexOf = process.hrtime(tindexOf);
var tmanual = process.hrtime();
tests.forEach(testcase => {
const arrLen = testcase.input.length;
var result = -1;
for(var i=0;i<arrLen;i++){
if(testcase.input[i] === testcase.target){
result = i;
break;
}
}
if(result !== testcase.output) console.log("Errr", result, testcase.output);
});
tmanual = process.hrtime(tmanual);
var tbinary = process.hrtime();
tests.forEach(testcase => {
var max = testcase.input.length-1;
var min = 0;
var check, num;
var result = -1;
while(max => min){
check = Math.floor((max+min)/2);
num = testcase.input[check];
if(num === testcase.target){
result = check;
break;
}
else if(num > testcase.target) max = check-1;
else min = check+1;
}
if(result !== testcase.output) console.log("Errr", result, testcase.output);
});
tbinary = process.hrtime(tbinary);
var tinterpolation = process.hrtime();
tests.forEach(testcase => {
var max = testcase.input.length-1;
var min = 0;
var result = -1;
var check, num;
while(max > min && testcase.target >= testcase.input[min] && testcase.target <= testcase.input[max]){
check = min + Math.round((max-min) * (testcase.target - testcase.input[min])/(testcase.input[max]-testcase.input[min]));
num = testcase.input[check];
if(num === testcase.target){
result = check;
break;
}
else if(testcase.target > num) min = check + 1;
else max = check - 1;
}
if(result === -1 && testcase.input[max] == testcase.target) result = max;
if(result !== testcase.output) console.log("Errr", result, testcase.output);
});
tinterpolation = process.hrtime(tinterpolation);
console.log(`Total time using indexOf : ${(tindexOf[0] * 1e9 + tindexOf[1]).toString().replace(/\B(?=(\d{3})+(?!\d))/g, ",")} nanoseconds`);
console.log(`Total time using for loop : ${(tmanual[0] * 1e9 + tmanual[1]).toString().replace(/\B(?=(\d{3})+(?!\d))/g, ",")} nanoseconds`);
console.log(`Total time using binary search : ${(tbinary[0] * 1e9 + tbinary[1]).toString().replace(/\B(?=(\d{3})+(?!\d))/g, ",")} nanoseconds`);
console.log(`Total time using interpolation search: ${(tinterpolation[0] * 1e9 + tinterpolation[1]).toString().replace(/\B(?=(\d{3})+(?!\d))/g, ",")} nanoseconds`);
}
module.exports = { performanceTest }
/*
* practice1.generator.js
*/
'use strict';
require('util');
const performanceUtil = require('./performance-utils');
const fs = require('fs');
const path = require('path');
const outputFilePath = path.join(__dirname, process.argv[3] || 'test-data.json');
const AMOUNT_TO_GENERATE = parseInt(process.argv[2] || 1000);
// Make sure ARRAY_LENGTH_MAX < (MAX_NUMBER - MIN_NUMBER)
const ARRAY_LENGTH_MIN = 10000;
const ARRAY_LENGTH_MAX = 18000;
const MIN_NUMBER = -10000;
const MAX_NUMBER = 10000;
const candidates = Array.from(Array(MAX_NUMBER - MIN_NUMBER + 1), (item, index) => MIN_NUMBER + index);
function createNewTestcase(){
var input = candidates.slice();
const lengthToGenerate = Math.floor(Math.random()*(ARRAY_LENGTH_MAX - ARRAY_LENGTH_MIN + 1)) + ARRAY_LENGTH_MIN;
while(input.length > lengthToGenerate){
input.splice(Math.floor(Math.random()*input.length), 1);
}
const notfound = input.length === lengthToGenerate ?
input.splice(Math.floor(Math.random()*input.length), 1)[0] : MIN_NUMBER-1;
const output = Math.floor(Math.random()*(input.length+1)) - 1;
const target = output === -1 ? notfound : input[output];
return {
input,
target,
output
};
}
var tgen = process.hrtime();
var tests = [];
while(tests.length < AMOUNT_TO_GENERATE){
tests.push(createNewTestcase());
}
fs.writeFileSync(outputFilePath, JSON.stringify(tests));
var tgen = process.hrtime(tgen);
console.log(`Generate time: ${(tgen[0] * 1e9 + tgen[1]).toString().replace(/\B(?=(\d{3})+(?!\d))/g, ",")} nanoseconds`);
performanceUtil.performanceTest(tests);
/*
* practice1.performance-test.js
*/
'use strict';
require('util');
const performanceUtil = require('./performance-utils');
const fs = require('fs');
const path = require('path');
const outputFilePath = path.join(__dirname, process.argv[2] || 'test-data.json');
var tests = JSON.parse(fs.readFileSync(outputFilePath));
performanceUtil.performanceTest(tests);
您运行的是什么版本的节点相当不错的解释,为什么在二进制JSON-解析方案获胜,插值搜索? –
嗨@SamH。我正在使用node v6.11 – AVAVT
刚刚在8.5.0 Current上测试过并得到了相同的结果。 – AVAVT