Почему циклический просмотр массива намного быстрее, чем родной JavaScript indexOf?

Question

Почему цикл по массиву выполняется намного быстрее, чем в нативном JavaScript indexOf? Есть ли ошибка или что-то, что я не учитываю? Я ожидал, что нативные реализации будут быстрее.

                For Loop        While Loop      indexOf
Chrome 10.0     50,948,997      111,272,979     12,807,549
Firefox 3.6     9,308,421       62,184,430      2,089,243
Opera 11.10     11,756,258      49,118,462      2,335,347   

http://jsben.ch/#/xm2BV

Answer 1

Через 5 лет в браузерах произошло много изменений. Теперь производительность indexOf увеличилась и, безусловно, лучше, чем у любой другой пользовательской альтернативы.

Chrome версии 49.0.2623.87 (64-разрядная версия)

Answer 2

Вероятно, потому что фактическая реализация indexOf делает намного больше, чем просто циклически перебирает массив. Вы можете увидеть внутреннюю реализацию Firefox здесь:

https://developer.mozilla.org/en/JavaScript/Reference/Global_Objects/Array/indexOf

Есть несколько вещей, которые могут замедлить цикл, которые существуют для здравомыслия:

• Массив повторно приводится к Объекту
• fromIndex преобразуется в число
• Они используют Math.max вместо троичного
• Они используют Math.abs

Answer 3

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

Извинения, но то, как это делается, приводит к ужасно неправильным выводам, поэтому я должен немного остановиться и прокомментировать предоставленные ответы.

Что не так с другими тестами здесь

Измерение, где найти элемент 777 в массиве, который никогда не изменяется, всегда приводя к индексу 117, кажется настолько неуместным по очевидным причинам, что я не могу объяснить, почему. Вы не можете разумно экстраполировать что-либо из такого слишком специфического теста! Единственная аналогия, которую я могу придумать, - это провести антропологическое исследование на одном человеке, а затем назвать результаты обобщенным обзором всей культуры страны, в которой живет этот человек. Другие критерии не так уж и велики. лучше.

Еще хуже: принятый ответ - это изображение без ссылки на эталонный тест, который использовался , поэтому у нас нет возможности контролировать, верен ли код для этого эталонного теста (я надеюсь это скриншот ссылки jsperf, которая первоначально была в вопросе, а затем отредактирована в пользу новой ссылки jsben.ch). Это даже не объяснение первоначального вопроса:. почему один работает лучше, чем другие (весьма спорно утверждение, чтобы начать с)

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

Теперь мы должны сравнивать производительность различных способов выполнения линейного поиска в массиве. Подумайте о самом алгоритме на секунду:

• посмотреть на значение для данного индекса в массиве.
• сравнить значение с другим значением.
  • если равно, вернуть индекс
  • если он не равен, перейти к следующему индексу и сравнить следующее значение.

Вот и весь алгоритм линейного поиска, верно?

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

Да, упорядоченные и несортированные массивы могут иметь значение при сравнении производительности линейного поиска с двоичного или интерполяционного поиска алгоритмов, но никто здесь не делает этого!

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

Вот результат более или менее копирования эталонного теста, связанного в вопросе с perf.zone (который более надежен, чем jsben.ch), но со следующими модификациями:

• мы выбираем случайное значение массива при каждом запуске, что означает, что мы предполагаем, что каждый элемент будет выбран так же, как и любой другой
• мы тестируем для 100 и для 1000 элементов
• мы сравниваем целые и короткие строки.

https://run.perf.zone/view/for-vs-while-vs-indexof-100-integers-1516292563568

https://run.perf.zone/view/for-vs-while-vs-indexof-1000-integers-1516292665740

https://run.perf.zone/view/for-vs-while-vs-indexof-100-strings-1516297821385

https://run.perf.zone/view/for-vs-while-vs-indexof-1000-strings-1516293164213

Вот результаты на моей машине:

https://imgur.com/a/fBWD9

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

Так что здесь нет универсального ответа, и он наверняка изменится в будущем по мере изменения браузеров и оборудования.

Стоит ли вообще это тестировать?

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

Это не означает, что этот вопрос не имеет значения - это редко, но бывает может случиться, что производительность линейного поиска имеет значение;У меня получился пример этого: установление скорости построения / поиска с помощью префикса trie , построенного с помощью вложенных объектов (с помощью поиска по словарю) или вложенных массивов (требующих линейного поиска).

Как видно из этого комментария github , тесты включают в себя различные реалистичные и наилучшие / худшие варианты полезной нагрузки в различных браузерах и платформах.Только пройдя через все это, я делаю выводы об ожидаемой производительности.В моем случае для большинства реалистичных ситуаций линейный поиск по массиву выполняется быстрее, чем поиск по словарю, но производительность в худшем случае хуже, чем сценарий замораживания (и его легко построить), поэтому реализация была помечена как«небезопасный» метод, чтобы дать понять другим, что им следует подумать о контексте, в котором будет использоваться код.

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

Что делать, когда вам делать необходимо выполнить микро-тест

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

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

В другихслова: одинаково ли может быть найден какой-либо индекс (равномерное распределение) или он с большей вероятностью будет центрирован по центру (нормальное распределение)?Будут ли найдены наши данные в начале или в конце?Гарантируется ли наше значение в массиве, или только определенный процент времени?Какой процент?

Я ищу массив строк?Номера объектов?Если это числа, это числа с плавающей точкой или целые числа?Пытаемся ли мы оптимизировать под старые смартфоны, современные ноутбуки или настольные компьютеры со встроенным IE10?

Это еще одна важная вещь: не оптимизируйте для лучшей производительности, оптимизируйте для реалистичная производительность в худшем случае .Если вы создаете веб-приложение, в котором 10% ваших клиентов используют очень старые смартфоны, оптимизируйте его;их опыт будет невыносимым с плохой производительностью, в то время как микрооптимизация тратится впустую на флагманских телефонах новейшего поколения.

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

Answer 4

indexOf выполняет кучу проверок и проверок типов, которые игнорируют цикл for и while.

Вот алгоритм indexOf:

https://developer.mozilla.org/en/JavaScript/Reference/Global_Objects/Array/indexOf

Редактировать: Я предполагаю, что indexOf быстрее для больших массивов, потому что он кэширует длину массива перед циклом его прохождения.

Answer 5

Запустите тест еще раз с внесенными мною правками.

Я увеличил размер массива и увеличил индекс, который вы ищете.Кажется, в больших массивах indexOf может быть более быстрым выбором.

http://jsben.ch/#/xm2BV

РЕДАКТИРОВАТЬ: Основываясь на большем количестве тестов, кажется, что indexOf работает быстрее, чем цикл for в версииSafari я использую (5.0.3) и медленнее почти во всем остальном.

Answer 6

Мы можем доверять равнине для цикла каждый раз.

Я написал код ниже, чтобы найти ответ на этот вопрос. Это также работоспособный . Это показывает, что обычный for loop является лучшим решением при рассмотрении производительности .

(Код также можно найти на jsfiddle )

console.clear()

let a = []
// populating array data
for (let i = 0; i < 100000; i++) {
	a.push(i)
}

let testNum = 90000
let found
let totalMS4ForLoop = 0
let totalMS4IndexOf = 0
let start
let end
// simulating 10000 requests which are come consecutively
for (o = 0; o < 10000; o++) {

  start = Date.now()
  for (let i = 0; i < a.length; i++) {
    if (a[i] == testNum) { found = a[i]; break }
  }
  end = Date.now()
  totalMS4ForLoop += end - start

  start = Date.now()
  found = a[a.indexOf(testNum)]
  end = Date.now()
  totalMS4IndexOf += end - start

}

console.log("10000 for-loop executions took total " + totalMS4ForLoop + " ms.")
console.log("10000 indexOf executions took total " + totalMS4IndexOf + " ms.")

Answer 7

Возможно, стоит отметить, что если все, что вы пытаетесь сделать, это хранить список элементов и проверять наличие (например, избегать добавления дубликатов идентификаторов в массив), было бы гораздо быстрее сохранить ОБЪЕКТ с ключами, которые отражают каждый идентификатор. Если вы думаете, что я неправ, сравните следующее с массивом + indexOf. Мы говорим 181 мс для метода объекта против 1 МИНУТЫ для метода indexOf массива.

var objs = []
var i_uid = {} // method 1
var a_uid = [] // method 2
var total_count = 100000, idLen = 5
var ts, te, cObj = 0

// method 1
ts = new Date()
while (cObj < total_count) {
    var u = uid(idLen),
        o = {
            uid: u,
            text: 'something',
            created: new Date()
        }
    if (!i_uid[u]) { // ensure unique uids only
        objs.push(o)
        i_uid[u] = cObj // current array position as placeholder
        cObj++
    }
    else {
        console.log('unique violation [duplicate uid', u, ']')
    }
}
te = new Date()
console.log('loaded ' + total_count + ' with object method in', (te - ts), 'ms')

i_uid = {} // free-up
cObj = 0 // reset
objs = [] // reset

// method 2
ts = new Date()
while (cObj < total_count) {
    var u = uid(idLen),
        o = {
            uid: u,
            text: 'something',
            created: new Date()
        }
    if (a_uid.indexOf(u) == -1) { // ensure unique uids only
        objs.push(o)
        a_uid.push(u)
        cObj++
    }
    else {
        console.log('unique violation [duplicate uid', u, ']')
    }
}
te = new Date()
console.log('loaded ' + total_count + ' with array + indexOf method in', (te - ts), 'ms')

function uid(l) {
    var t = '',
        p = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789',
        pl = p.length
    for (var i = 0; i < l; i++)
        t += p.charAt(Math.floor(Math.random() * pl))
    return t
}