Подтвердить что ты не робот

Почему использование цикла для итерации от начала массива до конца быстрее, чем повторение начала и конца и завершения?

Учитывая массив с .length 100, содержащий элементы, имеющие значения 0 - 99 в соответствующих индексах, где требование состоит в том, чтобы найти элемент массива, равный n: 51.

Почему используется цикл для итерации от начала массива до конца быстрее, чем повторение начала и конца и завершения? 

const arr = Array.from({length: 100}, (_, i) => i);
const n = 51;
const len = arr.length;

console.time("iterate from start");
for (let i = 0; i < len; i++) {
  if (arr[i] === n) break;
}
console.timeEnd("iterate from start");
4b9b3361

ОТВЕТЫ

Ответ 1

Ответ довольно очевиден:

Дополнительные операции занимают больше времени.

Оценивая скорость кода, вы можете посмотреть, сколько операций он будет выполнять. Просто переходите и считайте их. Каждая инструкция будет принимать один или несколько циклов процессора, и чем больше времени, тем больше времени потребуется для запуска. Эти разные инструкции занимают различное количество циклов, в основном это не имеет значения - в то время как поиск массива может быть более дорогостоящим, чем целочисленная арифметика, обе из них в основном занимают постоянное время, а если их слишком много, он доминирует над стоимостью нашего алгоритма.

В вашем примере существует несколько различных типов операций, которые вы можете рассчитывать индивидуально:

  • сравнения
  • приращений/декремент
  • поиск массива
  • условные прыжки

(мы могли бы быть более зернистыми, например, подсчитывать операции выборки и хранения, но это вряд ли имеет значение - все равно все регистры), и их число в основном линейно для остальных).

Теперь оба ваших кода повторяются примерно в 50 раз - элемент, на котором они разбивают цикл, находится в середине массива. Игнорируя ошибки "за-на-несколько", это числа:

               |  forwards  | forwards and backwards
---------------+------------+------------------------
>=/===/<       |       100  |                   200
++/--          |        50  |                   100
a[b]           |        50  |                   100
&&/||/if/for   |       100  |                   200

Учитывая, что не неожиданно, что выполнение дважды работы занимает значительно больше времени.

Я также отвечу на несколько вопросов из ваших комментариев:

Требуется ли дополнительное время для поиска второго объекта?

Да, каждый индивидуальный счетчик подсчета. Это не похоже, что они могут быть выполнены сразу или оптимизированы в единый поиск (можно предположить, если они искали один и тот же индекс).

Должны ли быть два отдельных цикла для каждого начала и конца для запуска?

Не имеет значения для количества операций, только для их порядка.

Или, иначе говоря, какой самый быстрый способ найти элемент в массиве?

В отношении заказа нет "самого быстрого", если вы не знаете, где находится элемент (и они распределены равномерно), вы должны попробовать каждый индекс. Любой порядок - даже случайный - будет работать одинаково. Обратите внимание, однако, что ваш код строго хуже, поскольку он смотрит на каждый индекс дважды, когда элемент не найден - он не останавливается посередине.

Но все же существует несколько различных подходов при микрооптимизации такого цикла: проверьте эти критерии.

Ответ 2

@Берги правильно. Больше операций - больше времени. Зачем? Больше тактовых циклов процессора. Время действительно является ссылкой на то, сколько циклов синхронизации требуется для выполнения кода. Для того, чтобы добраться до мелочей, вам нужно посмотреть код машинного уровня (например, код уровня сборки), чтобы найти истинные доказательства. Каждый тактовый цикл CPU (core?) Может выполнять одну команду, поэтому сколько команд вы выполняете?

Я не учитывал тактовые циклы в течение длительного времени с момента программирования процессоров Motorola для встроенных приложений. Если ваш код занимает больше времени, он на самом деле генерирует более большой набор команд машинного кода, даже если цикл короче или работает равное количество раз.

Никогда не забывайте, что ваш код фактически скомпилирован в набор команд, которые CPU будет выполнять (указатели на ячейки памяти, указатели уровня кода инструкций, прерывания и т.д.). Так работают компьютеры и их легче понять на уровне микроконтроллеров, таких как процессор ARM или Motorola, но то же самое верно для современных машин, на которых мы работаем сегодня.

Ваш код просто не работает так, как вы его пишете (звучит безумно правильно?). Он запускается, поскольку он скомпилирован для запуска как инструкции на уровне машины (писать компилятор не забавно). Математическое выражение и логика могут быть скомпилированы в довольно кучу сборки, код машинного уровня, и это зависит от того, как компилятор решает его интерпретировать (это сдвиг бит и т.д., Помните, что каждый двоичный математик?)

Ссылка: https://software.intel.com/en-us/articles/introduction-to-x64-assembly

Твой вопрос трудно ответить, но поскольку @Bergi заявил, что чем больше операций, тем дольше, но почему? Чем больше циклов синхронизации, необходимых для выполнения вашего кода. Двухъядерный, четырехъядерный, поточный, сборный (машинный язык) сложный. Но никакой код не выполняется, как вы его написали. С++, C, Pascal, JavaScript, Java, если вы не пишете в сборке (даже это компилируется до машинного кода), но ближе к фактическому коду выполнения.

Мастер в CS, и вы сможете подсчитывать такты и время сортировки. Вероятно, вы создадите собственный язык, созданный на машинных наборах команд.

Большинство людей говорят, кого это волнует? Память сегодня дешевая, а процессоры быстро кричат ​​и становятся быстрее.

Но есть некоторые критические приложения, где требуется 10 мс, где требуется немедленное прерывание и т.д.

Коммерция, НАСА, Атомная электростанция, Подрядчики защиты, некоторые робототехники, вы получаете эту идею.,

Я голосую, дайте ему двигаться и продолжайте двигаться.

Cheers, Wookie

Ответ 3

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

Каждое обновление переменной требует времени, каждое сравнение требует времени, и вы делаете в два раза больше. Поскольку вы знаете, что в этой версии будет выполнено одно или два меньше итераций цикла, вы должны поразмыслить, что это будет стоить в два раза больше процессорного времени.

Эта стратегия по-прежнему O(n) сложна по времени, так как она смотрит только на каждый элемент один раз, это особенно заметно, когда элемент находится рядом с центром списка. Если это близко к концу, этот подход будет иметь более ожидаемое время выполнения. Попробуйте найти элемент 90 в обоих, например.

Ответ 4

Выбранный ответ превосходный. Я хотел бы добавить еще один аспект: Try findIndex(), это в 2-3 раза быстрее, чем использование циклов:

const arr = Array.from({length: 900}, (_, i) => i);
const n = 51;
const len = arr.length;

console.time("iterate from start");
for (let i = 0; i < len; i++) {
  if (arr[i] === n) break;
}
console.timeEnd("iterate from start");

console.time("iterate using findIndex");
var i = arr.findIndex(function(v) {
  return v === n;
});
console.timeEnd("iterate using findIndex");

Ответ 5

Другие ответы здесь касаются основных причин, но я думаю, что интересным дополнением может быть упоминание кеша.

В общем, последовательный доступ к массиву будет более эффективным, особенно с большими массивами. Когда ваш процессор считывает массив из памяти, он также выбирает соседние ячейки памяти в кеш. Это означает, что при извлечении элемента n элемент n+1 также, вероятно, загружается в кеш. Теперь в настоящий момент кеш относительно велик, поэтому ваш 100-int-массив, возможно, удобно вписывается в кеш. Однако, в массиве гораздо большего размера, чтение последовательно будет быстрее, чем переключение между началом и концом массива.