Есть ли более эффективный во время выполнения способ перебора этого массива? (JavaScript)

Question

Так что мне просто интересно, отнимает ли присвоение переменной переменной эффективность времени выполнения в этой простой функции ниже:

const biggestNumberInArray = (arr) => {
  let biggest = 0;
  for (item of arr) {
    biggest = (item > biggest) ? item : biggest;
  }
  return biggest;
}

Внутри для l oop каждая итерация имеет вид: хорошо, присваивая значение переменной large . Так что если бы я написал вместо этого:

if (biggest < item) { biggest=item;};

, стала бы эта функция более эффективной? У меня нет большого массива, этот вопрос в основном теоретический, я хочу понять, как работает механика.

спасибо!

Answer 1

С учетом двух точек зрения:

1. С теоретической точки зрения, т. Е. С учетом Асимптоти c Сложность , это не имеет никакого значения. Оба алгоритма будут работать за линейное время - O (n), так как вам все равно придется перебирать массив. Задания занимают постоянное время. Предложение if также занимает постоянное время. Одно постоянное время или два постоянных времени все еще остаются постоянными.

2. С практической точки зрения, это может иметь какое-то значение, но, вероятно, не будет актуально, особенно для больших массивов. Для небольших массивов относительная разница может быть более существенной, но, поскольку время мало, нас это обычно не волнует.

Answer 2

Я протестировал следующие 5 функций на jsbench.me (ссылка ведет на сохраненные тесты):

const data = [1,2,3,4,5,6,7,8,9,0,99,88,77,66,55,44,33,22,11]

const fn1 = xs => xs.reduce((acc, x) => acc > x ? acc : x, -Infinity)

const fn2 = xs => {
  let res = -Infinity
  for (const x of xs) res = x > res ? x : res
  return res
}

const fn3 = xs => {
  let res = -Infinity
  for (const x of xs) {
    if (x > res) res = x
  }
  return res
}

const fn4 = xs => xs.reduce((acc, x) => Math.max(acc, x), -Infinity)

const fn5 = ([x, ...xs], acc = -Infinity) =>
  x == undefined ? acc : fn5(xs, x > acc ? x : acc)

Самая быстрая функция на сегодняшний день - это # ​​1 на основе Array.prototype.reduce и избегая переназначения.

Функции # 2 - # 4 (включая вашу исходную функцию и функцию с потенциальным улучшением производительности, которую вы предложили) все на 40-55% медленнее, чем # 1. # 4 (reduce с Math.max), по-видимому, стабильно быстрее, чем # 2 и # 3, примерно на 20%.

Самая медленная функция (которая зависит от рекурсии) - это # ​​5, с тактовой частотой около На 80-90% медленнее, чем # 1.

Math.max(x, y) медленнее, чем x > y ? x : y.

Я тестировал на MacBook Pro 2019 с MacOS 10.15.1 (Catalina) и Chrome v79.0.3945.88 (64 бита). Вы можете получить разные результаты с другой настройкой теста, но я уверен, что решение, основанное на reduce и избежании переназначения, будет самым быстрым вариантом в большинстве современных браузеров.