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

вая массив, имеющий.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");

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

console.time("iterate from start and end");
for (let i = 0, k = len - 1; i < len && k >= 0; i++, k--) {
  if (arr[i] === n || arr[k] === n) break;
}
console.timeEnd("iterate from start and end");

JSPerfhttps://jsperf.com/iterate-from-start-iterate-from-start-and-end/1

 Jaromanda X01 нояб. 2017 г., 06:53
вам нужно будет спросить, делали ли вы это в более чем одном браузере: p вы действительно понимаете, что в каждой итерации второго кода происходит намного больше, верно? дополнительная проверка>= и|| и другой===
 Jaromanda X01 нояб. 2017 г., 06:58
Тем не менее, немного больше происходит в каждой итерации, возможно, не может быть так легко "оптимизирован" на лету?
 guest27131401 нояб. 2017 г., 07:00
@JaromandaX Требуется ли дополнительное время для поиска второго объекта? Должны ли быть два отдельных цикла для каждого начала до конца и конца до начала? Или это все тот же код в двух разных блоках?
 guest27131401 нояб. 2017 г., 06:57
@JaromandaX Да. Chromium и Firefox имеют тот же результат, что итерация от начала до конца быстрее всего. Ожидаемый результат для начала и конца, чтобы начать, чтобы быть быстрее, чем только начать и закончить какarr[k] === n должно быть достигнуто доarr[i] === nменьше шагов от99 в51 чем из0 в51; 51 а также48 соответственно
 Jaromanda X01 нояб. 2017 г., 07:01
чувак, я последний человек, который действительно спрашивает о бенчмаркинге и внутренностях подобных вещей - если что-то занимает 101мс вместо 80мс, мне действительно все равно: p

Ответы на вопрос(5)

попробуйте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");

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

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

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

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

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

Решение Вопроса

Больше операций занимает больше времени.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Но тем не менее, есть несколько разных подходов к микрооптимизации такого цикла - проверкаэти ориентиры.

let (все еще?) медленнее, чемvar, видетьПочему использование `let` внутри цикла` for` так медленно в Chrome? а такжеПочему в nodejs допускается медленнее, чем var в цикле for?, Этот разрыв (и около 50 раз) объема тела цикла фактически доминирует в вашей среде выполнения, поэтому ваш неэффективный код не в два раза медленнее.сравнивая с0 немного быстрее, чем сравнение с длиной, что ставит петли назад в преимущество. ВидетьПочему итерация массива назад быстрее, чем вперед, Производительность цикла JavaScript - почему уменьшение итератора до 0 быстрее, чем увеличение а такжеЦиклы действительно быстрее наоборот?в общем смКакой самый быстрый способ перебрать массив в JavaScript?: меняется с обновления двигателя на обновление двигателя. Не делайте ничего странного, пишите идиоматический код, и это оптимизируется лучше.
 dnickless14 нояб. 2017 г., 22:03
Я добавил еще одну ревизию ваших тестов JSPerf, показывающую несколько развернутых примеров, которые обычно превосходят обычные циклы:jsperf.com/iterate-from-start-iterate-from-start-and-end/9 Имейте в виду, есть это, чтобы понять:stackoverflow.com/questions/38111355/...

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

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

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

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

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

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

Мастер в CS, и вы получите подсчет тактов и времени сортировки. Скорее всего, вы создадите свой собственный язык в машинных инструкциях.

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

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

Коммерция, НАСА, АЭС, оборонные подрядчики, немного робототехники, вы поняли идею. , ,

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

Ура, вуки

 Bergi14 нояб. 2017 г., 16:35
Даже машинный код не работает так, как написано на современных процессорах :-)
 Wookies-Will-Code15 нояб. 2017 г., 00:19
Да, это правда. Как погоня за Алисой по кроличьей норе. Спасибо Tech Gods за Gigaflops, это делает многое из этого неуместным.

Ваш ответ на вопрос