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

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

dima писал(а):
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;
}

так сравнение должно быть только одно..

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

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

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

На PowerPC есть команда select. Она бы эту задачу сильно ускорила, но на Intel ее нету.

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

Какой код быстрее?

inline bool IsInRange( int value, int min, int max )
{
return value >= min && value <= max;
}

или

inline bool IsInRange( int value, int min, int max )
{
return (((int)(value >= min)) & ((int)(value <= max))) == 0;
}

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

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

С тривиальным, как Дима выше написал.

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

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

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

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

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

Да, без вопросов. Это работает.
Вопрос, как оптимизировать.

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

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

Это к чему я склоняюсь, но у меня нет в этом уверенности.

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

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

Перемножение против сравнения - действительно, вопрос.
Если большинство сравнений правильно предскажутся, то умножение проиграет. Если нет, то скорее всего, выиграет. От платформы, действительно зависит.

А вот битовые операции выиграют практически всегда. Если не брать совсем уж допотопных платформ.

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

sz писал(а):
ajkj3em писал(а):чтобы понять если ли ноль, надо что-то сделать с каждым
елементом (и может быть что-то еще дополнительно). вопрос состоит
в том будет ли вто что-то быстрее или медленнее операции
сравнения.
Любой набор битовых операци числом меньше 10 (а иногда и больше) быстрее сравнения. От процессора практически не зависит.

и явный loop из этих операций будет быстрее "rep scasb" ? не верю

Какой код быстрее?

зависит от компилятора

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

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

ajkj3em писал(а):и явный loop из этих операций будет быстрее "rep scasb" ? не верю

Нас, кажется, на Си просили написать?

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

ajkj3em писал(а):зависит от компилятора

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

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

Код: Выделить всё

bool func(const int* array, size_t size) {
	int tmp = size/2;
	int result = 1;
	for(; *(result)&*(reslult+1) && tmp; tmp--, result+=2);
	return (tmp*2==size) ? (tmp!=0) : (tmp!=0 || *(array+size)==0);
}

как то так - идея проверять парами сразу

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

sz писал(а):Если большинство сравнений правильно предскажутся, то умножение проиграет.

..и задача сведется к варианту №1, предложенному aissp в самом начале

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

sz писал(а):
ajkj3em писал(а):и явный loop из этих операций будет быстрее "rep scasb" ? не верю
Нас, кажется, на Си просили написать?

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

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

ajkj3em писал(а):ну так, нас просили оптимизировать что-то под абстрактную платформу.

Но сейчас нет платформ на которых замена if-ов xor-ами не давала бы улучшения. А платформ на которых нету rep scasb - сколько угодно.

Кстати говоря, на xbox360 MemSet128 дерет по производительности аналогичную ассемблерную команду, как сидорову козу. Но там, конечно, действительно, оптимизация сильно заточенная под архитектуру. Я просто привожу, как пример того, что rep scasb - тоже не панацея.

ajkj3em писал(а):чисто алгоритмической оптимизации здесь нет, так что задача либо
не имеет решения, либо она не полностью определена. оптимизировать
xor'ами в таком контексте смысла нет.

А вопрос был и не на алгоритмическую оптимизацию. А на знание основных техник оптимизации. Совсем неплохой вопрос, кстати сказать. Когда тебе интервьюируемый на него начинает вопрошать "нафига", сразу ясно, что на низком уровне оптимизацией никогда не занимался. То есть, вопрос идеальный для интервью - сразу дает точный ответ, кто перед тобой.

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

а если умножать каждый член на минус единицу и проверять изменился ли знак?