Как ускорить время выполнения трудоемких расчетов

Я пытаюсь написать функцию для преобразования изображения в символы и цвета для консоли Windows. На данный момент вычисление занимает около 13 секунд для изображения с разрешением 700×700 пикселей, но это время нежелательно, особенно когда я планирую сделать функцию более сложной, чтобы учитывать формы символов.

Каковы некоторые методы для ускорения тяжелых вычислений и циклов, как показано ниже в C ++? Мне порекомендовали несколько потоков, SIMD и встроенную сборку, но как мне улучшить эти функции, как показано ниже?

Это текущий код, который я использую.

unsigned char characterValues[256] = { 0 };

// This operation can be done ahead of time when the program is started up
{
ResourceInputStream in = ResourceInputStream();
// This image is the font for the console. The background color is black while the foreground color is white
in.open(BMP_FONT, 2); // 2 is for RT_BITMAP, BMP_FONT is a resource
if (in.isOpen()) {
auto bmp = readBitmap(&in, true);
in.close();
for (int x = 0; x < bmp->size.x; x++) {
for (int y = 0; y < bmp->size.y; y++) {
int charIndex = (x / 8) + (y / 12) * 16;
if (bmp->pixels[x][y].r == 255)
characterValues[charIndex]++;
}
}
}
}
// This operation is for asciifying the image
{
FileInputStream in = FileInputStream();
in.open(R"(image-path.bmp)");
if (in.isOpen()) {
auto bmp = readBitmap(&in, false);
in.close();

auto image = /* make default image here */
Point2I imageSize = (Point2I)GMath::ceil((Point2F)bmp->size / Point2F(8.0f, 12.0f));
int totalImageSize = imageSize.x * imageSize.y;
image->resize(imageSize);
auto palette = /* get palette of 16 colors here */

// Iterate through each (character area)
for (int imgx = 0; imgx < imageSize.x; imgx++) {
for (int imgy = 0; imgy < imageSize.y; imgy++) {

// Read image color value
int r = 0, g = 0, b = 0;
int totalRead = 0;
// Read each pixel inside the bounds of a single character
for (int px = 0; px < 8; px++) {
for (int py = 0; py < 12; py++) {
Point2I p = Point2I(imgx * 8 + px, imgy * 12 + py);
if (p < bmp->size) {
r += bmp->pixels[p.x][p.y].r;
g += bmp->pixels[p.x][p.y].g;
b += bmp->pixels[p.x][p.y].b;
totalRead++;
}
}
}
Color imageValue = Color(r / totalRead, g / totalRead, b / totalRead);

// A combo of a character and foreground/background color
Pixel closestPixel = Pixel();
float closestScore = std::numeric_limits<float>().max();
for (int col = 1; col < 255; col++) {
unsigned char f = getFColor(col);
unsigned char b = getBColor(col);
for (int ch = 1; ch < 255; ch++) {
// Calculate values
Color value = Color(
(palette[f].r * characterValues[ch] + palette[b].r * (TOTAL_CHARACTER_VALUE - characterValues[ch])) / TOTAL_CHARACTER_VALUE,
(palette[f].g * characterValues[ch] + palette[b].g * (TOTAL_CHARACTER_VALUE - characterValues[ch])) / TOTAL_CHARACTER_VALUE,
(palette[f].b * characterValues[ch] + palette[b].b * (TOTAL_CHARACTER_VALUE - characterValues[ch])) / TOTAL_CHARACTER_VALUE
);
// Add up score here
float score =
(float)((int)value.r - (int)imageValue.r) * (float)((int)value.r - (int)imageValue.r) +
(float)((int)value.g - (int)imageValue.g) * (float)((int)value.g - (int)imageValue.g) +
(float)((int)value.b - (int)imageValue.b) * (float)((int)value.b - (int)imageValue.b);
if (score < closestScore) {
closestPixel = Pixel((unsigned char)ch, (unsigned char)col);
closestScore = score;
}
}
}
// Set the character/color combo here
}
}
}
}

0

Решение

у вас есть цикл x и вложенный цикл y, вы уверены, что это порядок байтов в памяти? Это может быть, но вы всегда можете попробовать наоборот, если это поможет.

// could be faster, depending on data structure
for (int y = 0; y < bmp->size.y; y++) {
for (int x = 0; x < bmp->size.x; x++) {

но так как индексы bmp идут [x] [y], похоже, это данные первого столбца, что нечетно.

Есть также дорогостоящие разделения в вашем внутреннем цикле. Вы можете выполнять любые циклически инвариантные вычисления вне каждого цикла:

 for (int x = 0; x < bmp->size.x; x++) {
int charIndex_x = (x / 8);
for (int y = 0; y < bmp->size.y; y++) {
int charIndex = charIndex_x + (y / 12) * 16;
// other stuff

Его можно еще улучшить, но вы просто избежали выполнения почти 65536 операций деления при выполнении этого для растрового изображения 256×256.

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

 for (int x = 0; x < bmp->size.x; x++) {
int charIndex_x = (x / 8);
auto current_pixel = &bmp->pixels[x][0];
for (int y = 0; y < bmp->size.y; y++) {
int charIndex = charIndex_x + (y / 12) * 16;
if (*current_pixel.r == 255)
characterValues[charIndex]++;
++current_pixel;

И увеличить его во внутреннем цикле. На самом деле вы могли бы переместить настройку current_pixel, прямо за пределами цикла x, но у меня была ситуация, когда это было помедленнее так как он должен поддерживать больше переменных в памяти. Обычно вы хотите локальные переменные во внутреннем цикле, если это возможно. Перемещение вычислений вне циклов ускоряет процесс, но использует больше памяти ЦП, а это может быть медленнее из-за манипулирования большим количеством сохраненных значений.

последнее, на что следует обратить внимание, это то, что каждый раз, когда вы проходите внутренний цикл, вы проверяете, меньше ли значение y, чем «bmp-> size.y», это включает в себя поиск bmp, затем ссылку на size, затем ссылку на size.y, который равен трем. операций, происходящих 65536 раз для битового массива 256×256. Вы можете записать размер y в локальную переменную, прежде чем она понадобится:

 for (int x = 0; x < bmp->size.x; x++) {
int charIndex_x = (x / 8);
auto current_pixel = &bmp->pixels[x][0];
int bmp_size_y = bmp->size.y;
for (int y = 0; y < bmp_size.y; y++) {
int charIndex = charIndex_x + (y / 12) * 16;
if (*current_pixel.r == 255)
characterValues[charIndex]++;
++current_pixel;

Вы можете вообще переместить его за пределы цикла x, чтобы избежать установки значения 256 раз, так как bmp-> size.y никогда не меняется, но экономия для этого очень мала, и это может даже замедлить работу, так как это приведет к дополнительный регистр, который может означать, что программе нужно манипулировать большим количеством вещей в памяти.

Память процессора как виртуальная память на вашем ПК с Windows. Если используется слишком много, все замедляется, потому что это разбивает содержимое на диск, но наличие большего количества в памяти также может ускорить процесс, потому что ему не нужно постоянно искать вещи с диска. Кодирование аналогичный в этом случае локальные переменные могут храниться только в ЦП, избегая необходимости искать их из памяти, но слишком много локальных переменных могут перегружать ЦП, что означает, что ему необходимо продолжать манипулировать ими, как это делает виртуальная память. Поэтому сделайте локальные переменные максимально локальными, чтобы избежать их чрезмерного использования. Вы должны всегда регистрировать любые изменения, которые вы делаете, чтобы увидеть, действительно ли они помогли.

~~~

Что касается вашего другого цикла, у вас есть много сложных повторных вычислений во внутреннем цикле:

bmp->pixels[p.x][p.y]

вычисляется три раза, и это включает разыменование указателя, разыменование двух членов (p.x и p.y), затем разыменование двумерного массива (которое в лучшем случае представляет собой умножение и сложение, а затем разыменование указателя). Это как минимум 6 атомных вычислений, просто чтобы получить ссылку на этот пиксель каждый раз.

Вместо этого вы можете пойти:

auto current_pixel = bmp->pixels[p.x][p.y];

Более того, вы вычисляете Point2I, а затем проверяете, находятся ли значения x и y этого значения в пределах bmp. Вам вообще не нужен Point2I, просто рассчитайте размеры x и y и сравните их с размерами bmp x и y по отдельности.

Вычислите границы x во внешнем цикле, выполните проверку if для x там, и вы вообще не будете попадать во внутренний цикл, если x выходит за пределы. Объедините это, избегая необходимости создавать или индексировать структуры во внутреннем цикле, и вы получите:

           for (int px = 0; px < 8; px++) {
int p_x = imgx * 8 + px;
if(p_x < bmp->size.x) {
for (int py = 0; py < 12; py++) {
int p_y = imgy * 12 + py;
if (p_y < bmp->size.y) {
auto pixel = bmp->pixels[p_x][p_y];
r += pixel.r;
g += pixel.g;
b += pixel.b;
totalRead++;
}
}
}
}
2

Другие решения

for (int x = 0; x < bmp->size.x; x++) {
for (int y = 0; y < bmp->size.y; y++) {

Запустите оба этих цикла с верхнего значения, т.е. bmp->size.x-1 а также bmp->size.y-1 соответственно и запускай их вниз в ноль. Таким образом, вы оцениваете граничные условия только один раз за цикл вместо каждой итерации.

int charIndex = (x / 8) + (y / 12) * 16;

Не вычисляйте это, если не собираетесь использовать это, то есть поместите это в следующее if блок.

1

По вопросам рекламы ammmcru@yandex.ru
Adblock
detector