powered by simpleCommunicator - 2.0.59     © 2025 Programmizd 02
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Форумы / C++ [игнор отключен] [закрыт для гостей] / Оценка времени выполнения аналогичных циклов.
22 сообщений из 22, страница 1 из 1
Оценка времени выполнения аналогичных циклов.
    #38713570
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Здравствуйте.
Допустим у нас есть два цикла:
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < n; ++j)
		{
			smth do //блок выполняется t единиц времени
		}
	}




и

Код: plaintext
1.
2.
3.
4.
	for (int i = 1; i <= (n - 1)*(n - 1); ++i)
	{
		smth do //блок выполняется t+t1 единиц времени, где t1 время затраченное на переход к (i,j)
	}



Подскажите пожалуйста, какое примерно отношение по времени между T1(время выполнения первого кода) и T2(время выполнения второго кода) ? Мне показалось что T1/T2 не стремится к 0. Или ошибаюсь ?
Хотя как я понимаю стандарт это не регламентирует, и это может зависеть только от компилятора, и среды выполнения
...
Рейтинг: 0 / 0
Оценка времени выполнения аналогичных циклов.
    #38713573
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SashaMercury,

1) Эти два кода имеют разное число итераций
Проверьте для n=1

2) Если даже переписать второй код правильно, то я уверен что второй код медленнее на порядок, т.к. для вычисления пары координат из линейного индекса потребуется деление, которое не такое уж быстрое.
Конечно при малых n теоретически может быть замедление первого кода из-за чуть более частых условных переходов.
Но обычно про скорость заботятся при больших n :)

Во всяком случае, если уж устранять условные переходы, то лучше разворачивать внутренний цикл с шагом в несколько итераций.
Схематически:
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < n; j += 4)
		{
 			// добавить обработку n некратных 4 (гуглить duff's device)
			do_somthing(i, j + 0);
			do_somthing(i, j + 1);
			do_somthing(i, j + 2);
			do_somthing(i, j + 3);
		}
	}
...
Рейтинг: 0 / 0
Оценка времени выполнения аналогичных циклов.
    #38713574
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Anatoly Moskovsky1) Эти два кода имеют разное число итераций
Проверьте для n=1

Вы правы. Я прошу прощение, должно быть так.
Код: plaintext
1.
2.
3.
4.
5.
	for (int i = 1; i <= n*n; ++i)
	{
		smth do //блок выполняется t+t1 единиц времени, где t1 время затраченное на переход к (i,j)

	}



Сегодня я подумаю о том, что вы написали ниже.

А если мой вопрос касается считывания квадратной матрицы из файла размерности 1000 на 1000 например, читаю я каждый элемент
Код: plaintext
1.
fscanf(in,"%i",&t);



То быстрее будет одномерный цикл по i от 0 до 10^6 -1 ? Ведь в данном случае мне не важен индекс, и я не трачу время t1. Использую каждое значение один раз, и не храню всю матрицу в памяти программы.
...
Рейтинг: 0 / 0
Оценка времени выполнения аналогичных циклов.
    #38713580
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SashaMercuryВы правы. Я прошу прощение, должно быть так.
Код: plaintext
1.
	for (int i = 1; i <= n*n; ++i)


Зачем вам эта 1.
Циклы базирующиеся на 1, так же как и закрытые интервалы - источник багов.
Пишите как и в первом коде - начиная с 0 и с полуоткрытым интервалом.
Код: plaintext
1.
for (int i = 0; i < n*n; ++i)



SashaMercuryА если мой вопрос касается считывания квадратной матрицы из файла размерности 1000 на 1000 например, читаю я каждый элемент
Код: plaintext
1.
fscanf(in,"%i",&t);




То быстрее будет одномерный цикл по i от 0 до 10^6 -1 ? Ведь в данном случае мне не важен индекс, и я не трачу время t1. Использую каждое значение один раз, и не храню всю матрицу в памяти программы.
Забейте, ввод/вывод на порядки медленнее любых циклов, делений и прочего. Никакой практической разницы в скорости не будет. Зато код усложнится.
...
Рейтинг: 0 / 0
Оценка времени выполнения аналогичных циклов.
    #38713582
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Anatoly Moskovsky Зачем вам эта 1.
Циклы базирующиеся на 1, так же как и закрытые интервалы - источник багов.
Пишите как и в первом коде - начиная с 0 и с полуоткрытым интервалом.

Больше так делать не буду(если без этого можно будет обойтись), понял на своём примере про "источник багов".



Спасибо что поправили меня. Сам я не сделал вывод на то, что сделал ошибку во многом из-за того что решил начать цикл с 1, и просто её исправил.
...
Рейтинг: 0 / 0
Оценка времени выполнения аналогичных циклов.
    #38713892
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SashaMercury,

Вообще, ты не там золото ищешь.
...
Рейтинг: 0 / 0
Оценка времени выполнения аналогичных циклов.
    #38713915
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SashaMercury,

Саш. Вот мне как-бы всё время хочеться тебе cказать - "не парься". . Потому
как ощущение непрерывной паровой бани у тебя не проходит

Кейс №2 используют для обхода элементов матрицы указателем когда она задана
"плоским" (plain) массивом. К примеру.

В остальных случаях развёртывание цикла ничего кроме головной боли и ошибок
тебе не даст.

Алгоритм №1 первичен и концептуален. Алгоритм №2 это некая переработка
причём не очень нужная.
...
Рейтинг: 0 / 0
Оценка времени выполнения аналогичных циклов.
    #38714319
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
MasterZiv, mayton

дело в том, что я не хочу ничего упустить. Мне нравится понимать как всё это работает, мне жутко приятно смотреть на недавний пример функции strcpy и понимать для чего нужны в её прототипе все квалификаторы, писать код, и понимать почему я делаю так, а не по другому, мне очень нравится разбираться в чужом коде, искать ошибки, или ещё больше смотреть на красивый код, или какие-нибудь элементы fe
Код: plaintext
1.
if(a-b)


и понимать, что это очень красиво, потому что полностью используется оператор if, и не нужно писать if((a-b)!=0).

Потому, когда я программирую, всегда думаю как это сделать лучше, как это сделать красивее, как это сделать правильно. И у меня часто возникают сомнения. И вот почему-то возникла такая мысль(почему-то двойной цикл, как мне показалось, был слишком медленный), и я решил спросить. Конечно, вопрос наверное простой и может напоминать какой-нибудь вброс, но это не так, просто не хочу упустить ничего.

Кстати, месяца два назад, я решал численно ДУ, в Maple, и там мне потребовалось развернуть n^2xn^2 массив в одномерный(left_nnnn), без этого не получилось бы никак:
Код: maple
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
left:=Matrix(1..n^2,1..n^2):#левая частьright:=Matrix(1..n^2,1..1):  #правая часть
> result_prev:=Matrix(1..n^2,1..1):#результат на предыдущем шаге
> result:=Matrix(1..n^2,1..1):#результат на последнем шаге
> #матрицы перехода
> left_nnnn:=Matrix(1..n^4,1..1):#левая часть 
> result_prev_nn:=Matrix(1..n,1..n):#результат на предыдущем шаге
> result_nn:=Matrix(1..n,1..n):#результат на последнем шаге

.....

#left
> #вектор перехода
> for m from 1 to n do
> for l from 1 to n do
> for i from 1 to n do
> for j from 1 to n do
> left_nnnn[(n*(i-1)+j)+n^2*((n*(m-1)+l)-1),1]:=evalf(left_f(i,j,m,l,(s-1)*tau)):
> end do; end do; end do; end do;
> 
> for i from 1 to n^2 do
> for j from 1 to n^2 do
> left[i,j]:=left_nnnn[n^2*(i-1)+j,1]:
> end do; end do;




Спасибо всем за советы :) Я сделал выводы.
Меня гонят (
...
Рейтинг: 0 / 0
Оценка времени выполнения аналогичных циклов.
    #38714350
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SashaMercury, вобщем кури теорию Алгоритмов. Книжек по сабжу много.
А на развертывании циклов ты ничего не выгадаешь. Хуже - будешь
крепко бит коллегами по проекту если они увидят "результат" твоих
оптимизаций.

P.S. Да гоним :)
...
Рейтинг: 0 / 0
Оценка времени выполнения аналогичных циклов.
    #38714362
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SashaMercury
Код: plaintext
1.
if(a-b)


и понимать, что это очень красиво, потому что полностью используется оператор if, и не нужно писать if((a-b)!=0).
читабельнее
Код: plaintext
1.
if(a != b)
...
Рейтинг: 0 / 0
Оценка времени выполнения аналогичных циклов.
    #39010931
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Здравствуйте.
Сегодня читал статью(p.5) , согласно которой прямой цикл будет медленнее обратного. Написал такой пример, получается ровно наоборот(программа вычисляет натуральный логарифм как сумму гармонического ряда без постоянной Эйлера-Маскерони). Я что-то не так понял в той работе, или пример неудачный ?



Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
#include <stdio.h>
#include <ctime> 

#define EULER_MASCHERONI_CONSTANT 0.577215664901532
#define NUMBER 1000000000
#define COUNT 10

//reverse cycle
long double ln___reverse(long long n){
	long double res = 0.0;
	for (int i = n; i!=0; i--){
		res += (1 / (long double)(i));
	}
	return res-EULER_MASCHERONI_CONSTANT;
}

//direct cycle
long double ln___direct(long long n){
	long double res = 0.0;
	for (int i = 1; i<=n+1;++i){
		res += (1 / (long double)(i));
	}
	return res - EULER_MASCHERONI_CONSTANT;
}


unsigned test_time(long long number, int count, long double(*ln)(long long))
{
	unsigned time_s = clock();
	for (int i = 0; i < COUNT; ++i){
		ln(number + i);
	}
	unsigned time_e = clock();
	return time_e - time_s;
}



int main()
{
	unsigned t1 = test_time(NUMBER, COUNT, ln___reverse);
	unsigned t2 = test_time(NUMBER, COUNT, ln___direct);
	printf("reverce time=%u\ndirect time=%u\n", t1,t2);
	return 0;
}
...
Рейтинг: 0 / 0
Оценка времени выполнения аналогичных циклов.
    #39011011
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
На ноль проверка быстрее идёт.
...
Рейтинг: 0 / 0
Оценка времени выполнения аналогичных циклов.
    #39011023
m_Sla
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SashaMercuryЗдравствуйте.
Сегодня читал статью(p.5) , согласно которой прямой цикл будет медленнее обратного. Написал такой пример, получается ровно наоборот(программа вычисляет натуральный логарифм как сумму гармонического ряда без постоянной Эйлера-Маскерони). Я что-то не так понял в той работе, или пример неудачный ?
...на разных платформах, на разных компиляторах результат может быть сильно разный
имхо пиши как можно понятнее, а оптимизацию, если будет нужно, делай в самый последний момент

Ален И. Голуб "Правила программирования на Си и Си++":

21.1. Эффективность — часто просто пугало
Я потратил несколько часов, делая одну подпрограмму более "эффективной", и не останавливался, чтобы подумать о том, как часто эта подпрограмма будет вызываться, что является пустой потерей времени в том случае, когда программа вызывается лишь один или два раза. Ваша программа должна быть непременно настолько эффективной, насколько это возможно, но вашей первоочередной заботой является сопровождение, и вы не должны приносить читаемость в жертву на алтарь эффективности. Напишите программу сперва с учетом сопровождения, затем запустите свою программу под профайлером и определите, где на самом деле есть узкие места. Будучи вооружены реальной информацией, вы теперь знаете, где стоит обменять часть читаемости на скорость, и можете вернуться и сделать это изменение. Тем не менее, вы можете включить первоначальный текст в комментарий, чтобы не потерять его. Всегда имейте в виду, что любое количество подчисток на уровне текста программы не повысит эффективность так, как это сделает лучший алгоритм. Пузырьковая сортировка будет выполняться медленно вне зависимости от того, насколько хорошо она запрограммирована
...
Рейтинг: 0 / 0
Оценка времени выполнения аналогичных циклов.
    #39011106
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
На сайтах intel и AMD в разделах разработки есть хорошие рекомендательные
документы по оптимизации разработки для этих архитектур. С учотом новых
систем комад процессора, кешей e.t.c. Но оптимизация for для проверки на ноль
можеть дать и внезапно обратный эффект если мы читаем память в "обратном"
порядке. Об этом надо помнить.

Кажется я уже где-то приводил одну из этих ссылок.
...
Рейтинг: 0 / 0
Оценка времени выполнения аналогичных циклов.
    #39011823
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Спасибо :)
...
Рейтинг: 0 / 0
Оценка времени выполнения аналогичных циклов.
    #39011939
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SashaMercury,

Ты прочитай про O() (большое О, big O), например, у (Кормен, Лейзерсон, Ривест, Штайн)-а "Алгоритмы, построение и анализ" -- там это одна глава небольшая -- всё сразу станет ясно.

Твой пример в принципе всегда работает с одинаковой сложностью , потому что число повторений smth_do одинаковое.
...
Рейтинг: 0 / 0
Оценка времени выполнения аналогичных циклов.
    #39012877
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
MasterZivSashaMercury,

Ты прочитай про O() (большое О, big O), например, у (Кормен, Лейзерсон, Ривест, Штайн)-а "Алгоритмы, построение и анализ" -- там это одна глава небольшая -- всё сразу станет ясно.

Твой пример в принципе всегда работает с одинаковой сложностью , потому что число повторений smth_do одинаковое.

Что такое асимптотическая сложность алгоритмов мне читать нет необходимости. Я исследовал эти циклы в контексте комментариев из статьи приведенной выше. Тут я начинал тему и этот пример больше относится к ней, вероятно, но её больше нет в Сообществе.
...
Рейтинг: 0 / 0
Оценка времени выполнения аналогичных циклов.
    #39012894
White Owl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Саша, ты не там золото ищешь.

Все твои вопросы в этом топике это сравнение нескольких пустынь: "а вот тут на одну песчинку больше, как же так?!".
В первом посте топика ты привел два кода, Анатолий над ними посмеялся. С одной стороны правильно. Но с другой, его хихиканье отвлекло внимание от главного вопроса: какое примерно отношение по времени между T1 и T2? Ответ: T1=T2. Потому что оба кода это . Все. Это финальный ответ.
При этом совершенно не важно если в одном случае это будет а в другом .
И человек которому нет необходимости читать что такое асимптотическая сложность алгоритмов будет понимать о чем я говорю :)


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


И Саша, я тебе очень сильно советую забыть на время про Си и С++. Возьмись за другие языки. За совсем другие. И не за строго математические типа Хаскела и иже с ним, а что-нибудь приземленное: Basic, SQL, bat, javascript. Саша, поверь: тебе это нужно! Да, Си это великий язык и мать сотен других, но знать только одну вершину - это очень узколобо.
...
Рейтинг: 0 / 0
Оценка времени выполнения аналогичных циклов.
    #39012904
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Спасибо за советы и наставления C:
Но я ещё слабо знаю Си. Как только напишу то что задумал, изучу что-нибудь ещё. Хотя больше мне ничего не нравится (из того что знаю кроме языка Си). Вот только ассемблер нужно изучить, я понимаю. Но пока трачу большую часть времени на математику, научным постоянно что-то не нравится :(
...
Рейтинг: 0 / 0
Оценка времени выполнения аналогичных циклов.
    #39012905
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Если в каждой из пустынь каждая песчинка будет весить на 10% меньше чем в другой, то число песчинок останется одинаковым, но вес каждой сильно повлияет на итоговый вес пустыни. Но сравнение на 0 в теле цикла не дало ожидаемого эффекта. Я пытаюсь найти контрпример к модели RAM, он наверняка должен быть
...
Рейтинг: 0 / 0
Оценка времени выполнения аналогичных циклов.
    #39013271
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Вещественное деление скушало эффект. Хотя.. надо ассемблерный код смотреть. Сравнение с нулём
даёт эффект на очень уж триваильных штуках типа измерения длины ASCIIZ-строки. На численном
методе получился пшик.
...
Рейтинг: 0 / 0
Оценка времени выполнения аналогичных циклов.
    #39013478
White Owl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SashaMercuryЕсли в каждой из пустынь каждая песчинка будет весить на 10% меньше чем в другой, то число песчинок останется одинаковым, но вес каждой сильно повлияет на итоговый вес пустыни. Но сравнение на 0 в теле цикла не дало ожидаемого эффекта. Я пытаюсь найти контрпример к модели RAM, он наверняка должен бытьЕсли бы да кабы...
В данных пустынях, все песчинки весят константные значения. Никаких прогрессий тут нет. Поэтому и выгадывать каждую - не эффективно.
Саша, я тебя очень прошу: забудь математику, забудь Си. Поработай с другими языками. Пока ты этого не сделаешь - у тебя не будет роста в Си.
...
Рейтинг: 0 / 0
22 сообщений из 22, страница 1 из 1
Форумы / C++ [игнор отключен] [закрыт для гостей] / Оценка времени выполнения аналогичных циклов.
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]