Гость
Целевая тема:
Создать новую тему:
Автор:
Форумы / C++ [игнор отключен] [закрыт для гостей] / Оценка времени выполнения аналогичных циклов. / 22 сообщений из 22, страница 1 из 1
06.08.2014, 02:46
    #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
06.08.2014, 03:44
    #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
06.08.2014, 04:00
    #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
06.08.2014, 04:23
    #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
06.08.2014, 04:42
    #38713582
SashaMercury
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Оценка времени выполнения аналогичных циклов.
Anatoly Moskovsky Зачем вам эта 1.
Циклы базирующиеся на 1, так же как и закрытые интервалы - источник багов.
Пишите как и в первом коде - начиная с 0 и с полуоткрытым интервалом.

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



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

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

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

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

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

Алгоритм №1 первичен и концептуален. Алгоритм №2 это некая переработка
причём не очень нужная.
...
Рейтинг: 0 / 0
06.08.2014, 16:18
    #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
06.08.2014, 16:32
    #38714350
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Оценка времени выполнения аналогичных циклов.
SashaMercury, вобщем кури теорию Алгоритмов. Книжек по сабжу много.
А на развертывании циклов ты ничего не выгадаешь. Хуже - будешь
крепко бит коллегами по проекту если они увидят "результат" твоих
оптимизаций.

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


и понимать, что это очень красиво, потому что полностью используется оператор if, и не нужно писать if((a-b)!=0).
читабельнее
Код: plaintext
1.
if(a != b)
...
Рейтинг: 0 / 0
20.07.2015, 08:43
    #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
20.07.2015, 10:21
    #39011011
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Оценка времени выполнения аналогичных циклов.
На ноль проверка быстрее идёт.
...
Рейтинг: 0 / 0
20.07.2015, 10:28
    #39011023
m_Sla
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Оценка времени выполнения аналогичных циклов.
SashaMercuryЗдравствуйте.
Сегодня читал статью(p.5) , согласно которой прямой цикл будет медленнее обратного. Написал такой пример, получается ровно наоборот(программа вычисляет натуральный логарифм как сумму гармонического ряда без постоянной Эйлера-Маскерони). Я что-то не так понял в той работе, или пример неудачный ?
...на разных платформах, на разных компиляторах результат может быть сильно разный
имхо пиши как можно понятнее, а оптимизацию, если будет нужно, делай в самый последний момент

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

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

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

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

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

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

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

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

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


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


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


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