Форум программистов, компьютерный форум CyberForum.ru

Циклы и их оптимизация - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 11, средняя оценка - 4.91
DVGU.MAKC
0 / 0 / 0
Регистрация: 13.01.2012
Сообщений: 35
11.06.2013, 21:41     Циклы и их оптимизация #1
Доброго времени суток!
Имеется код программы, необходимо оптимизировать вложенный цикл чтобы время потраченное на выполнение программы уменьшилось после оптимизации на заметное число >1 секунды. Можете по своему усмотрению усложнить код (вложив еще цикл) для заметности автоматизации.
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream.h>
#include <math.h>
#include <process.h>
 int main()
{
    int n, i=2, j;
    double sum;
    cout<<"n= ";
    cin>>n;
    for(i=0; i<n+1; i++)
    {
    sum=0;
    for(j=1; j<i+2; j++)
        sum+=(double)1/(i*i+j);
    cout<<"F"<<i<<"="<<sum<<endl;
    }
    system("pause");
   return 0;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.06.2013, 21:41     Циклы и их оптимизация
Посмотрите здесь:

Оптимизация C++
Оптимизация кода, массивы и циклы C++
Оптимизация алгоритма C++
Оптимизация алгоритма C++
C++ оптимизация кода
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
castaway
Эксперт С++
4837 / 2976 / 367
Регистрация: 10.11.2010
Сообщений: 11,008
Записей в блоге: 10
Завершенные тесты: 1
11.06.2013, 22:57     Циклы и их оптимизация #2
Единственное что приходит в голову - это lookup table.
C++
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
#include <iostream>
 
using namespace std;
 
static const size_t n_max = 55;
static double       lut[n_max * n_max + n_max + 1];
 
int main()
{
    int     n, i, ii, j;
    double  sum;
 
    cout << "n = ";
    cin >> n;
 
    if ( n > n_max ) {
        cout << "n must be less or equal " << n_max << endl;
        return 1;
    }
 
    // precalculate values
    for ( i = 0; i < n + 1; i++ ) {
        for ( j = 1; j < i + 2; j++ ) {
            lut[i * i + j] = 1. / (i * i + j);
        }
    }
 
    for ( i = 0; i < n + 1; i++ ) {
        ii = i * i;
 
        sum = 0;
        for ( j = 1; j < i + 2; j++ ) {
            sum += lut[ii + j];
        }
 
        cout << "F" << i << " = " << sum << endl;
    }
    return 0;
}
На сколько это ускорит процесс я не знаю.. надо замерять.
С другой стороны я не вижу ни одной причины, по которой стоит оптимизировать этот цикл.
DVGU.MAKC
0 / 0 / 0
Регистрация: 13.01.2012
Сообщений: 35
11.06.2013, 23:03  [ТС]     Циклы и их оптимизация #3
А что программа делает, я ввожу число понятно, результат она его делит на что то,объясните смысл программы, не могу понять вот это:
C
1
2
for(j=1; j<i+2; j++)
        sum+=(double)1/(i*i+j);
castaway
Эксперт С++
4837 / 2976 / 367
Регистрация: 10.11.2010
Сообщений: 11,008
Записей в блоге: 10
Завершенные тесты: 1
11.06.2013, 23:05     Циклы и их оптимизация #4
Это твоя программа, ты мне должен объяснять что она делает.
Зачем тебе понадобилась оптимизация цикла, который ты не знаешь для чего и как работает?
DVGU.MAKC
0 / 0 / 0
Регистрация: 13.01.2012
Сообщений: 35
11.06.2013, 23:07  [ТС]     Циклы и их оптимизация #5
Цитата Сообщение от lazybiz Посмотреть сообщение
Это твоя программа, ты мне должен объяснять что она делает.
сижу, разбираюсь в оптимизации циклов, уже 12 часов сижу, голова кругом, нашел какую то программу, увидел вложенный цикл решил поинтересоваться для общего развития как можно оптимизировать и что она делает, я сам понять не могу. А Вы бы не могли подсказать?
castaway
Эксперт С++
4837 / 2976 / 367
Регистрация: 10.11.2010
Сообщений: 11,008
Записей в блоге: 10
Завершенные тесты: 1
11.06.2013, 23:11     Циклы и их оптимизация #6
Если тебе нужны приемы оптимизации то я привел тебе один.
Для того чтобы понять как он работает не надо знать для чего нужна эта программа и какие магические числа она считает.
Matan!
13 / 13 / 1
Регистрация: 31.05.2013
Сообщений: 206
Записей в блоге: 2
Завершенные тесты: 1
11.06.2013, 23:44     Циклы и их оптимизация #7
на всякий случай приведу комментарии

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream.h>  //подключение библиотек
#include <math.h>
#include <process.h>
 int main()
{
    int n, i=2, j;   // i, j - счётчики циклов
    double sum;
    cout<<"n= ";  //это число,которое вводим, должно быть максимальным
    cin>>n;
    for(i=0; i<n+1; i++)  //если n максимальное число,
                                //то незачем прибавлять к нему 1, проще записать for(i=0; i<=n; i++)
    {
    sum=0;    //сначала сумма была равна 0...
    for(j=1; j<i+2; j++)
        sum+=(double)1/(i*i+j);  //приведение типов в С++
    cout<<"F"<<i<<"="<<sum<<endl;
    }
    system("pause");  //останавливаем прогу,чтобы посмотреть на её результат
   return 0;
}
Добавлено через 2 минуты
попытайтесь оптимизировать прогу,путём изменения входных данных.
castaway
Эксперт С++
4837 / 2976 / 367
Регистрация: 10.11.2010
Сообщений: 11,008
Записей в блоге: 10
Завершенные тесты: 1
11.06.2013, 23:47     Циклы и их оптимизация #8
Цитата Сообщение от Matan! Посмотреть сообщение
путём изменения входных данных.
А можно оптимизировать программу путем изменения алгоритма?
DVGU.MAKC
0 / 0 / 0
Регистрация: 13.01.2012
Сообщений: 35
11.06.2013, 23:51  [ТС]     Циклы и их оптимизация #9
Ну вот смотрите: sum+=(double)1/(i*i+j); sum += i; // Оператор цикла, double - обозначает дробную переменную
получается 1/(i*i+j) то есть с математической точки зрения 1/(n*n+i+2) 1/(150*150+150+2)... 150 это допустим число повторений или с чего начинается сама программа? если с чего начинается сама программа то 1... Правильно я мыслю?
castaway
Эксперт С++
4837 / 2976 / 367
Регистрация: 10.11.2010
Сообщений: 11,008
Записей в блоге: 10
Завершенные тесты: 1
11.06.2013, 23:53     Циклы и их оптимизация #10
Цитата Сообщение от DVGU.MAKC Посмотреть сообщение
Правильно я мыслю?
Хз. Я не понял что ты сказал.
А ты в Си/С++ вообще разбираешься?
DVGU.MAKC
0 / 0 / 0
Регистрация: 13.01.2012
Сообщений: 35
11.06.2013, 23:54  [ТС]     Циклы и их оптимизация #11
Цитата Сообщение от lazybiz Посмотреть сообщение
Хз. Я не понял что ты сказал.
А ты в Си/С++ вообще разбираешься?
есть немного, ну так совсем чуть чуть
castaway
Эксперт С++
4837 / 2976 / 367
Регистрация: 10.11.2010
Сообщений: 11,008
Записей в блоге: 10
Завершенные тесты: 1
11.06.2013, 23:55     Циклы и их оптимизация #12
Не рановато ты в оптимизацию полез?!
Matan!
13 / 13 / 1
Регистрация: 31.05.2013
Сообщений: 206
Записей в блоге: 2
Завершенные тесты: 1
11.06.2013, 23:55     Циклы и их оптимизация #13
Цитата Сообщение от lazybiz Посмотреть сообщение
А можно оптимизировать программу путем изменения алгоритма?
Алгоритм и так прост,как тибетский валенок)
DVGU.MAKC
0 / 0 / 0
Регистрация: 13.01.2012
Сообщений: 35
11.06.2013, 23:58  [ТС]     Циклы и их оптимизация #14
Ну смотри: for(j=1; j<i+2; j++) sum+=(double)1/(i*i+j);i=2 получается по условию задачи в объявлении переменной, j исходя из описания цикла получается <i+2 получается сумма=1/(2*2+3)=1/7=0,14 отсюда следует программа запрашивает число повторений допустим 10, стартовое значение получается 1, потом пробегая по циклам в результате чего совершив 1 цикл делит 1на0.14 верно?
Matan!
13 / 13 / 1
Регистрация: 31.05.2013
Сообщений: 206
Записей в блоге: 2
Завершенные тесты: 1
12.06.2013, 00:02     Циклы и их оптимизация #15
Цитата Сообщение от DVGU.MAKC Посмотреть сообщение
(double)1/(i*i+j)
это приведение типов.Почитай учебник.У тебя i и j целые и в знаменателе,поэтому надо перевести это выражение в double.

Цитата Сообщение от DVGU.MAKC Посмотреть сообщение
sum += i
- это просто sum =sum + i.
DVGU.MAKC
0 / 0 / 0
Регистрация: 13.01.2012
Сообщений: 35
12.06.2013, 00:03  [ТС]     Циклы и их оптимизация #16
Цитата Сообщение от lazybiz Посмотреть сообщение
Не рановато ты в оптимизацию полез?!
да рановато, а толку та, когда приспичит и не в такое полезешь. с 10 числа сижу курсовую делаю, оптимизация встроенных циклов, вчера в 3 часа дня как встал так и до сих пор не ложился завтра сдавать уже надо, время уже 7:01 (я в Приморье живу), информации вроде как нашел, прочитал, переделал, а вот с программой не думал что все так будет сложно, вот и приходится разбираться сидеть
castaway
Эксперт С++
4837 / 2976 / 367
Регистрация: 10.11.2010
Сообщений: 11,008
Записей в блоге: 10
Завершенные тесты: 1
12.06.2013, 00:04     Циклы и их оптимизация #17
В первой итерации i=0, j=1, поэтому сначала 1. делится на 1
Matan!
13 / 13 / 1
Регистрация: 31.05.2013
Сообщений: 206
Записей в блоге: 2
Завершенные тесты: 1
12.06.2013, 00:05     Циклы и их оптимизация #18
Нет,i=2 в начале.А потом i++.
Ты ведь вложил один цикл в другой.

Добавлено через 1 минуту
Цитата Сообщение от DVGU.MAKC Посмотреть сообщение
int n, i=2
Цитата Сообщение от DVGU.MAKC Посмотреть сообщение
for(i=0
непонятки...
castaway
Эксперт С++
4837 / 2976 / 367
Регистрация: 10.11.2010
Сообщений: 11,008
Записей в блоге: 10
Завершенные тесты: 1
12.06.2013, 00:07     Циклы и их оптимизация #19
Цитата Сообщение от Matan! Посмотреть сообщение
Нет,i=2 в начале.А потом i++.
Ты ведь вложил один цикл в другой.
Читай внимательней. Тут каким значением инициализируется i: for(i=0; i<n+1; i++) ?

Добавлено через 46 секунд
В самом начале =2 можно вообще убрать, на результат не повлияет.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.06.2013, 00:09     Циклы и их оптимизация
Еще ссылки по теме:

Оптимизация кода C++
Оптимизация программы C++
Оптимизация робота C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
DVGU.MAKC
0 / 0 / 0
Регистрация: 13.01.2012
Сообщений: 35
12.06.2013, 00:09  [ТС]     Циклы и их оптимизация #20
Смотрите что получается:
n=15
F0=1
F1=0.833333
F2=0.509524
F3=0.351166
F4=0.26463
F5=0.211287
Может быть не мучиться, взять решить исходя из этих данных математически найти в результате чего происходят такие изменения и все?
Ну выполняется же сначала внутренний цикл а потом внешний или неправильно?
Yandex
Объявления
12.06.2013, 00:09     Циклы и их оптимизация
Ответ Создать тему
Опции темы

Текущее время: 06:51. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru