Перебор массива циклом или сверка значений проверкой?

Question

[Urukhayy]

Что будет быстрей и оптимальней?

for(new i; i != 100; i++)
{
if(Array[i] == variable) break; 
}

vs

if(1232 == variable || 2232 == variable || 
1532 == variable || 1432 == variable || 
1262 == variable || 12332 == variable || ...) // и так множество значений, которые даны в массиве Array

Comments

[h8nor]

lurkmore.to/_/1806#mws_upT1Sjm

Answer 1

[Сергей Протько]

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

Вообще как, для большинства языков, в том числе для интерпритируемых, развертка цикла дает прирост производительности. За счет чего происходит ускорение? А за счет того что все эти инструкции внутри цикла независимы друг от друга, у нас нет конфликтов по записи (и не может быть) и посему процессор спокойно так паралелит выполнение инструкций. Это удобно когда надо посчитать какой-нибудь длинный массив (например добавить на картинку яркости).

Пример. Возьмем массив на 1 000 000 чисел, и попробуем сделать его копию, с увеличенным в два раза значением:

var data = range(1000000);
var result = range(1000000);
// обычный вариант
for(var i = 0;i<1000000;i++) {
    result[i] = data[i] * 2;
}

// развертка цикла
for(var i = 0;i<1000000;i+=4) {
    result[i] = data[i] * 2;
    result[i+1] = data[i+1] * 2;
    result[i+2] = data[i+2] * 2;
    result[i+3] = data[i+3] * 2;
}

jsperf.com/loop-unroll-simple

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

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

Answer 2

[olexandr7]

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

Answer 3

[Mrrl]

На С++ прямая проверка работает примерно вдвое быстрее, чем проверка циклом. Я проверял для массива из 10 элементов (проверял, входит ли число в первые 10 простых чисел). С циклом проблема ещё и в том, что для такого "if" трудно написать else-часть - нужно либо добавлять лишнюю логическую переменную, либо использовать goto.