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

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

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

Студворк — интернет-сервис помощи студентам
Добрый вечер. Решил задачу, и решил прогнать по 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
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
01.11.2013, 16:24
Ответы с готовыми решениями:

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

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

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

17
188 / 187 / 46
Регистрация: 24.03.2011
Сообщений: 670
01.11.2013, 18:20
Слишком много циклов. подсчитывать занятые можно и в первом:
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  [ТС]
Цитата Сообщение от 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
Ну, это не означает, что время уменьшилось) Погрешность просто...
Сдается мне, узкое место здесь - чтение данных. В буфер бы раз прочитать, и оттуда уже извлекать(из массива интов, порядок расположения тебе известен...)

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Эксперт С++
 Аватар для MrGluck
8216 / 5047 / 1437
Регистрация: 29.11.2010
Сообщений: 13,453
01.11.2013, 19:27
Цитата Сообщение от Инспектор Котик Посмотреть сообщение
выходит 2.5 секунд, в идеале должно быть не меньше одной
так в идеале же, что еще менять?
0
0 / 0 / 0
Регистрация: 06.09.2013
Сообщений: 9
01.11.2013, 19:34  [ТС]
Цитата Сообщение от monolit Посмотреть сообщение
Ну, это не означает, что время уменьшилось) Погрешность просто...
Сдается мне, узкое место здесь - чтение данных. В буфер бы раз прочитать, и оттуда уже извлекать(из массива интов, порядок расположения тебе известен...)
спасибо. Не уверен что там можно создавать файлы, но попробую и отпишусь.

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

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

Не по теме:

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

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

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

Не по теме:


2.5 не меньше 1

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

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

Не по теме:

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

1
Неэпический
 Аватар для Croessmah
18144 / 10728 / 2066
Регистрация: 27.09.2012
Сообщений: 27,026
Записей в блоге: 1
02.11.2013, 01:21
Экзотика
ВНИМАНИЕ!!! В коде черт глаза сломает!!!
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
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
02.11.2013, 01:21
Помогаю со студенческими работами здесь

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

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
18
Ответ Создать тему
Новые блоги и статьи
PhpStorm 2025.3: WSL Terminal всегда стартует в ~
and_y87 14.12.2025
PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .
Access
VikBal 11.12.2025
Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.
Новый ноутбук
volvo 07.12.2025
Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro
Музыка, написанная Искусственным Интеллектом
volvo 04.12.2025
Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .
От async/await к виртуальным потокам в Python
IndentationError 23.11.2025
Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов
Argus19 22.11.2025
Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .
Сколько Государство потратило денег на меня, обеспечивая инсулином.
Programma_Boinc 20.11.2025
Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .
Ломающие изменения в C#.NStar Alpha
Etyuhibosecyu 20.11.2025
Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .
Мысли в слух
kumehtar 18.11.2025
Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .
Создание Single Page Application на фреймах
krapotkin 16.11.2025
Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru