JavaScript 在不同时间执行相同的函数

Question

寻找著名的勒索信任务的最佳解决方案，(eg. from 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);

提前非常感谢您!

Answer 1

访问内存是一个随机过程(也称为随机存取内存)。 当您执行“magazine.indexOf(w)”时，它是随机内存访问，以获取完整内存中值“w”内存单元的位置。因此，有时它很慢，有时很快，这取决于它在这个随机过程中检查了多少个内存单元。这会影响所需的时间。