Массив с нулём

aissp · Сообщение **aissp** » 23 мар 2007, 11:03

size is even

bool func(int* qq, size_t size) {
unsigned int i=0;
for(; (qq+i) & (qq+i+1) ; i+=2);
}

если программа бросает корку в массиве нулей нет

tiasur · Сообщение **tiasur** » 23 мар 2007, 11:04

папа Карло писал(а):
как вариант, создай класс SmartArray который имеет одно дополнительное проперти есть ли в массиве 0. тогда читать будет быстро, но "перебор" будет на этапе вставки. эсли это допустимо, то все пучком.

Перебор и сравнение переносится в класс? Тогда это не решение и не оптимизация.

папа Карло

tiasur писал(а):
папа Карло писал(а):
как вариант, создай класс SmartArray который имеет одно дополнительное проперти есть ли в массиве 0. тогда читать будет быстро, но "перебор" будет на этапе вставки. эсли это допустимо, то все пучком.
Перебор и сравнение переносится в класс? Тогда это не решение и не оптимизация.

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

если при чтении то без перебора не обойдешься как не крути. как в сказке: и рыбку съесть и на.... сесть

tiasur · Сообщение **tiasur** » 23 мар 2007, 11:06

ajkj3em писал(а):
просто если там int, то написать что либо быстрее
Код: Выделить всё
rep scasb/scasw/scasd 
в терминах интелловского ассемблера вряд ли получитcя, а
вто собственно memchr & co. из стандартной библиотеки

Поцессор может быть другим.

dima · Сообщение **dima** » 23 мар 2007, 11:14

tiasur писал(а):Как проверить массив на наличие там нуля не перебирая его члены?

никак - надо перебирать.

tiasur · Сообщение **tiasur** » 23 мар 2007, 11:24

никак - надо перебирать.

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

ajkj3em · Сообщение **ajkj3em** » 23 мар 2007, 11:33

tiasur писал(а):
ajkj3em писал(а):
просто если там int, то написать что либо быстрее
Код: Выделить всё
rep scasb/scasw/scasd 
в терминах интелловского ассемблера вряд ли получитcя, а
вто собственно memchr & co. из стандартной библиотеки
Поцессор может быть другим.

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

чтобы понять если ли ноль, надо что-то сделать с каждым
елементом (и может быть что-то еще дополнительно). вопрос состоит
в том будет ли вто что-то быстрее или медленнее операции
сравнения.

твои пример с &&= прекрасное тому подтверждение - в зависимости
от платформы операция приведения int'a к 0 или 1 может быть
имплементирована сильно по-разному, и в результате такой метод
может оказаться как быстрее так и медленнее тривиального.

ajkj3em · Сообщение **ajkj3em** » 23 мар 2007, 11:34

tiasur писал(а):
никак - надо перебирать.
Когда ставится вопрос, то подразумевается, что решение существует.

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

* перевод с транслита

папа Карло

tiasur писал(а):
никак - надо перебирать.
Когда ставится вопрос, то подразумевается, что решение существует.
Да и переберать можно, но сравнение должно быть одно, и полученный вариан должен быть оптимизированный по отношению к тривиальному.

я подразумеваю что ты подразумеваешь не верно.

можешь объяснить почему ты считаешь, что существует решение которое не поребирает массив и делает это за одно сравнение (итерацию)? можешь поделиться дополнительной информацией которая заставляет тебя так думать?

ajkj3em · Сообщение **ajkj3em** » 23 мар 2007, 11:37

папа Карло писал(а):.. решение которое не поребирает массив

перебирать можно http://forum.kamorka.com/viewtopic.php?p=147557#147557

sz · Сообщение sz » 23 мар 2007, 11:40

Ну, например, вот так:

bool HasZeroes( const unsigned* array, unsigned size )
{
unsigned result = 1;
for( ; size != 0; --size,++array ) result &= *array-1^*array;
return result == 0;
}

Компилировать и запускать не пытался, так что больно не драться, если что. Просто демонстрирует идею.

папа Карло

ajkj3em писал(а):
папа Карло писал(а):.. решение которое не поребирает массив
перебирать можно http://forum.kamorka.com/viewtopic.php?p=147557#147557

хмм.... ок.

тогда встает вопрос об оптимизации под определенный процессор я так понимаю....

tiasur · Сообщение **tiasur** » 23 мар 2007, 11:46

ajkj3em, если задачу предлагают решить на С, то не стоит вникать в тип процессора и особенностей его асемблера.

папа Карло, я уже признал свою ошибку в формулировки задачи. Правильно так:

Определить есть ли ноль в массиве не сравнивая каждый член этого массива с нулем. Можно использовать другие математические операции. Сравнение с нулём может быть произведено только один раз. Код должен получиться в результате оптимизированным. Язык С.

Аман Ванкуверский

tiasur писал(а): Определить есть ли ноль в массиве не сравнивая каждый член этого массива с нулем. Можно использовать другие математические операции. Сравнение с нулём может быть произведено только один раз. Код должен получиться в результате оптимизированным. Язык С.

Оптимизированным по сравнению с каким алгоритмом?

dima · Сообщение **dima** » 23 мар 2007, 11:50

sz писал(а):Ну, например, вот так:

bool HasZeroes( const unsigned* array, unsigned size )
{
unsigned result = 1;
for( ; size != 0; --size,++array ) result &= *array-1^*array;
return result == 0;
}

Компилировать и запускать не пытался, так что больно не драться, если что. Просто демонстрирует идею.

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

bool HasZeroes( const unsigned* array, unsigned size )
{
for( ; size != 0; size--,array++ )
{
if(*array == 0)
return true
}
return false;
}

Каморка

Массив с нулём

Re: Массив с нулём