[C++] Быстрая проверка области памяти на предмет равенства значению. (2 стр)

заводим переменную - _количество_ нулевых значений в массиве.
потом, смотря что на что меняем в массиве - делаем +1 или -1 к этой переменной

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

и никаких ассемблеров и sse...

150 мегов за 0.3 секунды в дебаге прогоняет с циклом как в первом посте. Быстрее _некуда_.

Altmer
> А вообще непонятно зачем подобное вообще понадобилось
Есть большой массив элементов, для каждого есть флаг "Готовность". Нужно определить готовность всех элементов.

(У меня задача про динам. загрузку ландшафта)

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

igo
Это я и хотел узнать - что компилер оптимизирует такие циклы.

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

-Eugene-
Была у меня похожая задача, но я решал ее за счет LODов в квадро дереве, если узел нужной детализации не подгрузился - я просто брал вышестоящий узел.  За загрузку отвечал фоновый поток. И ничего массово проверять не надо было, все делалось во время обхода дерева. Если детализация твоего ландшафта фиксированная и ты используеш для прикрытия недогруженных частей туман войны или что-то аналогичное, то тут я бы посоветовал вместо флага готовности использовать кольцо куда твой загрузчик будет скидывать индексы готовых тайлов, и соответственно кольцо для постановки тайлов в очередь загрузки. Если я конечно правильно понял, а так - думаю тебе не стоит заморачиваться, вот если тормоза будут - тогда бери профайлер и смотри что у тебя малину портит, а затем уже оптимизируй )

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

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

Алгоритм основывается на построении дерева, в прекомпьюте в узлах которого за линейную сложность строятся суммы для всех отрезков. Не то разностное дерево, не то дерево Фенвика - надеюсь, кто-нибудь из местных олимпиадников подскажет.

Altmer
> CX <= 100500

То есть 34964?

о, нашёл: http://ru.wikipedia.org/wiki/Дерево_Фенвика
читать дерефо фенвика для максимума. разумеется, русская статья ужасна, лучше читать в кормене.

Suslik
Хм... Это прогоняется в каждом рендере, поэтому я хотел знать, оптимизируется ли он компилером. Потому что если нет - ФПС буит покоцано.

Набросал код в Visual Studio с разными вариантами только для случая когда мы ищем 1 среди 0, массив int 1Гб(?) выровнен по границе 16 байт, единица в конце.)
Результаты разнятся от запуска к запуску (не #0 #1 и т.д. а всей программы).

while #0: 277 ms, b: 0, i: 262144000
while #1: 280 ms, b: 0, i: 262144000
while #2: 279 ms, b: 0, i: 262144000
while #3: 280 ms, b: 0, i: 262144000
while #4: 285 ms, b: 0, i: 262144000

for #0: 316 ms, b: 0, i: 262143999
for #1: 316 ms, b: 0, i: 262143999
for #2: 317 ms, b: 0, i: 262143999
for #3: 322 ms, b: 0, i: 262143999
for #4: 319 ms, b: 0, i: 262143999

for OR #0: 255 ms, b: 0, i: 262144000
for OR #1: 255 ms, b: 0, i: 262144000
for OR #2: 253 ms, b: 0, i: 262144000
for OR #3: 254 ms, b: 0, i: 262144000
for OR #4: 255 ms, b: 0, i: 262144000

sse #0: 164 ms, b: 0, i: 65536000
sse #1: 165 ms, b: 0, i: 65536000
sse #2: 166 ms, b: 0, i: 65536000
sse #3: 163 ms, b: 0, i: 65536000
sse #4: 166 ms, b: 0, i: 65536000

ни на что не претендующий код: http://pastebin.com/w0hR7NBx

6 гигов в секунду на SSE. Видимо, целиком шину памяти выжирает.

Кстати, очень хорошо видно, что если 250 миллионов чисел обрабатывается за 250 ms самым быстрым скалярным кодом, то мы получаем 1 миллиард операций OR в секунду. Частота проца всяко больше гигагерца. Так что проблема, очевидно, в латентностях или в неправильно выбранном типе для b.

Вот такой скалярный код:

    int b0 = 0;
    int b1 = 0;
    int b2 = 0;
    int b3 = 0;

    int i = 0;
    for(; i < SIZE; i += 4) {
      b0 |= mas[i + 0];
      b1 |= mas[i + 1]; 
      b2 |= mas[i + 2];
      b3 |= mas[i + 3];

    }

должен выжрать всю шину памяти, как и SSE. Но это не потому, что SSE плохое расширение. А потому что шина узкая.

Так что оптимизять ясно как - надо понижать битность данных. Если можно не int а char - круто. Если можно одни битики хранить - еще круче.

IronPeter, действительно, смена bool на int в варианте с for без сравнения дает аналогичный результат, видимо оптимизируется компилятором.
т.е.

    int b = 0;
    int i = 0;
    for(; i < SIZE; i++) {
      b |= mas[i];
    }

аналогичен

    int b = 0;
    int i = 0;
    for(; i < SIZE; i += 4) {
      b |= mas[i + 0];
      b |= mas[i + 1]; 
      b |= mas[i + 2];
      b |= mas[i + 3];
    }

в обоих случаях получается ~200мс

for x4 #0: 202 ms, b: 0, i: 262144000
for x4 #1: 201 ms, b: 0, i: 262144000
for x4 #2: 202 ms, b: 0, i: 262144000
for x4 #3: 203 ms, b: 0, i: 262144000
for x4 #4: 203 ms, b: 0, i: 262144000

с вашим выводом согласен.)

*у меня как раз память DDR2 800, у которой согласно вики пиковая скорость передачи данных 6,4 ГБ/с