В поисках оптимального решения для известной задачи Ransom Note, (например, из HackerRank) , я экспериментировал со временем выполнения функции JavaScript, когда она итерирует массивы различной длины (пошаговое выполнение немного в стороне от первоначальной идеи задачи).
Я регистрировал время, необходимое для перебора пар массивов длиной: 1. одна тысяча 2. десять тысяч 3. сто тысяч 4. двести тысяч 5. сотен тысяч.
Конечно, я ожидал, что время увеличится по мере увеличения длины массива, и хотел увидеть шаблон за ним.
Однако результаты меня удивили: одна и та же функция, выполняющая одинаковые действия с точно такими же массивами, имеет значительную разницу во времени выполнения . Иногда.
Я сохранил время выполнения для каждой длины в одном объекте, что привело к следующему:
veryVeryBigData: {
'1000': [ 1, 0, 0, 0, 0, 1, 0, 0 ],
'10000': [ 12, 12, 12, 12, 12, 12, 12, 12 ],
'100000': [ 1464, 5498, 5637, 5591, 5389, 5524, 5481, 5440 ],
'200000': [ 5858, 21847, 22704, 22214, 21638, 21845, 21798, 21926 ],
'400000': [ 64027, 91809, 92233, 90515, 92953, 92394, 93374, 104708 ]
}
Как вы можете видеть, существуют значительные различия для некоторых итераций для массивов от 100000 и более .
Буду очень признателен, если кто-нибудь подскажет, почему это происходит, или порекомендует определенный предмет для более глубокого понимания.
Мой код указан ниже:
const ten = ["one", "two", "three", "four", "five", "six", "seven", "eight", "nine", "ten" ];
const thousand = Array(100).fill(ten).flat();
const tenThousand = Array(10).fill(thousand).flat();
const hundredThousand = Array(10).fill(tenThousand).flat();
const twoHundredThousand = Array(2).fill(hundredThousand).flat();
const fourHundredThousand = Array(4).fill(hundredThousand).flat();
const wordsArrays = [thousand, tenThousand, hundredThousand, twoHundredThousand, fourHundredThousand];
const veryVeryBigData = { 1000: [], 10000: [], 100000: [], 200000: [], 400000: [] };
const checkMagazine = (mag, note) => {
const start = Date.now();
let iterations = 0;
let result = "Yes";
let magazine = [...mag];
note.map((w, i) => {
iterations++;
const index = magazine.indexOf(w);
if (magazine.includes(w)) {
magazine.splice(index, 1);
} else {
result = "No";
}
});
const totalTime = Date.now() - start;
veryVeryBigData[note.length].push(totalTime);
console.log("Result: ", result);
};
const performChecks = (mags, ns) => {
mags.map(magazine => {
ns.map(note => {
if (note.length === magazine.length) {
checkMagazine(magazine, note);
}
});
});
};
//for the sake of experiment I compare two identical arrays, as my goal is just to calculate iteration time
//do it 8 times to see different results
for (let i = 0; i <= 8; i++) {
performChecks(wordsArrays, wordsArrays);
}
console.log("veryVeryBigData: ", veryVeryBigData);
Большое спасибо заранее!