«Проходной балл» Как ускорить работу кода и устранить недоработку?
Помогите разобраться где может быть недоработка и каким образом можно ускорить работу кода?
#include #include #include using namespace std; struct Student < char fam[20]; char name[20]; int howMOc = 0; //как много оценок(размер для массива *ocenki ) int* ocenki; //помещаем double srBal = 0; >; int main() < freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); setlocale(0, "rus"); int howMStud = -1; int howMSubj; int pasScore = -1; //прох балл cin >> howMStud; if ((howMStud > 10000) || (howMStud < 1)) exit(0); Student* postup = new Student[howMStud]; for (int i = 0; i < howMStud; i++) < cin >> postup[i].fam; cin >> postup[i].name; cin >> howMSubj; if ((howMSubj > 50) || (howMSubj < 1)) exit(0); postup[i].howMOc = howMSubj; postup[i].ocenki = new int[howMSubj]; for (int j = 0; j < howMSubj; j++) < cin >> postup[i].ocenki[j]; postup[i].srBal += postup[i].ocenki[j]; >//for j postup[i].srBal = postup[i].srBal / howMSubj; >//for i cin >> pasScore; //Вывод for (int i = 0; i < howMStud; i++) < if (postup[i].srBal >= pasScore) < cout //end if >//end i //system("pause"); return 0; > 
Отслеживать
219k 15 15 золотых знаков 119 119 серебряных знаков 230 230 бронзовых знаков
задан 2 окт 2016 в 12:51
Vladislav Solopov Vladislav Solopov
530 1 1 золотой знак 4 4 серебряных знака 24 24 бронзовых знака
3 ответа 3
Сортировка: Сброс на вариант по умолчанию
Из того что я вижу в этом коде:
- (WA) при вычислении среднего от 50: 10^9 10^9 . 10^9 вы получите целочисленное переполнение, рекомендую использовать тип long long (у вас может и 64 бита но не факт что там так же).
- (TL) работа с cin/cout оочень медленная. Есть разные способы исправить это, можете читать через scanf/printf, можно использовать магические строки cout.tie(0); iostream::sync_with_stdio(0);
- (WA/UB) размер строки 20 символов, но не 21 (а нуль символ?)
- Отвыкайте использовать динамическую память на олимпиадах без реальной необходимости, лучше задать массив сразу размера 10.000 и всё. Больше не меньше.
- (ML) не храните массив с оценками только само среднее значение, массив используйте общий для всех студентов.
Так код с виду рабочий.
Отслеживать
ответ дан 2 окт 2016 в 13:29
9,844 3 3 золотых знака 29 29 серебряных знаков 42 42 бронзовых знака
3. Так размер массива на 20 символов
2 окт 2016 в 13:35
@VladislavSolopov да 20 символов, а куда 0 символ строки запихать? Вы же понимаете что такое char *?
2 окт 2016 в 13:37
@VladislavSolopov \0(null-байт) в конце строки всегда есть 😀
2 окт 2016 в 13:38
@VladislavSolopov статью читайте) если кратко то отключили синхронизацию с scanf/printf
2 окт 2016 в 14:05
@pavel Я тестировал 🙁 Это вообще больное место у MS — по выводу на консоль их обставляют все, даже такая древность, как Watcom.
2 окт 2016 в 16:55
Откровенно говоря, странно, что проблема по времени. Если это на e-olymp, то там же дают целую секунду — это же вечность 🙂 Вот этот код просвистел на ура:
#include #include #include #include #include using namespace std; struct Data < char name[48]; unsigned int cnt; unsigned int avg; unsigned int rem; Data():cnt(0),avg(0),rem(0)<>; >; int main(int argc, const char * argv[]) < vectords; int N = 0; ifstream in("input.txt"); in >> N; string s; s.reserve(24); ds.reserve(N); for(int i = 0; i < N; ++i) < Data d; in >> s; strcpy(d.name,s.c_str()); in >> s; strcat(d.name," "); strcat(d.name,s.c_str()); in >> d.cnt; for(int j = 0; j < d.cnt; ++j) < unsigned int v; in >> v; d.rem += v%d.cnt; d.avg += v/d.cnt; > ds.push_back(d); > int K; in >> K; ofstream out("output.txt"); for(int i = 0; i < N; ++i) < if (ds[i].avg + ds[i].rem/ds[i].cnt >= K) out > Оптимизация 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: Учтите, что каждый случай нужно тестировать, а не оптимизировать преждевременно.
Оптимизация кода на С++
Иногда бывает сложно решить, какую конструкцию лучше использовать i++ или ++i, либо выбрать между конструкцией if-else и switch. В этой статье, написанной специально для сообщества iT works, представлены наиболее реальные средства оптимизации кода, которые должен знать каждый профессиональный программист.
Некоторые считают, что времена оптимизации на уровне кода прошли навсегда, однако это не так. Сейчас существует множество платформ в которых нет таких могущественных компиляторов как в Microsoft Visual Studio. Например шейдерные языки (hlsl, glsl) или код для CUDA, PlayStation3, SPU или мобильные платформы. В зависимости от организации кода, может в десятки раз отличаться его эффективность иногда из-за неэффективности компилятора, на чаще из-за доступа к памяти.
Программируя для разных платформ изучите возможности вашего компилятора и особенности архитектуры процессора (если вы пишите для конкретной консоли). Проведите тесты производительности разных вариантов оптимизации. Часто сложно предполагать, какие именно способы будут наиболее эффективными. А эта статья подскажет разные приемы, которые могут вам помочь. Однако не следует оптимизировать слепо, без предварительного анализа и профилирования. Помните, что преждевременная оптимизация — это зло.
Если вы являетесь программистом в VS под Windows, то скорее всего со многими описанными приемами оптимизации компилятор эффективно справится. Обратите внимание на пункты работы с памятью, а так же я рекомендую ознакомиться с техникой Data oriented design. Некоторые советы по ее использования ищите в статье Методы оптимизации памяти.
- Используйте векторизацию данных и векторные команды их обработки (например SSE в CPU или упаковывайте данные если используете шейдеры или CUDA). Это позволит использовать SIMD (Single Instruction, Multiple Data) архитектуру, что значительно повысит скорость вычислений. Если вы решите использовать этот метод, то не забывайте про выравнивание данных в памяти.
- Эффективнее складывать и умножать в перемешку, чем сначала все сложить, а потом все умножить. Это происходит от того, что сложение и умножение выполняются разными модулями процессора и могут выполняться одновременно.
1 2 3 4 5 6 7 8 9 10 11 12 13 14
int [float, double, single, unsigned] a,b,c,k,m,n,t,f1,f2,f3,g1,g2,g3; a = b + с; k = m + n; t = a + k; f1 = f2 * f3; g1 = g2 * g3; Менее эффективно чем: a = b + с; f1 = f2 * f3; k = m + n; g1 = g2 * g3; t = a + k;
1 2 3
const float a = 100.0f; float some1 = some3 * 1.0f / a; float some2 = some4 * 1.0f / a;
более эффективно написать не:
1 2 3
const float a_inv = 1.0f / a; some1 = some3 * a_inv; some2 = some4 * a_inv;
some1 = some3 * (1.0f / a); some2 = some4 * (1.0f / a);
Почему это будет эффективнее? Операторы с равным приоритетом выполняются последовательно. Это значит, что будет выполнено сначала умножение, а затем деление. Если же обрамить операцию деления в скобки, то ее выполнит компилятор, а в реальном времени будет выполняться только операция умножения. Что качается отличий варианта 3 от варианта 2, то в 3-ем варианте не создается дополнительной переменной, нет нужны глядя на код думать о том, что это за переменная. А эффективность 2-го и 3-го варианты будет одинаковой.
1 2 3
if( a && b ) - нужно первым ставить менее вероятное условие, для большей эффективности if( a || b ) - нужно первым ставить более вероятное условие, для большей эффективности if( Func1() && Func2() ) - нужно ставить более быстрый оператор первым
1 2 3 4 5 6 7 8
void Func( int* a ) int b = 10; Следующие строки одинаковые по эффективности (по времени выполнения): b = 100; *a = 100; >
Это происходит по тому, что доступ к стековой переменной осуществляется по указателю на стек. Тоже идет разыменование указателя.
1 2 3
int a[ 1000 ]; for( int i =0; i1000; ++i ) a[ i ] = 50;
Значительно эффективнее будет:
Оптимизация кода
Оптимизируя исполняемый файл, можно добиться баланса между быстрым выполнением и небольшим размером кода. В этом разделе обсуждаются механизмы, предоставляемые Visual Studio для оптимизации кода.
Возможности языка
В следующих разделах описываются некоторые функции оптимизации в C/C++.
Прагмы и ключевые слова оптимизации
Список ключевых слов и прагм, которые можно использовать в коде для повышения производительности.
Параметры компилятора, упорядоченные по категориям
Список параметров компилятора /O, которые влияют на скорость выполнения или размер кода.
Декларатор ссылки Rvalue: &&
Ссылки rvalue поддерживают реализацию семантики перемещения. Если для реализации библиотек шаблонов используется семантика перемещения, производительность приложений, использующих эти шаблоны, может значительно повыситься.
Прагма optimize
Если оптимизированный раздел кода вызывает ошибки или замедление, можно использовать прагму optimize, чтобы отключить оптимизацию для этого раздела.
Заключите код между двумя прагмами, как показано ниже:
#pragma optimize("", off) // some code here #pragma optimize("", on) Рекомендации по программированию
При компиляции кода с оптимизацией можно заметить дополнительные предупреждения. Такое поведение является ожидаемым, так как некоторые предупреждения относятся только к оптимизированному коду. Обращайте внимание на эти предупреждения, чтобы избежать многих проблем с оптимизацией.
Парадоксально, но оптимизация программы для ускорения может привести к снижению скорости выполнения кода. Это обусловлено тем, что некоторые оптимизации для скорости увеличивают размер кода. Например, функции встраивания устраняют издержки, вызванные вызовами функций. Однако встраивание слишком большого объема кода может сделать программу настолько большой, что число ошибок страниц виртуальной памяти увеличится. Таким образом, выигрыш в скорости, полученный при исключении вызовов функций, будет компенсирован обменом памятью.
В следующих разделах рассматриваются оптимальные методы программирования.
Рекомендации по оптимизации критичного по времени кода
Улучшенные методы программирования могут повысить производительность. В этом разделе предлагаются приемы программирования, которые помогут обеспечить удовлетворительную производительность критичного по времени кода.
Рекомендации по оптимизации
Общие рекомендации по эффективной оптимизации приложения.
Отладка оптимизированного кода
Поскольку оптимизация может изменить код, созданный компилятором, рекомендуется выполнить отладку приложения и оценить его производительность, а затем оптимизировать код.
В следующих разделах представлена информация о том, как отладить сборки выпуска.
- Отладка в Visual Studio
- Практическое руководство. Отладка оптимизированного кода
- Почему может уменьшиться точность чисел с плавающей запятой
В следующих разделах содержатся сведения о том, как оптимизировать сборку, загрузку и выполнение кода.
- Улучшение производительности компилятора
- При использовании имен функций без скобок () код не создается
- Оптимизация встроенного кода на языке ассемблера
- Настройка оптимизации компилятора для проекта ATL
- Методы увеличения скорости загрузки клиентского приложения