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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Инспектор Котик
0 / 0 / 0
Регистрация: 06.09.2013
Сообщений: 9
#1

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

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

Добрый вечер. Решил задачу, и решил прогнать по ********. Программа заваливается по времени выполнения, выходит 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;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
01.11.2013, 16:24     Уменьшение времени работы программы
Посмотрите здесь:

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

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

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

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

Уменьшение размера программы - C++
Здравствуйте, мне нужно уменьшить размер программы, прочитал что нужно добавлять строки: #pragma optimize(&quot;gsy&quot;,on) #pragma...

Уменьшение зависимостей скомпилированной программы - C++
#include &lt;iostream&gt; using namespace std; void main() { cout &lt;&lt; &quot;hi&quot; &lt;&lt; endl; system(&quot;pause&quot;); } На чистой WinXpSp2 ...

Оценка времени работы - C++
Можете оценить время работы алгоритма? http://acm.timus.ru/problem.aspx?space=1&amp;num=1100 - это задача, на которую он проходит По моему...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
monolit
185 / 184 / 22
Регистрация: 24.03.2011
Сообщений: 667
Завершенные тесты: 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
185 / 184 / 22
Регистрация: 24.03.2011
Сообщений: 667
Завершенные тесты: 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
Модератор
Эксперт CЭксперт С++
7171 / 4337 / 633
Регистрация: 29.11.2010
Сообщений: 11,784
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
Модератор
Эксперт CЭксперт С++
7171 / 4337 / 633
Регистрация: 29.11.2010
Сообщений: 11,784
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
_
201 / 145 / 9
Регистрация: 08.10.2011
Сообщений: 432
01.11.2013, 19:52     Уменьшение времени работы программы #9
а ларчик то просто открывается: в задаче сказано, что данные должны читаться из файла INPUT.txt и записываться в OUTPUT.txt. у вас они читаются из cin, а записываются в cout, а система ищет файл OUTPUT.txt
ValeryS
Модератор
6551 / 5017 / 463
Регистрация: 14.02.2011
Сообщений: 16,735
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
185 / 184 / 22
Регистрация: 24.03.2011
Сообщений: 667
Завершенные тесты: 1
01.11.2013, 21:34     Уменьшение времени работы программы #12
Цитата Сообщение от MrGluck Посмотреть сообщение
должно быть не меньше одной
Цитата Сообщение от MrGluck Посмотреть сообщение
быть не меньше одной
Цитата Сообщение от MrGluck Посмотреть сообщение
не меньше одной
Цитата Сообщение от MrGluck Посмотреть сообщение
не меньше
Не больше, ты хотел написать?)
ValeryS
Модератор
6551 / 5017 / 463
Регистрация: 14.02.2011
Сообщений: 16,735
01.11.2013, 21:35     Уменьшение времени работы программы #13
Цитата Сообщение от Инспектор Котик Посмотреть сообщение
Вот как я мог угадать что у переменно w потолок это 100?
отсюда
Цитата Сообщение от Инспектор Котик Посмотреть сообщение
содержит два натуральных числа w и h (1 ≤ w, h ≤ 100).
MrGluck
Модератор
Эксперт CЭксперт С++
7171 / 4337 / 633
Регистрация: 29.11.2010
Сообщений: 11,784
01.11.2013, 21:36     Уменьшение времени работы программы #14
Цитата Сообщение от monolit Посмотреть сообщение
Не больше, ты хотел написать?)
это ТС так хотел написать, я ему уже 2 поста тонко намекаю, а он в упор не видит
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
01.11.2013, 21:43     Уменьшение времени работы программы
Еще ссылки по теме:

Уменьшать счетчик времени работы - C++
Здравствуйте друзья. У меня тут появился вопросик по С++. Я хочу сделать программу по генераций алгоритма проектирования. И мне надо...

Организовать контроль времени работы программного обеспечения - C++
Консольное приложение Win32 Текст задачи: Организовать контроль времени работы программного обеспечения. Исходные параметры: текущее...

Замер времени работы функции через clock() - C++
Имеется некая функция, требуется замерить время её выполнения. Накидал такой код : #include &lt;iostream&gt; #include &lt;stdint.h&gt; ...

Разработать класс CTime для работы со значениями времени - C++
Ребята, помогите пожалуйста недопрограммитсу))) 1. Разработать класс CTime для работы со значениями времени. Класс должен содержать...

Требуется узнать сколько времени прошло с момента завершения работы приложения - C++
Моей программе необходимо при запуске знать, сколько времени прошло с последнего запуска. Есть ли какие-нибудь интересные идеи, кроме как в...


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

Или воспользуйтесь поиском по форуму:
monolit
185 / 184 / 22
Регистрация: 24.03.2011
Сообщений: 667
Завершенные тесты: 1
01.11.2013, 21:43     Уменьшение времени работы программы #15
Цитата Сообщение от MrGluck Посмотреть сообщение
это ТС так хотел написать, я ему уже 2 поста тонко намекаю, а он в упор не видит
Эт я цитату не оттуда взял просто)
Yandex
Объявления
01.11.2013, 21:43     Уменьшение времени работы программы
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru