Каморка

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

Есть два способа

(1) обратиться к sz он конечно ето не сделает, но (ежели предскажет пральный бранч) с вероятностью 1/2 получит правильный ответ перебрав только половину членов.

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

ЗЫ правдивый ответ никак

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

К примеру если сравнивать побитовое умножение (&=) всех членов?

tiasur писал(а):У меня есть мысль перемножить все члены

и как вто сделать без перебора ?

и как вто сделать без перебора ?

Я ошибся. В задаче - сделать только одно сравнение.

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

правильно ли я понимайт задачу?

Задача типа: написать функцию

bool func(int* qq, size_t size);

которая возвращает true если в массиве qq отсуствуют 0 и false в противном случае. При етом в теле функции отсуствуют какие либо циклы и какие либо другие виды перебора?

Вообще-то, это тоже перебор элементов в неком роде

. И даже больше, такой способ заведомо ВСЕ элементы массива перебирает. Простое сравнение может закончиться на первом элементе, если он 0, а Ваш способ с одним сравнением в конце обязан до конца массива умножать.
Быстрее, чем перебор, боюсь, не получится (если найдёте метод - поделитесь, пожалуйста)...
Одно сравнение - sort по модулю по возрастающей и проверить первый элемент (хотя не явно здесь сравнение тоже есть)...
Но можно вообще без сравнения

:

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

 __try
  {
   for( int  i = 0; i < SizeOfArray; i++ )
    {
     int res = 1 / Array[ i ];
    }
  }
__except( 1 ) // compiler-specific statement to catch SE / EXCEPTION_EXECUTE_HANDLER == 1 on Windows
 {
   cout << "Gotcha, sucker..." << endl;
 }

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

Azazello писал(а):Но можно вообще без сравнения ;):

это пять :) чем-то напоминает вот это -

http://www.mailcom.com/TemplatedSQRT.html

Azazello писал(а):Вообще-то, это тоже перебор элементов в неком роде . И даже больше, такой способ заведомо ВСЕ элементы массива перебирает. Простое сравнение может закончиться на первом элементе, если он 0, а Ваш способ с одним сравнением в конце обязан до конца массива умножать.
Быстрее, чем перебор, боюсь, не получится (если найдёте метод - поделитесь, пожалуйста)...
Одно сравнение - sort по модулю по возрастающей и проверить первый элемент (хотя не явно здесь сравнение тоже есть)...
Но можно вообще без сравнения :
Код: Выделить всё
 __try
  {
   for( int  i = 0; i < SizeOfArray; i++ )
    {
     int res = 1 / Array[ i ];
    }
  }
__except( 1 ) // compiler-specific statement to catch SE / EXCEPTION_EXECUTE_HANDLER == 1 on Windows
 {
   cout << "Gotcha, sucker..." << endl;
 }

Сомневаюсь что Ваше решение оптимизированное vs. с перебором и сравнением каждого члена с 0.

tiasur писал(а):Преадлагается оптимизировать решение с перебором. На перебор ограничений не вводится. А вот сравнений должно быть только одно. Также упоминается что наличие 0 в массиве маловероятно.

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

просто если там int, то написать что либо быстрее

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

rep scasb/scasw/scasd

в терминах интелловского ассемблера вряд ли получитcя, а
вто собственно memchr & co. из стандартной библиотеки

tiasur писал(а):предлагается оптимизировать задачу до единственного сравнения. У меня есть мысль перемножить все члены, а потом сравнить их с нулём, но я дико сомневаюсь, что это будет более оптимизированный код?

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

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

Каморка

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

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