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

Оптимизация вычислений - C++

Восстановить пароль Регистрация
 
Ksan
26 / 26 / 0
Регистрация: 02.11.2010
Сообщений: 370
12.03.2012, 18:05     Оптимизация вычислений #1
Есть код:

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
fstream file("out13.txt", ios::out);
    
    int index[16], summ;
    
    for(index[0] = 0; index[0]<=9; ++index[0])
    {
        cout << "index[0] = " << index[0] << '\n';
        for(index[1] = 0; index[1]<=9; ++index[1])
        {
            cout << "index[1] = " << index[1] << '\n';
            for(index[2] = 0; index[2]<=9; ++index[2])
            {
                for(index[3] = 0; index[3]<=9; ++index[3])
                {
                    for(index[4] = 0; index[4]<=9; ++index[4])
                    {
                        for(index[5] = 0; index[5]<=9; ++index[5])
                        {
                            for(index[6] = 0; index[6]<=9; ++index[6])
                            {
                                for(index[7] = 0; index[7]<=9; ++index[7])
                                {
                                    for(index[8] = 0; index[8]<=9; ++index[8])
                                    {
                                        for(index[9] = 0; index[9]<=9; ++index[9])
                                        {
                                            for(index[10] = 0; index[10]<=9; ++index[10])
                                            {
                                                for(index[11] = 0; index[11]<=9; ++index[11])
                                                {
                                                    for(index[12] = 0; index[12]<=9; ++index[12])
                                                    {
                                                        summ = 0;
                                                  for(int i=0; i<13; ++i) summ += index[i];
                                                if(summ == 13)
                                                {
                                                  for(int i=0; i<13; ++i) if(index[i] != 0) file << index[i];
                                                file << '\n';
                                              }
                                                        
                                                    }
                                                }
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    
    file.close();

Но он будет выполняться слишком долго. Какие есть идеи оптимизации?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
12.03.2012, 18:05     Оптимизация вычислений
Посмотрите здесь:

C++ Точность вычислений
Точности вычислений double C++
программирование математических вычислений C++
C++ Погрешность вычислений
Распараллеливание вычислений C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
12.03.2012, 18:58     Оптимизация вычислений #2
А задачу можно узнать?
Ksan
26 / 26 / 0
Регистрация: 02.11.2010
Сообщений: 370
12.03.2012, 19:01  [ТС]     Оптимизация вычислений #3
Мне нужно перебрать все числа от 999...999 до 0. Где количество 9 равно N. В файл записываются только варианты, гда сумма цифр числа = N. я перебрал уже 1..10, нужно до 16 включительно.
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
12.03.2012, 19:19     Оптимизация вычислений #4
Я как-то писал подобную задачу для чисел от 10^9 до 10^10, но максимум, чего я достиг - 2 минуты. До 10^16 вообще сложно перебирать, даже если цикл будет пустым, то работать будет очень долго.
P.S. ваш вариант можно оптимизировать, если вычислять сумму получившего числа за O(1), и автоматически отсекать лишние циклы, когда эта сумма становится больше требуемой.

Добавлено через 8 минут
Вот, примерно так.
Только вместо массива я макрос использовал, за секунду отрабатывает, причем почти все время на вывод уходит.
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
40
41
#include <stdio.h>
 
#define FOR(x, l, code)                                 \
    for ( a##x = l; a##x <= 9 && sum <= 10 ; ++a##x )   \
    {                                                   \
        sum += a##x;                                    \
        code                                            \
        sum -= a##x;                                    \
    }           
    
 
 
int main()
{   
    int sum = 0;
    int a1, a2, a3, a4, a5, a6, a7, a8, a9, a10;
    
    FOR(1, 1,
    FOR(2, 0,
    FOR(3, 0,
    FOR(4, 0,
    FOR(5, 0,
    FOR(6, 0,
    FOR(7, 0,
    FOR(8, 0,
    FOR(9, 0,
    FOR(10, 0,
        
        if ( sum == 10 )
        {
            long long number = a1 * 1e9 + a2 * 1e8 + a3 * 1e7 + a4 * 1e6
                             + a5 * 1e5 + a6 * 1e4 + a7 * 1e3 + a8 * 1e2
                             + a9 * 10 + a10;           
            
            printf("%lld ", number);            
        }
        
    ) ) ) ) ) ) ) ) ) )
    
    return 0;                                   
}
В принципе можно и для 10^16 посчитать таким способом, т.к. на самом деле перебирается небольшое количество чисел, все лишнее отсекается.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
12.03.2012, 19:51     Оптимизация вычислений #5
Цитата Сообщение от diagon Посмотреть сообщение
Только вместо массива я макрос использовал, за секунду отрабатывает, причем почти все время на вывод уходит.
А Вы попробуйте сразу в файл выводить.

diagon, есть более быстрый способ: методом перебора или рекурсией перебираем все варианты когда последующая цифра равна или больше предыдущей (можно отсекать лишние циклы, варианты). Натыкаемся на вариант когда сумма цифр числа = N. Делаем перестановку этого набора и идем дальше.
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
12.03.2012, 20:02     Оптимизация вычислений #6
Цитата Сообщение от valeriikozlov Посмотреть сообщение
А Вы попробуйте сразу в файл выводить.
Так за 0.015 отрабатывает =)
Правда я вывод более оптимальный сделал:
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
40
41
42
43
44
45
46
47
48
49
#include <stdio.h>
 
#define FOR(x, l, code)                                 \
    for ( a##x = l; a##x <= 9 && sum <= 10 ; ++a##x )   \
    {                                                   \
        sum += a##x;                                    \
        code                                            \
        sum -= a##x;                                    \
    }           
    
 
 
int main()
{   
    freopen("output.txt", "w", stdout);
    
    int sum = 0;
    int a1, a2, a3, a4, a5, a6, a7, a8, a9, a10;
    
    FOR(1, 1,
    FOR(2, 0,
    FOR(3, 0,
    FOR(4, 0,
    FOR(5, 0,
    FOR(6, 0,
    FOR(7, 0,
    FOR(8, 0,
    FOR(9, 0,
    FOR(10, 0,
        
        if ( sum == 10 )
        {
            putchar(a1 + '0');
            putchar(a2 + '0');
            putchar(a3 + '0');
            putchar(a4 + '0');
            putchar(a5 + '0');
            putchar(a6 + '0');
            putchar(a7 + '0');
            putchar(a8 + '0');
            putchar(a9 + '0');
            putchar(a10 +'0');
            putchar(' ');
        }
        
    ) ) ) ) ) ) ) ) ) )
    
    return 0;                                   
}
Цитата Сообщение от valeriikozlov Посмотреть сообщение
Делаем перестановку этого набора и идем дальше.
В смысле? Если просто выводить все перестановки этого числа, то в дальнейшем, когда попадется перестановка этого числа, как узнать, что оно уже было?
Ну, например, для трехзначного:
102
можно вывести перестановки
102, 120, 210, 201, но когда попадется число 120, то как узнать, что оно уже выводилось?
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
12.03.2012, 20:06     Оптимизация вычислений #7
Цитата Сообщение от diagon Посмотреть сообщение
Ну, например, для трехзначного:
102
можно вывести перестановки
102, 120, 210, 201, но когда попадется число 102, то как узнать, что оно уже выводилось?
я же писал:
Цитата Сообщение от valeriikozlov Посмотреть сообщение
все варианты когда последующая цифра равна или больше предыдущей
то есть нам попадется вариант 012, по этому варианту мы делаем перестановки 021, 102, 120, 210, 201.
Варианты 021, 102, 120, 210, 201 нам уже не попадутся.
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
12.03.2012, 20:08     Оптимизация вычислений #8
Цитата Сообщение от valeriikozlov Посмотреть сообщение
то есть нам попадется вариант 012, по этому варианту мы делаем перестановки 021, 102, 120, 210, 201.
Варианты 021, 102, 120, 210, 201 нам уже не попадутся.
Ну да, тогда вариант оптимальнее сложно придумать.
Ksan
26 / 26 / 0
Регистрация: 02.11.2010
Сообщений: 370
12.03.2012, 20:43  [ТС]     Оптимизация вычислений #9
Прокомментируйте пожалуйста код, не совсем понимаю что к чему
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
13.03.2012, 11:32     Оптимизация вычислений
Еще ссылки по теме:

Распараллеливание вычислений C++
C++ Перенос вычислений в подпрограмму
C++ Шаблон параллельных вычислений

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

Или воспользуйтесь поиском по форуму:
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
13.03.2012, 11:32     Оптимизация вычислений #10
Цитата Сообщение от Ksan Посмотреть сообщение
Прокомментируйте пожалуйста код, не совсем понимаю что к чему
Почитайте где-нибудь про макросы
первый FOR(1, 1, ...) раскрывается как
C
1
2
3
4
5
6
for (a1 = 1; a1 <= 9 && sum <= 10; ++a1)
{
    sum += a1;
    ...
    sum -= a1;
}
Ну и этот код перебирает все десятизначные числа.

Вот код, который перебирает числа от 0 до 10^16.
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <stdio.h>
 
#define FOR(x, code)                                    \
    for ( a##x = 0; a##x <= 9 && sum <= 16 ; ++a##x )   \
    {                                                   \
        sum += a##x;                                    \
        code                                            \
        sum -= a##x;                                    \
    }           
    
 
 
int main()
{   
    freopen("output.txt", "w", stdout);
    
    int sum = 0;
    int a1, a2, a3, a4, a5, a6, a7, a8, a9, a10, a11, a12, a13, a14, a15, a16;
    
    FOR(1, 
    FOR(2, 
    FOR(3, 
    FOR(4, 
    FOR(5, 
    FOR(6, 
    FOR(7, 
    FOR(8, 
    FOR(9, 
    FOR(10, 
    FOR(11,
    FOR(12,
    FOR(13,
    FOR(14,
    FOR(15,
    FOR(16,
        
        if ( sum == 16 )
        {
            char str[17];
            
            str[0] = a1 + '0';
            str[1] = a2 + '0';
            str[2] = a3 + '0';
            str[3] = a4 + '0';
            str[4] = a5 + '0';
            str[5] = a6 + '0';
            str[6] = a7 + '0';
            str[7] = a8 + '0';
            str[8] = a9 + '0';
            
            str[9 ] = a10 + '0';
            str[10] = a11 + '0';
            str[11] = a12 + '0';
            str[12] = a13 + '0';
            str[13] = a14 + '0';
            str[14] = a15 + '0';
            str[15] = a16 + '0';
            
            str[16] = '\0';
            
            char * p = str;
            while (*p == '0')
                ++p;
                
            printf("%s ", p);
        }
        
    ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) )
    
    return 0;                                   
}
Работает у меня ровно 100 секунд, но проверить правильность я не могу, т.к. размер файла доползает до 2.1 гб, а больше у меня, видимо, создать нельзя, поэтому еще половина чисел попросту недописывается =\
А вообще это быдлокод, конечно, лучше использовать вариант, который предложил valeriikozlov.
Yandex
Объявления
13.03.2012, 11:32     Оптимизация вычислений
Ответ Создать тему
Опции темы

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