Как ускорить код 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

#include  using namespace std; int a[15][15]; int m,n,k,a1, b, c, d; int main(){ cin>> m >> n >> k; for(int i=0; im; i++) a[i][0]=0; for(int i=0; in; i++) a[0][i]=0; for(int i=1; im; i++) { for (int j = 1; j  n; j++) { cin >> a[i][j]; a[i][j] += a[i][j - 1]; } } for(int i=1; im; i++){ for (int j = 1; j  n; j++) { a[i][j] += a[i - 1][j]; } } for (int i=0; ik;i++){ cin >> a1 >> b >> c >> d; cout  [c][d] - a[a1 - 1][d] - a[c][b - 1] + a[a1 - 1][b - 1]  ; } return 0; }

94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
Ответы с готовыми решениями:

Как ускорить код?
Есть код : #include <cstdio> #include <cstring> #include <memory.h> #include <iostream> using.

Как можно ускорить этот код?
Решил поиграться с искривлением экрана, но происходит это как-то медленно, хотелось бы, чтобы.

Как можно ускорить код? Решение выдаёт верное, но по времени не проходит
Как можно ускорить код? Решение выдаёт верное, но по времени не проходит ограничение по времени.

Нужно ускорить код
Мне нужно написать программу, для преобразования коэффициентов системы и столбца свободных членов .

Оптимизация C/C++ кода

Данная статья является вольным переводом статьи Optimizing C++/Code optimization/Faster operations. Оригинал найти можно по ссылке.

Предисловие

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

Часть 1

Расположение членов в структурах/классах

Распологать члены в структурах/классах, стоит таким образом, чтобы наиболее используемые переменные находились в первых 128 байтах, а затем отсортировать от самого большого члена до самого маленького.

Предположим, что есть некая структура:

struct < char msg[400]; double d; int i; >;

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

struct < double d; int i; char msg[400]; >;

На некоторых процессорах адресация элемента более эффективна, если его расстояние от начала структуры меньше 128 байт. В первом примере для адресации полей d и i, с использованием указателя на начало структуры, требуется смещение не менее 400 байт, тогда как во втором, смещения составляет всего несколько байтов, что позволяет использовать более компактные инструкции.

struct < bool b; double d; short s; int i; >;

Если посчитать размер структуры, 1 (bool) + 7 (padding) + 8 (double) + 2 (short) + 2 (padding) + 4 (int), то мы получим 24 байта, 9 из котороых будут использованы для выравнивания, что относительно размера структуры довольно много. Давайте перепишем эту же структуру таким образом:

struct < double d; int i; short s; bool b; >;

Снова проведем подсчет — 8 (double) + 4 (int) + 2 (short) + 1 (bool) + 1 (padding). Теперь наша структура займет 16 байт. Сортировка устранила ненужные вызванные, и поэтому мы получили более компактную структуру.

Преобразование типа с плавающей точкой в целочисленный

Язык C++ не предоставляет примитивную операцию округления чисел с плавающей точкой. Самым простым методом преобразования числа с плавающей точкой x в ближайшее целое число n будет оператор:

n = int(floor(x + 0.5f));

Используя такой метод, если x будет точно посередине между двумя целыми числами, то n будет округлено в большую сторону. Например, 0,5 -> 1; 1,5 -> 2; -0,5 -> 0; -1,5 -> -1;.

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

#if defined(__unix__) || defined(__GNUC__) // For 32-bit Linux, with Gnu/AT&T syntax __asm ("fldl %1 \n fistpl %0 " : "=m"(n) : "m"(x) : "memory" ); #else // For 32-bit Windows, with Intel/MASM syntax __asm fld qword ptr x; __asm fistp dword ptr n; #endif

Код, приведенный выше, округляет x до ближайшего целого числа, но если значение x находится точно между целыми числами, то n будет ближайшим четным целым числом. Например, 0,5 -> 0; 1,5 -> 2; -0,5 -> 0; -1,5 -> -2;.

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

Работа с битами

У величить производительность можно с помощью использования знаний работы с битами, здесь есть коллекция хаков, которые помогут в этом. Часть из приведенных там «трюков», на самом деле, уже используются некоторыми компиляторами, другие же полезны для решения редких проблем, а некоторые, вообще, полезны только на определенных платформах.

Размер ячеек массива

Случается, что размер (можно проверить с помощью sizeof) небольших ячеек массивов или векторов является степенью двойки, а размер больших ячеек — нет. Прямой доступ к ячейке массива выполняется путем умножения индекса на размер ячейки, который является константой. Если второй коэффициент этого умножения равен степени двойки, то такая операция выполняется намного быстрее, так как осуществляется в виде битового сдвига. Аналогично, в многомерных массивах.

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

Однако, при доступе к ячейкам многомерного массива, в котором константа достигает достаточной большой степени двойки, то вы рискуете конфликт данных(data cache contention), что может замедлить вычисление в 10 и более раз. Это происходит только тогда, когда ячейки массива превышают определенный размер, который зависит от кэша данных, но составляет от 1 до 8 КБ. Следовательно, в случае, если алгоритм должен обрабатывать массив, чьи ячейки имеют или могут иметь размер равный 1024 байта, то стоит определить, имеет ли место конфликт данных, чтобы попробовать его избежать.

Например, матрица размером 100 x 512 float — это 100 массивов по 512 эелементов. Каждая ячейка массива первого уровня имеет размер 512 x 4 = 2048 байт, и поэтому она подвержена риску конфликта данных.

Чтобы обнаружить конкуренцию, достаточно добавить еще одну ячейку ( float ) в каждый массив из массива последнего уровня, но при этом обрабатывать те же ячейки, что и раньше, и измерять, существенно ли сокращается время обработки (по меньшей мере на 20% ). Если это так, то вы должны обеспечить более стабильную работу такого улучшения. Для этой цели вы можете использовать один из следующих методов:

• Добавьте один или несколько неиспользуемых елементов в конец каждого массива последнего уровня. Например, массив double a [100] [1024] может стать double a [100] [1026], даже если полезные данные будут находиться также до 1024.
• Храните размеры массива, разделяйте его на прямоугольные блоки и обрабатывайте все ячейки в одном блоке за раз.

Как ускорить код? Оптимизировать?

Как ускорить код?
Решаю задачу на нахождение суммы в подматрице через префиксы. Написал код, но не проходит по.

Как ускорить код?
Есть код : #include <cstdio> #include <cstring> #include <memory.h> #include <iostream> using.

Вывести все правильные скобочные выражения (оптимизировать алгоритм, ускорить работу кода)
есть код, нужно cout и cin перевести на printf и scanf дополнительных библиотек не подключать.

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

Как оптимизировать код?
мне нужно чтобы значения угла перебирались от начального до конечного в зависимости от времени.

Оптимизация C/C++ кода

Данная статья является вольным переводом статьи Optimizing C++/Code optimization/Faster operations. Оригинал найти можно по ссылке. Первая часть лежит здесь.

Часть 2

Префиксный или постфиксный оператор

Префиксный оператор предпочтительнее постфиксного. При работе с примитивными типами префиксные и постфиксные арифметические операции, вероятно, будут иметь одинаковую производительность. Однако с объектами, операторы постфикса могут заставить объект создать собственную копию, чтобы сохранить свое начальное состояние (которое должно быть возвращено в результате операции), а также вызвать побочный эффект операции. Рассмотрим следующий пример:

class IntegerIncreaser < int m_Value; public: /* Postfix operator. */ IntegerIncreaser operator++ (int) < IntegerIncreaser tmp (*this); ++m_Value; return tmp; >; /* Prefix operator. */ IntegerIncreaser operator++ () < ++m_Value; return *this; >; >;

Поскольку операторы постфикса обязаны возвращать неизмененную версию значения, которое увеличивается (или уменьшается) — независимо от того, используется ли результат на самом деле — скорее всего, он сделает копию. Итераторы STL (например) более эффективны при изменении с помощью префиксных операторов.

Встроенные функции

Если вы не используете параметры компилятора для оптимизации всей программы, чтобы компилятор мог встраивать любую функцию, то есть смысл перенести некоторые функции в заголовочные файлы как inline функции, то есть объявить их встроенными.

Если верить руководству (например компилятора gcc «5.34 An Inline Function is As Fast As a Macro»), то inline функция выполняется (так же быстро как макрос) быстрее чем обычная из-за устранения служебных вызовов, но стоит учитывать, что не все функции будут работать быстрее, а некоторые функции, объявленные как inline способны замедлить работу всей программы.

Целочисленное деление на постоянную

Когда вы делите целое число (которое является положительным или равным нулю) на константу, преобразуйте целое число в unsigned.

Например, если s — целое число со знаком, u — целое число без знака, а C — выражение с постоянным целым числом (положительное или отрицательное), операция s / C медленнее, чем u / C, а s% C медленнее, чем u% C. Это проявляется наиболее явно, когда С — степень двойки, но, все же, при делении знак стоит учитываться.

Кстати, преобразование из signed в unsigned ничего не будет нам стоить, поскольку это только другая интерпретация одних и тех же битов. Следовательно, если s — целое число со знаком, которое будет использоваться в дальнейшем, как положительное или ноль, вы можете ускорить его деление, используя следующие выражения: ( unsigned ) s / C и ( unsigned ) s% C.

Использование нескольких массивов вместо полей структуры

Вместо обработки одного массива совокупных объектов параллельно обрабатывайте два или более массива одинаковой длины. Например, вместо следующего кода:

const int n = 10000; struct < double a, b, c; >s[n]; for (int i = 0; i

следующий код может быть быстрее:

const int n = 10000; double a[n], b[n], c[n]; for (int i = 0; i

Используя эту перегруппировку, «a», «b» и «c» могут обрабатываться командами обработки массива, которые значительно быстрее, чем скалярные инструкции. Эта оптимизация может иметь нулевые или неблагоприятные результаты для некоторых архитектур.

Еще лучше перемежать массивы:

const int n = 10000; double interleaved[n * 3]; for (int i = 0; i

PS: Учтите, что каждый случай нужно тестировать, а не оптимизировать преждевременно.