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

Уменьшение времени работы программы - C++

Восстановить пароль Регистрация
 
Инспектор Котик
0 / 0 / 0
Регистрация: 06.09.2013
Сообщений: 9
01.11.2013, 16:24     Уменьшение времени работы программы #1
Добрый вечер. Решил задачу, и решил прогнать по ********. Программа заваливается по времени выполнения, выходит 2.5 секунд, в идеале должно быть не меньше одной. Помогите плиз.
Вот задача:

Кликните здесь для просмотра всего текста

Известный художник решил написать новый шедевр. После многих дней усердной работы он захотел исследовать свое творение. Художник вспомнил, что картина писалась следующим образом: сначала был взят белый холст, имеющий форму прямоугольника шириной w и высотой h. Затем художник нарисовал на этом холсте n прямоугольников со сторонами, параллельными сторонам холста и вершинами, расположенными в целочисленных координатах. Помогите художнику определить площадь незакрашенной части холста.
Входные данные

Первая строка входного файла INPUT.TXT содержит два натуральных числа w и h (1 ≤ w, h ≤ 100). Во второй строке записано целое число n (0 ≤ n ≤ 5000) – количество прямоугольников. Следующие n строк содержат информацию о всех прямоугольниках. Каждая строка описывает один прямоугольник в виде четырех чисел x1, y1, x2, y2 , где (x1, y1) и (x2, y2) – координаты левого верхнего и правого нижнего угла прямоугольника соответственно.
Выходные данные

Выведите в выходной файл OUTPUT.TXT одно целое число – площадь незакрашенной части холста.

Вот Код:
Кликните здесь для просмотра всего текста

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
72
73
74
75
76
77
78
79
80
81
82
#include <iostream>
 
 
using namespace std;
 
 
int main()
{
    int w = 0;
    int h = 0;
    int n = 0;
    int x1 = 0;
    int y1 = 0;
    int x2 = 0;
    int y2 = 0;
    int c = 0;
 
    cin >> w >> h;
 
    int** canvas = new int*[w];
 
    for(int i = 0; i < w; i++)
    { canvas[i] = new int[h]; }
 
   for(int i = 0; i < w; i++)
    {
            for(int j = 0; j < h; j++)
            {
               canvas[i][j] = 0;
            }
    }
 
   cin >> n;
 
 
   while(n > 0)
   {
       cin >> x1 >> y1 >> x2 >> y2;
 
       for(int i = x1; i < x2; i++)
       {
           for(int j = y1; j < y2; j++)
           {
               canvas[i][j] = 1;
 
           }
       }
 
       n-=1;
 
   }
   cout << endl;
 
 
 
  for(int i = 0; i < w; i++)
   {
       for(int j = 0; j < h; j++)
       {
           if(canvas[i][j] == 1)
           {
               c++;
           }
       }
   }
 
   c = (w * h) - c;
 
   cout << c  << endl;
 
 
 
 
  for(int i = 0; i < w; i++)
       {
            delete[] canvas[i];
       }
 
 
 
    return 0;
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
monolit
179 / 179 / 21
Регистрация: 24.03.2011
Сообщений: 641
Завершенные тесты: 1
01.11.2013, 18:20     Уменьшение времени работы программы #2
Слишком много циклов. подсчитывать занятые можно и в первом:
C++
1
2
3
4
5
6
7
8
9
10
11
12
while(n > 0) {
       cin >> x1 >> y1 >> x2 >> y2;
       for(int i = x1; i < x2; i++) {
           for(int j = y1; j < y2; j++) {
               if (!canvas[i][j]) {
                    ++c;
                    canvas[i][j] = 1;
               }
           }
       }
       n-=1;
   }
Эээ... А как ты файл использовал то? Если будешь использовать - для ускорения посоветую читать не посимвольно/по словам, а раз прочитать в какой-нибудь буфер(скажем, массив), и оттуда в нужном порядке извлекать данные. Поможет stl'евские copy, ostream_iterator и vector.
А еще (хз, мож тут и не заметно будет) можно развернуть матрицу в массив(т.е. память выделять один раз), и обращаться как [I] a[j] -> a[j*width+i]. Опять же, на таких данных может прироста и не заметишь...хотя по идее при больших размерах массива это будет быстрее(выделение памяти чертовски накладная операция)

Ах да, инициализацию можно занести туда:
C++
1
2
3
4
for(int i = 0; i < w; i++) { 
canvas[i] = new int[h]; 
for(int j = 0; j < h; j++) canvas[i][j] = 0;
}
Или воспользоваться memset, вроде должно быть быстрее:
C++
1
2
3
4
for(int i = 0; i < w; i++) { 
canvas[i] = new int[h]; 
memset(canvas[i], 0, sizeof(int)*h);
}
Инспектор Котик
0 / 0 / 0
Регистрация: 06.09.2013
Сообщений: 9
01.11.2013, 19:05  [ТС]     Уменьшение времени работы программы #3
Цитата Сообщение от monolit Посмотреть сообщение
Слишком много циклов. подсчитывать занятые можно и в первом:
C++
1
2
3
4
5
6
7
8
9
10
11
12
while(n > 0) {
       cin >> x1 >> y1 >> x2 >> y2;
       for(int i = x1; i < x2; i++) {
           for(int j = y1; j < y2; j++) {
               if (!canvas[i][j]) {
                    ++c;
                    canvas[i][j] = 1;
               }
           }
       }
       n-=1;
   }
Спасибо) было 2,411 стало 2,399 ))) буду дальше облегчать)
monolit
179 / 179 / 21
Регистрация: 24.03.2011
Сообщений: 641
Завершенные тесты: 1
01.11.2013, 19:16     Уменьшение времени работы программы #4
Ну, это не означает, что время уменьшилось) Погрешность просто...
Сдается мне, узкое место здесь - чтение данных. В буфер бы раз прочитать, и оттуда уже извлекать(из массива интов, порядок расположения тебе известен...)

C++
1
2
3
4
5
6
7
ifstream is("INPUT.txt");
vector<int> v;
copy(
  istream_iterator<int>(is), 
  istream_iterator<char>(), 
  back_inserter(v)
);
И в v у тебя все твои числа.

Добавлено через 57 секунд
Ну, это не означает, что время уменьшилось) Погрешность просто...
Сдается мне, узкое место здесь - чтение данных. В буфер бы раз прочитать, и оттуда уже извлекать(из массива интов, порядок расположения тебе известен...)

C++
1
2
3
4
5
6
7
ifstream is("INPUT.txt");
vector<int> v;
copy(
  istream_iterator<int>(is), 
  istream_iterator<char>(), 
  back_inserter(v)
);
И в v у тебя все твои числа.
MrGluck
Ворчун
Эксперт С++
 Аватар для MrGluck
4927 / 2670 / 243
Регистрация: 29.11.2010
Сообщений: 7,429
01.11.2013, 19:27     Уменьшение времени работы программы #5
Цитата Сообщение от Инспектор Котик Посмотреть сообщение
выходит 2.5 секунд, в идеале должно быть не меньше одной
так в идеале же, что еще менять?
Инспектор Котик
0 / 0 / 0
Регистрация: 06.09.2013
Сообщений: 9
01.11.2013, 19:34  [ТС]     Уменьшение времени работы программы #6
Цитата Сообщение от monolit Посмотреть сообщение
Ну, это не означает, что время уменьшилось) Погрешность просто...
Сдается мне, узкое место здесь - чтение данных. В буфер бы раз прочитать, и оттуда уже извлекать(из массива интов, порядок расположения тебе известен...)
спасибо. Не уверен что там можно создавать файлы, но попробую и отпишусь.

Добавлено через 2 минуты
Цитата Сообщение от MrGluck Посмотреть сообщение
так в идеале же, что еще менять?
******** же=) хочу войти в лимит, что бы поумнеть и получить плюсик в карму
MrGluck
Ворчун
Эксперт С++
 Аватар для MrGluck
4927 / 2670 / 243
Регистрация: 29.11.2010
Сообщений: 7,429
01.11.2013, 19:44     Уменьшение времени работы программы #7
vector<char> будет работать быстрее всех его специализаций. Но если честно, не за чем тут усложнять обычный двумерный массив.

Добавлено через 50 секунд

Не по теме:

Цитата Сообщение от Инспектор Котик Посмотреть сообщение
хочу войти в лимит
2.5 не меньше 1

Инспектор Котик
0 / 0 / 0
Регистрация: 06.09.2013
Сообщений: 9
01.11.2013, 19:48  [ТС]     Уменьшение времени работы программы #8
Цитата Сообщение от MrGluck Посмотреть сообщение
vector<char> будет работать быстрее всех его специализаций. Но если честно, не за чем тут усложнять обычный двумерный массив.

Добавлено через 50 секунд

Не по теме:


2.5 не меньше 1

у остальных получилось, хочу также.
ya_noob
_
200 / 144 / 9
Регистрация: 08.10.2011
Сообщений: 432
01.11.2013, 19:52     Уменьшение времени работы программы #9
а ларчик то просто открывается: в задаче сказано, что данные должны читаться из файла INPUT.txt и записываться в OUTPUT.txt. у вас они читаются из cin, а записываются в cout, а система ищет файл OUTPUT.txt
ValeryS
Модератор
6377 / 4843 / 442
Регистрация: 14.02.2011
Сообщений: 16,061
01.11.2013, 20:04     Уменьшение времени работы программы #10
Инспектор Котик,
у тебя алгоритм не тот
во первых ты выделяешь память при максиме это 101 одно выделение памяти
потом 10000 обращений к памяти чтобы обнулить
далее чтобы что то записать в ячейку ты гуляешь по указателям, тоже тормоза
выдели статический массив всего то 10000 ячеек (при инте 40000 байт памяти)
а чтобы его не обнулять сделай или глобальным или static
скорость возрастет

Добавлено через 7 минут
Цитата Сообщение от Инспектор Котик Посмотреть сообщение
C++
1
2
3
4
5
6
7
8
9
10
11
for(int i = 0; i < w; i++)
 {
  for(int j = 0; j < h; j++)
   {
     if(canvas[i][j] == 1)
     {
        c++;
     }
  }
 }
c = (w * h) - c;
дальше
ты считаешь закрашенные а потом вычитаешь из общего
тут тормоза *if(canvas[i][j] == 1)
зачем???
закрашенные 1 не закрашенные 0
т.е прибавишь незакрашенную ячейку результат не изменится
C++
1
с+=canvas[i][j];
можно сразу считать незакрашенные
примерно так
C++
1
2
3
4
c = (w * h);
for(int i = 0; i < w; i++)
  for(int j = 0; j < h; j++)
      c-=canvas[i][j];
Инспектор Котик
0 / 0 / 0
Регистрация: 06.09.2013
Сообщений: 9
01.11.2013, 21:34  [ТС]     Уменьшение времени работы программы #11
Спасибо всем, это просто моя первая задача в таком формате. я бы и не догадался что нужно input.txt и output.txt создавать. да и массив динамический оказывается не нужен, ну дурак на своих ошибках учится. Главное что в основном решалось все правильно при ручных проверках. в общем дурак на своих ошибках учится. И еще в задаче не указано что w меньше или равно 100, вот я и подумал в сторону дин. массивов.

Добавлено через 19 минут
Вот как я мог угадать что у переменно w потолок это 100?
monolit
179 / 179 / 21
Регистрация: 24.03.2011
Сообщений: 641
Завершенные тесты: 1
01.11.2013, 21:34     Уменьшение времени работы программы #12
Цитата Сообщение от MrGluck Посмотреть сообщение
должно быть не меньше одной
Цитата Сообщение от MrGluck Посмотреть сообщение
быть не меньше одной
Цитата Сообщение от MrGluck Посмотреть сообщение
не меньше одной
Цитата Сообщение от MrGluck Посмотреть сообщение
не меньше
Не больше, ты хотел написать?)
ValeryS
Модератор
6377 / 4843 / 442
Регистрация: 14.02.2011
Сообщений: 16,061
01.11.2013, 21:35     Уменьшение времени работы программы #13
Цитата Сообщение от Инспектор Котик Посмотреть сообщение
Вот как я мог угадать что у переменно w потолок это 100?
отсюда
Цитата Сообщение от Инспектор Котик Посмотреть сообщение
содержит два натуральных числа w и h (1 ≤ w, h ≤ 100).
MrGluck
Ворчун
Эксперт С++
 Аватар для MrGluck
4927 / 2670 / 243
Регистрация: 29.11.2010
Сообщений: 7,429
01.11.2013, 21:36     Уменьшение времени работы программы #14
Цитата Сообщение от monolit Посмотреть сообщение
Не больше, ты хотел написать?)
это ТС так хотел написать, я ему уже 2 поста тонко намекаю, а он в упор не видит
monolit
179 / 179 / 21
Регистрация: 24.03.2011
Сообщений: 641
Завершенные тесты: 1
01.11.2013, 21:43     Уменьшение времени работы программы #15
Цитата Сообщение от MrGluck Посмотреть сообщение
это ТС так хотел написать, я ему уже 2 поста тонко намекаю, а он в упор не видит
Эт я цитату не оттуда взял просто)
Инспектор Котик
0 / 0 / 0
Регистрация: 06.09.2013
Сообщений: 9
01.11.2013, 21:59  [ТС]     Уменьшение времени работы программы #16
Да понял я на счет не меньше одной))))) просто под вечер я уже никакой + болезнь(ангина, температура). Думаю все когда то болеют.
ValeryS
01.11.2013, 22:00
  #17

Не по теме:

Цитата Сообщение от Инспектор Котик Посмотреть сообщение
росто под вечер я уже никакой + болезнь(ангина, температура)
ну к это, выздоравливай
и не напрягайся сильно, чтоб осложнений не было

MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
02.11.2013, 01:21     Уменьшение времени работы программы
Еще ссылки по теме:

Подсчет времени работы программы C++
C++ Уменьшение размера программы
Измерение времени работы кода C++

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

Или воспользуйтесь поиском по форуму:
Croessmah
Модератор
Эксперт С++
 Аватар для Croessmah
11845 / 6824 / 771
Регистрация: 27.09.2012
Сообщений: 16,919
Записей в блоге: 2
Завершенные тесты: 1
02.11.2013, 01:21     Уменьшение времени работы программы #18
Экзотика
ВНИМАНИЕ!!! В коде черт глаза сломает!!!
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
#include <fstream>
#include <list>
#include <utility>
 
using namespace std ;
 
int main ( ){   
    int width , height , rectsCount ;
    ifstream iFile ( "INPUT.TXT" ) ;
    iFile >> width >> height >> rectsCount ;
    
    const int maxHeight = 100 ;
    list < pair < int , int > > arr [ maxHeight ] ;
    
    int x1 , y1 , x2 , y2 ;
    while ( rectsCount ) {
        iFile >> x1 >> y1 >> x2 >> y2 ;
        for ( int y = y1 , addX1 = x1 , addX2 = x2 ; y < y2 ; ++y , addX1 = x1 , addX2 = x2  ) {
            for ( list < pair < int , int > >::iterator nowX = arr [ y ].begin ( ) ; nowX !=  arr [ y ].end ( ) ; ) {
                if ( ( addX1 - (*nowX).second ) * ( addX2 - (*nowX).first ) > 0 ) { 
                    ++nowX ;
                }
                else {
                    addX1 = min ( addX1 , (*nowX).first ) ;
                    addX2 = max ( addX2 , (*nowX).second ) ;
                    nowX = arr [ y ].erase ( nowX ) ;
                }
            }
            arr[y].push_front ( make_pair ( addX1 , addX2 ) ) ;
        }
        --rectsCount ;
    }
    
    int rectsSquare = 0 ;
    for ( int y = 0 ; y < height ; ++y ) {
        for ( list < pair < int , int > >::iterator nowX = arr [ y ].begin ( ) , endX = arr [ y ].end ( ) ; nowX != endX ; ++nowX ) {
            rectsSquare += (*nowX).second - (*nowX).first ;
        }
    }   
    ofstream oFile ( "OUTPUT.TXT" ) ;
    oFile << ( width * height - rectsSquare ) ;
}
Yandex
Объявления
02.11.2013, 01:21     Уменьшение времени работы программы
Ответ Создать тему
Опции темы

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