Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.67/9: Рейтинг темы: голосов - 9, средняя оценка - 4.67
0 / 0 / 0
Регистрация: 06.09.2013
Сообщений: 9
1

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

01.11.2013, 16:24. Показов 1835. Ответов 17
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Добрый вечер. Решил задачу, и решил прогнать по acmp.ru. Программа заваливается по времени выполнения, выходит 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;
}
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
01.11.2013, 16:24
Ответы с готовыми решениями:

Уменьшение времени работы кода
Здравствуйте, есть код: #include &lt;iostream&gt; using namespace std; int main(){ int a , b , c,...

Подсчет времени работы программы
Есть код программы. Задача такая - вставить таймер который будет считать сколько времени работала...

Ограничение по времени работы программы
Всем доброго времени суток. Есть задача: Программа (любая) должна позволять пользоваться ей...

Подсчет времени работы программы
пожалуйста помогите посчитать время программы с функцией.не знаю почему программа выдает что-то...

17
188 / 187 / 46
Регистрация: 24.03.2011
Сообщений: 670
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);
}
1
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 ))) буду дальше облегчать)
0
188 / 187 / 46
Регистрация: 24.03.2011
Сообщений: 670
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 у тебя все твои числа.
1
Форумчанин
Эксперт CЭксперт С++
8215 / 5045 / 1437
Регистрация: 29.11.2010
Сообщений: 13,453
01.11.2013, 19:27 5
Цитата Сообщение от Инспектор Котик Посмотреть сообщение
выходит 2.5 секунд, в идеале должно быть не меньше одной
так в идеале же, что еще менять?
0
0 / 0 / 0
Регистрация: 06.09.2013
Сообщений: 9
01.11.2013, 19:34  [ТС] 6
Цитата Сообщение от monolit Посмотреть сообщение
Ну, это не означает, что время уменьшилось) Погрешность просто...
Сдается мне, узкое место здесь - чтение данных. В буфер бы раз прочитать, и оттуда уже извлекать(из массива интов, порядок расположения тебе известен...)
спасибо. Не уверен что там можно создавать файлы, но попробую и отпишусь.

Добавлено через 2 минуты
Цитата Сообщение от MrGluck Посмотреть сообщение
так в идеале же, что еще менять?
acmp.ru же=) хочу войти в лимит, что бы поумнеть и получить плюсик в карму
0
Форумчанин
Эксперт CЭксперт С++
8215 / 5045 / 1437
Регистрация: 29.11.2010
Сообщений: 13,453
01.11.2013, 19:44 7
vector<char> будет работать быстрее всех его специализаций. Но если честно, не за чем тут усложнять обычный двумерный массив.

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

Не по теме:

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

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

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

Не по теме:


2.5 не меньше 1

у остальных получилось, хочу также.
0
_
317 / 151 / 27
Регистрация: 08.10.2011
Сообщений: 432
01.11.2013, 19:52 9
а ларчик то просто открывается: в задаче сказано, что данные должны читаться из файла INPUT.txt и записываться в OUTPUT.txt. у вас они читаются из cin, а записываются в cout, а система ищет файл OUTPUT.txt
1
Модератор
Эксперт по электронике
8908 / 6677 / 918
Регистрация: 14.02.2011
Сообщений: 23,521
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];
1
0 / 0 / 0
Регистрация: 06.09.2013
Сообщений: 9
01.11.2013, 21:34  [ТС] 11
Спасибо всем, это просто моя первая задача в таком формате. я бы и не догадался что нужно input.txt и output.txt создавать. да и массив динамический оказывается не нужен, ну дурак на своих ошибках учится. Главное что в основном решалось все правильно при ручных проверках. в общем дурак на своих ошибках учится. И еще в задаче не указано что w меньше или равно 100, вот я и подумал в сторону дин. массивов.

Добавлено через 19 минут
Вот как я мог угадать что у переменно w потолок это 100?
0
188 / 187 / 46
Регистрация: 24.03.2011
Сообщений: 670
01.11.2013, 21:34 12
Цитата Сообщение от MrGluck Посмотреть сообщение
должно быть не меньше одной
Цитата Сообщение от MrGluck Посмотреть сообщение
быть не меньше одной
Цитата Сообщение от MrGluck Посмотреть сообщение
не меньше одной
Цитата Сообщение от MrGluck Посмотреть сообщение
не меньше
Не больше, ты хотел написать?)
0
Модератор
Эксперт по электронике
8908 / 6677 / 918
Регистрация: 14.02.2011
Сообщений: 23,521
01.11.2013, 21:35 13
Цитата Сообщение от Инспектор Котик Посмотреть сообщение
Вот как я мог угадать что у переменно w потолок это 100?
отсюда
Цитата Сообщение от Инспектор Котик Посмотреть сообщение
содержит два натуральных числа w и h (1 ≤ w, h ≤ 100).
0
Форумчанин
Эксперт CЭксперт С++
8215 / 5045 / 1437
Регистрация: 29.11.2010
Сообщений: 13,453
01.11.2013, 21:36 14
Цитата Сообщение от monolit Посмотреть сообщение
Не больше, ты хотел написать?)
это ТС так хотел написать, я ему уже 2 поста тонко намекаю, а он в упор не видит
0
188 / 187 / 46
Регистрация: 24.03.2011
Сообщений: 670
01.11.2013, 21:43 15
Цитата Сообщение от MrGluck Посмотреть сообщение
это ТС так хотел написать, я ему уже 2 поста тонко намекаю, а он в упор не видит
Эт я цитату не оттуда взял просто)
0
0 / 0 / 0
Регистрация: 06.09.2013
Сообщений: 9
01.11.2013, 21:59  [ТС] 16
Да понял я на счет не меньше одной))))) просто под вечер я уже никакой + болезнь(ангина, температура). Думаю все когда то болеют.
0
ValeryS
01.11.2013, 22:00
  #17

Не по теме:

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

1
Неэпический
17870 / 10635 / 2054
Регистрация: 27.09.2012
Сообщений: 26,737
Записей в блоге: 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 ) ;
}
0
02.11.2013, 01:21
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
02.11.2013, 01:21
Помогаю со студенческими работами здесь

Уменьшение времени выполнения цикла
Нужна помощь, мне надо засечь время выполнения цикла, который инициализирует элементы массива. А...

Уменьшение времени выполнения кода
//Помогите ускорить код #include &lt;iostream&gt; #include &lt;vector&gt; #include &lt;algorithm&gt; using...

Уменьшение\Увеличение времени (посфикс,префикс)
Добрый день! Имеется задание на уменьшение и увеличение времени инкрементом (постфикс,префикс)....

Уменьшение размера программы
Здравствуйте, мне нужно уменьшить размер программы, прочитал что нужно добавлять строки: #pragma...


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

Или воспользуйтесь поиском по форуму:
18
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru