Не совсем правильное сравнение. Тут основное время занимает заполнение массива. Вот я почистил код. Каждый вариант запускается по три раза:

В результате у меня получися следующий вывод:

А если как-то так попробовать?



Это сообщение отредактировал(а) Dov - 1.7.2011, 00:10

Да это будет быстрее. 

Это сообщение отредактировал(а) voral - 1.7.2011, 00:38

Окей, практика показала увеличение производительности. А теперь теоретически это как-то можно объяснить? Я вот на прошлой странице пытался провести сравнение сложности алгоритмов "на бумажке" по количеству машинных операций, но, видимо, оно чего-то (многого) не учитывает.

Это сообщение отредактировал(а) newbieone - 1.7.2011, 09:47

Это о последнем алгоритме?
Там все просто. 
Сначала бежим по каждому элементу сторки, прибавляем его у сумме и сравниваем.
Как только нашли первый отрицательный элемент, нас уже не интересует есть ли еще отрицательные, по этому мы уходим в продолжение цикла где нет проверок на отрицательность, т.е. избавляемся от лишнй операции на каждую итерацию. (в предыдущем "быстром" варианте мы все равно проверяли флаг на равенство 1 или 0)

voral, я имел ввиду математическое пояснение в терминах теории сложности вычислений (сложности алгоритмов).

Вашего первоначального и того, что предложил borisbn.

Это сообщение отредактировал(а) newbieone - 1.7.2011, 10:26

а вы про этот пост где N расписывали 
Ну тогда както так:
В худшем случае (кагда нет отрицательных числ)
мы имеем N сравнений и ни одногоприсваивания
В лучшем случае когда первый элемент в строке отрицателен имеем 1 сравнени и так же ни одного присваивания.

Итак имеем от 1 до N (в зависимости от позиции отрицательного числа) операций против от N до 2N

Добавлено через 4 минуты и 35 секунд
А вообще. Если целью поставить быстродействие и если позволяет процедура заполнения матрицы. Добавить еще один одномерный массив. При вводе нового элемента матрицы анализировать существование отрицательного значения и заносить номер строки в массив. Хотя в этом случае (такой ввод) моно собственну и суму здесь же считать. Но это уже теряем гибкость.

voral, не могу с вами согласиться. У вас же там в условном операторе два условия через &&, сравнений соответственно будет в два раза больше, плюс вы забываете о сравнениях (о первом из них, второе из-за short-circuiting не будет вычисляться) уже после присваивания...
Если пытаться анализировать этим способом, имеем практически одинаковые результаты: N+2 до 2N против N+1 до 2N.

Если первый элемент отрицательней, проведется 2 сравнения, 1 присваивание, и после этого еще N-1 сравнений (т.к. fexists станет равным единице, то первое сравнение даст false и дальше выражение вычисляться не будет). В сумме N+1 сравнений и 1 присваивание, т.е. N+2 операций.
Если все положительные, то fexists всегда остается равным нулю и имеем 2N сравнений.

Здесь если существует единственный отрицательный элемент, N сравнений и 1 присваивание, т.е. N+1 операция.
Если все отрицательные, N сравнений и N присваиваний, т.е. 2N операций.

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

Это сообщение отредактировал(а) newbieone - 1.7.2011, 13:50

видимо мы о разном. Я разложил именно поселедний самый шустрый вариант.
Этот же случай 

я понимаю так. 
Самое плохое когда нет отрицательных
два сравнения, сложение энд т.е. 3N - операций 
Самое хорошее когда первое отрицательное
первая итерация  два сравнения, сложение энд и присваивание 4 операции
остальные итерации одно сравнение
т.е. (N-1)+4
Т.е получаем от N+3 до 3N  против N+1 до 2N, (кстати операция операции рознь и && совсем не одно и то же что сравнение)

К тому же. У нас диапазон чисел от -1 до 9. При размере матрицы 15000 шанс что в строке не будет отрицательных чисел очень мал. Т.е. скорее всего исходный случай с одним сравнением будет стремиться именно к 2N, В то время как где два сравнения врят ли дотянет до 3N...
Думаю если уменьшить размер, или увеличить диапазон чисел.... ТО может быть преимущество перейдет.

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

Хехе, ну вот, а говорили на предыдущей странице, что

Вот еще небольшой тестик

Результат:


Добавлено через 2 минуты и 54 секунды
При размере строки 11 все равно неплохой результат:

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

Тут я взял за основу код уважаемого voral, т.к. удобнее дописать функцию

вот основа:




Вот что я добавил: 





Значит функция maloc вроде бы написана без синтаксических ошибок, ибо компилятор не матерится. Однако как проверить правильно ли выделяется память я не знаю, поэтому прошу провеhить код функции maloc

Далее, то что код функции freememory должен находится не тут я понимаю (ибо выделил память и тут же аннулировал), но где она должна находиться? После main? прямо перед main? Будьте добры, подскажите.

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

Ты сделал свои обертки для malloc и free.  Желательно их вызывать (для одной области) в  рамках однной функции - в которой живет переменная хранящая адрес.

Однако, могут быть ситуации когда ты передаешь адрес в другую функцию/поток, а из той в которой создал уходишь... Тогда уже там надо позаботиться об освобождении.
Например

Переменная Result будет уничтожена. Но память останется выделенной.....

Т.е. мне надо вызвать функцию малок внутри каждой из моих двух функций или вызвать её в мейне перед выполнением двух других функций?

Добавлено @ 14:40
и получается освобождать память тоже не надо, т.к. нет глобальных переменных ?

Это сообщение отредактировал(а) Kruger2 - 11.7.2011, 14:40

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

Это сообщение отредактировал(а) Kruger2 - 11.7.2011, 14:53