Как можно оптимизировать код?

@Petrign · Регистрация: 30.03.2021

Студворк — интернет-сервис помощи студентам

В первые годы существования кино технология изготовления киноплёнки была, что естественно, на невысоком уровне. Так что «артефакты» на экране были самым обычным делом.

После отсмотра только что снятой сцены известный байтландский режиссёр предъявил претензии поставщикам плёнки из-за большого количества артефактов на экране. Согласно договору, плёнка считается бракованной, если в некотором прямоугольнике, каждая из сторон которого параллельна сторонам экрана и имеет длину не менее m, доля артефактов превышает определённое значение.

Перед встречей с представителем поставщика режиссёр хочет выяснить, чему равен максимум соответствующей доли артефактов для заданного кадра.

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
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
 
int main()
{
    int u = 0, d = 0, m = 0;
    std::cin >> u >> d >> m;
    std::string arts = "";
    std::cin>>arts;
    float max = 0.0f;
    std::string kadr[u];
    int ansdef = 0;
    int maxs = 0;
    for (int i = 0; i < u; i++)
    {
        std::cin>>kadr[i];
    }
    for (int i = m; i <= std::min(u,d); i++)
    {
        for (int ij = m; ij <= std::min(u,d); ij++)
        {
        for (int j = 0; j <= u-i; j++)
        {
            for (int k = 0; k <= d-ij; k++)
            {
                int artscur = 0;
                for (int h = 0; h < i; h++)
                {
                    for (int w = 0; w < ij; w++)
                    {
                        if (arts.find(kadr[j+h][k+w]) != std::string::npos)
                        {
                            artscur++;
                        }
                    }
                }
                if ((artscur*1.0f)/(i*ij) >= max)
                {
                    max = (artscur*1.0f)/(i*ij);
                    ansdef = artscur;
                    maxs = i*ij;
                }
            }
        }
        }
    }
    std::cout << ansdef << "/" << maxs << "\n";
    return 0;
}

@Bleach163 · 11.07.2022, 09:27

Petrign, тут бы уже не помешало увидеть точное условие задачи и ограничения по вводу, времени и памяти, а то сейчас как окажется, что мой вариант всё равно не проходит ни по времени, ни по памяти.

Пару моментов:

1. Народ, вы пробовали кешировать вычисления?
Зачем вы храните массив строк, если вам достаточно булевой матрицы?
Да и подсчёт тоже можно кешировать... В некотором виде.
Моя мысль простая: я создаю дополнительную матрицу, в которой counts[i][j] хранит кол-во битых пикселей в прямоугольнике от [0][0] до [i][j]. Кол-во битых пикселей в прямоугольнике от [k][l] до [i][j] можно получить по формуле:
counts[i][j] + counts[k-1][l-1] - counts[i][l-1] - counts[k-1][j]

2. Очень прикольно, что вы просто забили на длину строки и записали всё в std::string[].
std::string хранит указатель на строку, а разыменовывание занимает время. Лучше всего когда вы идёте по элементам расположенным в памяти подряд.
Была бы у вас обычная прога, я бы забил на это, но раз вы гоняетесь за скоростью при 6 вложенных циклах, то я добавил немного одномерных массивов и арифметки указателей.

Вернул ввод к изначальному виду: кол-во строк, длина строки, минимальная длина стороны прямоугольника, битые пиксели, матрица

Code
1
2
3
4
5
6
7
8
9
10
11
12
10 10 3
0123456789
abcdefghik
ab23efghik
abcdefghik
abcde12hik
abcde6ghik
ab2345ghik
abcdefghik
abcdefghik
abcd123hik
abcd456hik

Код с отладочной инфой типа найденного прямоугольника и времени 1000 повторов.

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

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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
#include <iostream>
#include <fstream>
#include <string>
#include <limits>
#include <chrono>
#include <cstdint>
 
typedef uint32_t size_type; // Для размеров массива/индексов
typedef uint32_t diff_type; // Для количества элементов в прямоугольнике
static_assert(std::numeric_limits<size_type>::max() <= std::numeric_limits<diff_type>::max(), "diff_type should be at least as large as size_type");
 
bool* input(size_type& rows, size_type& cols, size_type& min, std::istream& fin = std::cin);
void output(bool* matr, size_type rows, size_type cols, size_type min, std::ostream& fout = std::cout);
void find(bool* matr, size_type rows, size_type cols, size_type min, size_type& i0, size_type& j0, size_type& ik, size_type& jk, diff_type& bad);
diff_type* get_counts(bool* matr, size_type rows, size_type cols);
 
int main()
{
    std::ifstream fin; fin.open("input.txt");
    size_type rows, cols, min;
    bool* matr = input(rows, cols, min, fin);
    fin.close();
 
    output(matr, rows, cols, min);
 
    size_type i0, j0, ik, jk, bad;
    int I = 0;
    std::cout << "\n\n";
    auto start = std::chrono::high_resolution_clock::now();
    while (I++ - 1000)
        find(matr, rows, cols, min, i0, j0, ik, jk, bad);
    auto finish = std::chrono::high_resolution_clock::now();
    auto time = std::chrono::duration_cast<std::chrono::duration<double, std::milli>>(finish - start);
    delete[] matr;
 
    std::cout << "\n\nDebug: Time: " << time.count() << " ms\n\n";
    std::cout << "Debug: Rect: (" << j0 << "; " << i0 << ") (" << jk << "; " << ik << ")" << '\n';
    std::cout << '\n' << bad << '/' << (ik - i0 + 1) * (jk - j0 + 1);
    std::cin.get();
    return 0;
}
 
 
 
bool* input(size_type& rows, size_type& cols, size_type& min, std::istream& fin)
{
    fin >> rows >> cols >> min >> std::ws;
    std::string delim; std::getline(fin, delim);
 
    bool* matr = new bool[rows * cols];
    bool* it_matr = matr;
    bool* end_matr = matr + rows * cols;
    while (it_matr != end_matr)
    {
        char tmp; fin >> tmp;
        bool res = delim.find(tmp) != std::string::npos;
        *it_matr++ = res;
    }
 
    return matr;
}
 
 
 
void output(bool* matr, size_type rows, size_type cols, size_type min, std::ostream& fout)
{
    fout << rows << "   " << cols << "   " << min << '\n';
    bool* it_matr = matr;
    bool* end_matr = matr + rows * cols;
    while (it_matr != end_matr)
    {
        if (it_matr != matr)
            fout << '\n';
 
        bool* end_row = it_matr + cols;
        while (it_matr != end_row)
            fout << *it_matr++;
    }
}
 
 
 
void find(bool* matr, size_type rows, size_type cols, size_type min, size_type& i0, size_type& j0, size_type& ik, size_type& jk, diff_type& bad)
{
    i0 = j0 = ik = jk = bad = 0;
    diff_type worst_area = 1;
    diff_type* counts = get_counts(matr, rows, cols);
 
    for (size_type beg_row = 0; beg_row < rows; beg_row++)
    {
        for (size_type beg_col = 0; beg_col < cols; beg_col++)
        {
            for (size_type end_row = beg_row + min - 1; end_row < rows; end_row++)
            {
                for (size_type end_col = beg_col + min - 1; end_col < cols; end_col++)
                {
                    diff_type count = counts[end_row * cols + end_col];
                    if (beg_row > 0 && beg_col > 0)
                        count += counts[(beg_row - 1) * cols + beg_col - 1];
                    if (beg_row > 0)
                        count -= counts[(beg_row - 1) * cols + end_col];
                    if (beg_col > 0)
                        count -= counts[end_row * cols + beg_col - 1];
 
                    diff_type area = (end_row - beg_row + 1) * (end_col - beg_col + 1);
 
                    if (count * worst_area > bad * area || count * worst_area == bad * area && count > bad) {
                        worst_area = area;
                        bad = count;
                        i0 = beg_row;
                        j0 = beg_col;
                        ik = end_row;
                        jk = end_col;
                    }
                }
            }
        }
    }
 
    delete[] counts;
}
 
 
 
diff_type* get_counts(bool* matr, size_type rows, size_type cols)
{
    diff_type* counts = new diff_type[rows * cols];
    diff_type* it_counts = counts;
    diff_type* end_counts = counts + rows * cols;
    bool* it_matr = matr;
 
    while (it_counts != end_counts)
    {
        diff_type* end_row = it_counts + cols;
        *it_counts++ = *it_matr++;
        while (it_counts != end_row)
            *it_counts++ = *(it_counts - 1) + *it_matr++;
    }
 
    it_counts = counts + cols;
 
    while (it_counts != end_counts)
        *it_counts++ = *it_counts + *(it_counts - cols);
 
    return counts;
}

Код чисто по заданию:

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

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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include <iostream>
#include <string>
#include <cstdint>
 
typedef uint32_t size_type; // Для размеров массива/индексов
typedef uint32_t diff_type; // Для количества элементов в прямоугольнике
 
bool* input(size_type& rows, size_type& cols, size_type& min);
void find(bool* matr, size_type rows, size_type cols, size_type min, diff_type& worst_area, diff_type& worst_score);
diff_type* get_counts(bool* matr, size_type rows, size_type cols);
 
int main()
{
    size_type rows, cols, min;
    bool* matr = input(rows, cols, min);
 
    diff_type worst_area, worst_score;
    find(matr, rows, cols, min, worst_area, worst_score);
    delete[] matr;
 
    std::cout << worst_score << '/' << worst_area;
}
 
 
 
bool* input(size_type& rows, size_type& cols, size_type& min)
{
    std::cin >> rows >> cols >> min >> std::ws;
    std::string delim; std::getline(std::cin, delim);
 
    bool* matr = new bool[rows * cols];
    bool* it_matr = matr;
    bool* end_matr = matr + rows * cols;
    while (it_matr != end_matr)
    {
        char tmp; std::cin >> tmp;
        bool res = delim.find(tmp) != std::string::npos;
        *it_matr++ = res;
    }
 
    return matr;
}
 
 
 
void find(bool* matr, size_type rows, size_type cols, size_type min, diff_type& worst_area, diff_type& worst_score)
{
    diff_type* counts = get_counts(matr, rows, cols);
    worst_area = 1;
    worst_score = 0;
 
    for (size_type beg_row = 0; beg_row < rows; beg_row++)
    {
        for (size_type beg_col = 0; beg_col < cols; beg_col++)
        {
            for (size_type end_row = beg_row + min - 1; end_row < rows; end_row++)
            {
                for (size_type end_col = beg_col + min - 1; end_col < cols; end_col++)
                {
                    diff_type count = counts[end_row * cols + end_col];
                    if (beg_row > 0 && beg_col > 0)
                        count += counts[(beg_row - 1) * cols + beg_col - 1];
                    if (beg_row > 0)
                        count -= counts[(beg_row - 1) * cols + end_col];
                    if (beg_col > 0)
                        count -= counts[end_row * cols + beg_col - 1];
 
                    diff_type area = (end_row - beg_row + 1) * (end_col - beg_col + 1);
 
                    if (count * worst_area > worst_score * area || count * worst_area == worst_score * area && count > worst_score) {
                        worst_area = area;
                        worst_score = count;
                    }
                }
            }
        }
    }
 
    delete[] counts;
}
 
 
 
diff_type* get_counts(bool* matr, size_type rows, size_type cols)
{
    diff_type* counts = new diff_type[rows * cols];
    diff_type* it_counts = counts;
    diff_type* end_counts = counts + rows * cols;
    bool* it_matr = matr;
 
    while (it_counts != end_counts)
    {
        diff_type* end_row = it_counts + cols;
        *it_counts++ = *it_matr++;
        while (it_counts != end_row)
            *it_counts++ = *(it_counts - 1) + *it_matr++;
    }
 
    it_counts = counts + cols;
 
    while (it_counts != end_counts)
        *it_counts++ = *it_counts + *(it_counts - cols);
 
    return counts;
}

Добавлено через 12 минут
О, нашёл ограничения по вводу:

В первой строке входа заданы три целых числа u, d и m — количество точек на экране по вертикали, количество точек на экране по горизонтали, длина стороны минимального квадрата m (1 ≤ u,d ≤ 50, 1 ≤ m ≤ min(u,d)). Следующая строка содержит от 1 до 26 попарно различных заглавных латинских букв, соответствующих артефактам на экране.

Далее следует описание кадра. Каждая из последующих u строк содержит по d заглавных латинских букв от “A” до “Z”, задающих яркость точек на экране (при этом, если буква входит в список обозначений артефактов, то в данной точке содержится артефакт).

Так что по идее должен уложиться по времени и, надеюсь, по памяти.

Новые блоги и статьи Все статьи Все блоги /
Поиск произведения положительных чётных чисел в последовательности Maks 18.07.2026 Решение задачи по прикладной информатике средствами 1С. Задача: Дана произвольная последовательность целых чисел. Найти произведение положительных четных чисел данной последовательности. . . .	Обработка трёх чисел: утроение и возведение в степень Maks 18.07.2026 Решение задачи по прикладной информатике средствами 1С. Задача: Даны три действительных числа. Утроить те из них, значения которых неотрицательны, и возвести в четвертую степень отрицательные. . . .	Расчёт стоимости яблок по весу Maks 18.07.2026 Решение задачи по прикладной информатике средствами 1С. Задача: Написать программу вычисления стоимости некоторого количества (по весу) яблок. Решение: Создан документ, с табличной частью. . .	сукцессия 30. Фосфорный и азотный замки по "честному" закону лимитирования Либиха anaschu 16.07.2026 Основные достижения за последние дни 1. Механизм отложенного высвобождения фосфора Добавлен специальный пул для медленного разложения меланизированных гиф ЕСМ Реализована разная скорость. . .
Запрет пометки на удаление и отмены проведения Maks 16.07.2026 Алгоритм из решения ниже реализован на нетиповом документе "ПутевойЛист" разработанного в КА2. Задача: запретить помечать на удаление и отменять проведения путевого листа при условии, если он сдан. . .	Как надо было делать правильно - вообще не слушать ИИ, его дело - текст. Hrethgir 15.07.2026 А вообще надо было делать не так, чтобы не исправлять ошибку https:/ / www. cyberforum. ru/ blogs/ 223907/ 10996. html , правильно было : удалил кнопку, а потом добавил её. Всё это стресс конечно. Почему?. . .	Знаете, от чего появляется стресс? kumehtar 15.07.2026 Стресс появляется оттого, что вы, зная как поступить правильно, делаете наоборот. Ларри Уингет	Нас бьют, а мы крепчаем? Какая чушь! kumehtar 15.07.2026 Вот это вот бытующее мнение, что человек меняется только под действием проблем, всегда считал вредоносным. Поверь, от проблем у людей появляются не изменения, а нервное расстройство и ПТСР. А. . .