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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

bool func(int* qq, size_t size);

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

Azazello · Сообщение **Azazello** » 23 мар 2007, 10:47

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

. И даже больше, такой способ заведомо ВСЕ элементы массива перебирает. Простое сравнение может закончиться на первом элементе, если он 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;
 }

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

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

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

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

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

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

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

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.

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

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

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

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

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

rep scasb/scasw/scasd

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

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

папа Карло

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

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

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