пятница, 7 декабря 2012 г.

Сокращение кода на C++ для acmp.ru


ПОСЛЕДНЕЕ ОБНОВЛЕНИЕ: 01.02.2016

Предисловие


Добрый день.
Меня зовут Хворых Павел и я решаю задачи на acmp.ru. В отличие от других сайтов, на acmp лучшими признаются не самые быстрые и экономные программы, а те, которые имеют наикратчайший исходный код. В этой статье я расскажу о некоторых приемах сокращения кода на C++.

В самом начале хочу обговорить несколько важных моментов.
  1. Необходимо знание C++ на уровне немного выше "Hello, World" (потоки, STL), а также отсутствие рвотного рефлекса и желания убивать при взгляде на строчку
    a[y+i%2-~x*60] += 1-i++%2*2;.
  2. При объяснении многих вещей мне приходится опускать многие моменты, так как объяснение каждого из них может вылиться в статью не меньших размеров. Например, я очень неаккуратно ввожу понятия "выражение" и "lvalue". Материалы по этим моментам достаточно легко найти в интернете, но это не требуется для понимания статьи.
  3. Приемы, описанные здесь, абсолютно бесполезны за пределами acmp. Более того, они вредны, так как представляют собой полное игнорирование соглашений о правильном программировании. НИКОГДА не используйте их на практике.
  4. В примерах кода опускается не нужный для понимания приёма код, например, подключение инклудов и префикс std::.
  5. Здесь описаны не все приемы сокращения кода. Из тех, что описаны, многие являются более-менее очевидными.
  6. Компиляторы Microsoft Visual C++ и GNU C++ будут в дальнейшем сокращаться как VC и G++. В случаях, когда версия компилятора не указана явно, подразумевается версия, используемая на acmp (Microsoft Visual C++ 2008 и GNU C++ 5.1.0).

Стандарт C++

У языка C++ есть так называемый стандарт - документ, полностью описывающий язык. Стандарт языка C++ в дальнейшем будет именоваться просто стандартом. Стандарт меняется со временем и разные компиляторы с разной степенью успешности поддерживают разные версии этого стандарта. В 2011 году был опубликован стандарт C++11, добавивший в язык большое количество нововведений. VC 2008, вышедший в 2007 году, фактически не поддерживает этот стандарт, а G++ 5.1.0, вышедший в 2015, поддерживает C++11 полностью. Среди важнейших для сокращения кода нововведений следует отметить auto и range-based for, вкратце описанные здесь.
Также следует заметить, что в компиляторах есть так называемые расширения: не указанные в стандарте возможности языка, реализуемые компилятором. Если ваш код компилируется у вас на компьютере, но не компилируется на acmp, то это означает, что либо вы написали код в более старом/новом стандарте, либо использовали расширения компилятора. Некоторые приёмы используют расширения компилятора, в таких случаях это оговаривается.

1 Общие идеи


1.1 Используйте кратчайший алгоритм
Основой для написания кратчайшего кода является кратчайший алгоритм. Придумать кратчайший алгоритм иногда непросто даже для очень простых задач.
Иногда наиболее краткий алгоритм отличается крайней неэффективностью и следует следить за ограничениями задачи: пройдет ли этот алгоритм? Для этого следует изучить понятие сложности алгоритма (это понятие в любом случае стоит изучить, даже если вы не планируете заниматься сокращением кода).
Например, если вам требуется найти длину кратчайшего пути между двумя вершинами, не спешите применять алгоритм Дейкстры (работает за O(n2)), возможно ограничения позволят применить алгоритм Флойда-Уоршелла (работает за O(n3)), реализация которого намного короче.
Оптимизации алгоритма могут быть микроскопическими. Что короче: обходить массив от начала в конец или с конца в начало? Ответ на этот вопрос меняется от задачи к задаче.

1.2 Изучите стандартную библиотеку
Просмотрите, какие функции, классы, методы этих классов существуют в стандартной библиотеке. В особенности рекомендуется изучить следующие разделы:
  1. Библиотеки C: cstdio, cstring, cstdlib, cmath.
  2. Библиотеки C++: algorithm, string.
  3. Поточный ввод/вывод: методы классов istream и ostream (такие типы имеют объекты cin и cout).
  4. Контейнеры vector, set, map.
Следует отметить, что иногда бывает короче не использовать удобные возможности стандартной библиотеки (тем более что для их использования зачастую требуется подключать соответствующий инклуд), а реализовать их вручную. В частности, использование string редко оправдано.

1.3 Минимум сущностей
Не используйте функции, структуры, классы и всякие другие приятные вещи, придуманные умными людьми для того, чтобы сделать программирование более удобным и понятным. Оптимальнее всего писать весь код программы в main. Возможные исключения:
  1. Бывает удобно использовать рекурсивные функции, например, в алгоритме поиска в глубину.
  2. Требуется оперировать нетривиальными объектами, которые не задаются примитивным типом.
Ко второму исключению следует относится с большой осторожностью. Зачастую можно обойтись без объявления своего типа.
Например, вместо создания массива точек
struct Point { int x, y; };
Point point[10];
иногда можно просто завести массив на каждую координату
int x[10], y[10];
Подобная замена приводит к сокращению одних фрагментов кода и удлинению других, поэтому необходимо рассматривать каждый случай отдельно.

2 Простейшие приёмы


2.1 Используйте однобуквенные переменные
По стандарту у вас есть как минимум 53 возможных однобуквенных имени: 26 строчных латинских букв, 26 заглавных латинских букв и символ подчеркивания.

2.2 Используйте пробелы вместо табуляции
Символ табуляции учитывается при подсчете символов, заменяйте его пробелами. Некоторые IDE заменяют символ табуляции на пробелы автоматически. Многие IDE можно настроить так, чтобы они тоже начали производить такую замену.
С 22.01.16 табуляции перестали учитываться при подсчете длины кода, можно использовать.

2.3 namespace std
Очень редко бывает выгодно использование директивы using namespace std;. Вместо этого следует писать std:: у требующих этого объектов и функций (cin, cout, sort).

2.4 _STD (только для VC)
В компиляторе VC определен дефайн _STD:
#define _STD std::
Например, можно писать _STD cin вместо std::cin.

2.5 Пишите int main
Некоторые объявляют функцию main как void main вместо int main, чтобы не писать return 0. Однако стандарт и так позволяет не писать return 0 в функции main - эта команда выполняется автоматически.
Более того, использование void main запрещено стандартом и поддерживается компиляторами в целях совместимости со старым кодом.

2.6 Пишите main (только для G++)
Если возвращаемым типом функции является int, то его можно опустить. Это правило действует и для функции main: программа main(){} является корректной.
В С существовало правило "неявного int" (или правило "int по умолчанию"). Это правило состоит в том, что если спецификатор базового типа явно не указан, то подразумевается спецификатор int. Впоследствии это правило отменили как в C, так и в C++. Однако, в G++ это правило частично поддерживается в целях совместимости со старым кодом.

2.7 Не используйте void (только для G++)
Ситуация, когда функция должна что-то возвращать, но не возвращает (выполняется до конца, не встретив return), объявлена стандартом неопределённым поведением. VC в таком случае выдаёт ошибку, а G++ всего лишь предупреждение. Благодаря этому можно объявлять функции, не возвращающие значения, как возвращающие int: то есть int f() вместо void f(). Вспомнив предыдущий пункт, выкидываем int из объявления, сокращая код еще на три символа: f().

2.8 Структуры вместо классов
Используйте структуры вместо классов: структуры позволяют ровно то же, что и классы, но все члены у структур публичные по умолчанию.

2.9 Объявление своих типов
После объявления типа можно сразу создавать переменные этого типа. Например,
struct P { int x, y, z; };
P p[10];
сокращается до
struct P { int x, y, z; } p[10];
Если вы вообще не используете имя типа в дальнейшем, то его можно опускать:
struct { int x, y, z; } p[10];

3 Основные приёмы


3.1 Объявление переменных и массивов
  1. Объявляйте массивы статически, присваивая им при этом максимально возможный в данной задаче размер. Например, если требуется считать N чисел и известно, что N <= 3000, то удобнее сразу объявить массив на 3000 элементов (int m[3000];), а не выделять массив на N элементов динамически (int * m = new int[n];).
  2. Используйте глобальные переменные вместо локальных (исключение: рекурсивные функции). Огромным преимуществом глобальных переменных является то, что они автоматически инициализируются нулем. В частности, все элементы глобально объявленного массива инициализируются нулем.
    Замечание: локальные переменные выделяются на стеке, который, как известно, ограничен. Поэтому определение больших локальных статических массивов может приводить к переполнению стека, что вызывает Runtime Error. Размер стека можно увеличить специальной директивой, но это явно не способствует сокращению программы. Во избежание таких проблем объявляйте статические массивы глобально.
  3. Обходитесь минимальным количеством переменных, переиспользуя одну и ту же переменную в нескольких местах. Например, если в программе несколько независимых циклов, то можно использовать во всех этих циклах одну и ту же переменную.
  4. Объявляйте переменные одного типа вместе, одной инструкцией: int i, j, m[10], *p;
У G++ есть важное расширение - Variable-length array (далее VLA) - массив с неизвестным на этапе компиляции размером (этот массив выделяется на стеке). Это даёт возможность написать int m[n] вместо int * m = new int[n] даже когда n является переменной.
Хотя такой массив придется объявлять в отрыве от остальных переменных (так как мы уже должны были объявить и считать переменную n), мы экономим на размере массива (пишем m[n] вместо m[10000]), что иногда позволяет сэкономить символы.
Также можно создавать многомерные VLA: int m[n][n];.

3.2 Используйте минимальные инклуды
В C++ для многих сишных инклудов name.h ввели замену cname. Например, можно писать cstdio вместо stdio.h, что экономит 1 символ. Также, многие инклуды включают в себя другие инклуды, например в VC можно не подключать cstdio, если вы подключили iostream. Но тут следует быть осторожным: такое поведение не стандартизировано и может меняться от одной версии компилятора к другой. Например, в последних версиях VC подключение iostream автоматически подключает cmath, но в VC 2008, используемой на acmp, приходится подключать cmath явно.
В G++ идея минимальных инклудов имеет мощную поддержку в виде инклуда bits/stdc++.h, который подключает все имеющиеся в языке инклуды. Используйте его, если вам нужно подключить больше одного инклуда.

3.3 Используйте наиболее краткие типы
Везде, где это возможно, пытайтесь использовать более краткие типы:
  1. int вместо bool/char/short (int занимает больше памяти, но это редко бывает критично).
  2. int вместо long (в используемых на acmp компиляторах long == int).
  3. __int64 (VC) / int64_t (G++) вместо long long.
  4. size_t вместо unsigned int. size_t равен unsigned int в силу того, что компиляторы acmp настроены под 32-битную платформу. При компиляции под 64-битную платформу size_t равен unsigned long long.
Внимательно изучите, какой размер в байтах и какой диапазон значений имеет каждый тип.

3.4 Уберите лишние скобки
Изучите таблицу приоритетов и ассоциативностей операций в C++ и не ставьте скобок там, где они не нужны. Например, важно знать, что приоритет оператора && выше приоритета оператора ||.
Иногда требуется немного видоизменить выражение, чтобы избавиться от скобок:
(a*b)/(c*d) // начальное выражение
a*b/(c*d) // избавились от лишних скобок
a*b/c/d // раскрыли скобки
Ниже будут разобраны различные техники избавления от скобок.

4 Неявная конвертация

Важной для сокращения кода чертой языка C++ является неявная конвертация: автоматическое приведение одного типа к другому без необходимости явного указания. Например, конвертация между всеми примитивными типами может быть осуществлена неявно (правда в некоторых случаях компилятор будет выдавать предупреждения). Благодаря этому можно легко оперировать объектами разных типов в одном выражении.

4.1 Конвертация в bool
В местах где ожидается bool, примитивные типы автоматически преобразуются в bool. Для числовых типов (в том числе вещественных) и указателей преобразование в bool равносильно сравнению с нулём: (bool)x тождественно x != 0. Местами, где ожидаются bool, являются, в частности, условия операторов if, while, for. Рассмотрим примеры.
  1. if(x != 0) можно записывать просто как if(x).
  2. if(x != n) можно записать как if(x - n != 0), что может быть сокращено до if(x - n).
Так как последним символом строки в C++ является символ с нулевым кодом, проход по строке можно записывать как
for(i=0; s[i] != 0; i++)
Приведенное свойство позволяет сократить этот шаблон:
for(i=0; s[i]; i++)

4.2 Конвертация из bool
true при конвертации в число преобразуется в 1, а false – в 0.
  1. Выражение if(x == 5) s++; можно заменить на s += (x == 5);. Полученное выражение можно дополнительно сократить, убрав избыточные скобки: s += x == 5;.
  2. Если аргументами оператора && являются выражения типа bool, а результат работы оператора используется как bool, то его можно заменить на оператор &. Например, вместо if(10 < x && x < 30) можно писать if(10 < x & x < 30). Данный приём применим не всегда, так как оператор & имеет больший приоритет, чем оператор &&.
    Аналогично для операторов || и |.
4.3 Конвертация из char в int
Символ в C++ – это число. Это число называется кодом символа. Коды символов можно узнать, посмотрев в ASCII-таблицу.
  1. Можно писать код символа вместо самого символа во всех выражениях (кроме инструкций, где важно наличие переменной именно типа char, например, вывод через потоки). Например, вместо if(c == 'B') можно писать if(c == 66).
  2. Если требуется вывести код символа, то необходимо преобразовать символ в число, что можно записать как int(c) или (int)c. Но если вспомнить, что компилятор C++ автоматически конвертирует небольшие типы (char, short и подобн.) в int при осуществлении арифметических операций, то можно записать это короче: +c.
    char c = 'a';
    cout << c; // выводит 'a'
    cout << +c; // выводит '97'
  3. Следует отметить, что символы в ASCII-таблице располагаются не случайным образом. Например, цифры, заглавные и строчные буквы английского алфавита располагаются по порядку. Поэтому мы можем писать 'a' <= c && c <= 'z' для проверки того, является ли символ строчной буквой. Воспользовавшись предыдущим пунктом, сокращаем это до 65 <= c && c <= 90, что можно сократить еще сильнее до 64 < c && c < 91. Аналогичным образом мы можем проверить, является ли символ цифрой: 47 < c && c < 58.
  4. Упорядоченность символов в ASCII-таблице позволяет легко определять цифру, изображенную на символе. Для этого достаточно вычесть из данного символа 48 (код символа 0):
    с - 48
    Аналогичным образом можно определять номер данной буквы в алфавите: c - 65 для заглавных и c - 97 для строчных. Эта идея позволяет кратко записать преобразование шестнадцатеричной цифры (0123456789abcdef) в число:
    c % 87 % 48
  5. Предположим, что нам дана заглавная латинская буква и нам надо преобразовать её в строчную. Заглянув в ASCII-таблицу, убеждаемся, что для любой латинской буквы строчная версия имеет код ровно на 32 больший, чем заглавная версия. Значит, искомый код будет выглядеть следующим образом:
    с += 32;
    Если перед выполнением кода в переменной c хранился символ с кодом 66 (то есть символ 'B'), то после его выполнения там будет хранится символ с кодом 98 (то есть символ 'b').

4.4 Конвертация istream в bool
Для сложных типов преобразование в bool вызывает operator bool(), если таковой определен. Важным примером такого типа является класс istream (экземпляром которого является cin). operator bool() у потока возвращает false, если при работе с потоком произошла какая-либо ошибка, например, попытка чтения при отсутствии данных для чтения. Рассмотрим использование этого свойства на примере. Пусть в задаче дан список из N точек. Каждая точка состоит из двух чисел. Наивный код:
for(i=0; i<n; i++)
  cin >> x[i] >> y[i];
operator bool() позволяет выполнять считывание жадно, то есть до тех пор, пока во входном потоке есть данные:
for(i=0; cin >> x[i] >> y[i]; i++);
Этот код короче исходного на 3 символа.

Дальше идёт объяснение того, как это работает, для сокращения кода оно не требуется
У класса istream (экземпляром которого является объект cin) перегружен оператор >>, поэтому выражение cin >> x интерпретируется компилятором как cin.operator>>(x). Метод istream::operator>> возвращает объект, у которого он был вызван, в данном случае это cin. Это нужно для того, чтобы мы могли делать так называемые "каскадные вызовы": cin >> x >> y. Это выражение выполняется следующим образом: сначала у объекта cin вызывается метод operator>>, который осуществляет считывание переменной x, после чего возвращает объект cin, у которого снова вызывается метод operator>>, который осуществляет считывание переменной y, после чего возвращает объект cin.
Из вышесказанного делаем следующий вывод: выражение cin >> x[i] >> y[i] из примера возвращает cin. Этот возвращаемый cin попадает в условие продолжения цикла и преобразуется в bool. Пока во входном файле есть числа, считывание происходит успешно, поток cin находится в корректном состоянии и при преобразовании в bool возвращает true. Как только во входном файле заканчиваются числа, выполнение выражения cin >> x[i] >> y[i] переводит поток cin в состояние ошибки и при преобразовании в bool он возвращает false, прекращая цикл.

5 Выражения

Для понимания дальнейшего материала важно изучить такие сущности, как выражения. Выражение – это некая комбинация переменных и операций над этими переменными. Свойством выражений является то, что они возвращают результат. Примеры выражений:
x // возвращает переменную x
++x // возвращает переменную x
x + y * 12 // возвращает число
x > 10 ? 1 : -1 // возвращает число
"456" // возвращает строку
x = 67  // возвращает число
sin(3.14)  // возвращает double
cout << x // возвращает cout
Инструкции, содержащие управляющие конструкции (if, for, while, return, break и.т.д.), выражениями не являются. Важным свойством выражений является то, что их можно записывать через запятую. При этом вся эта конструкция также является выражением, которое возвращает результат последнего в списке выражения:
x += 3, y -= 4 // возвращает y
Выражения можно сочетать причудливым образом:
cout << (x += 3, y -= 4)
// прибавляет 3 к x, отнимает 4 от y, выводит y, возвращает cout
Логическим выражением будем называть выражение, которое может быть преобразовано к bool. Как следует из предыдущего раздела, все приведенные в данном отступлении выражения являются логическими.

5.1 Экономия фигурных скобок
Тело операторов if, else, while, for должно обрамляться фигурными скобками. Однако если это тело состоит всего из одной инструкции, то фигурные скобки писать необязательно. Зачастую количество инструкций в теле можно уменьшить до одной и избавиться от фигурных скобок. Рассмотрим пример:
while(cin >> x)
{
  s += x;
  cout << s;
}
Тело while состоит из двух инструкций, каждое из которых является выражением. Запишем выражения через запятую:
while(cin >> x)
{
  s += x,
  cout << s;
}
Теперь тело while состоит всего из одной инструкции, что позволяет убрать фигурные скобки и сэкономить два символа:
while(cin >> x)
  s += x,
  cout << s;

5.2 Тернарный оператор
Тернарный оператор имеет вид boolean_expr ? expr1 : expr2, где expr1 и expr2 представляют собой выражения, а boolean_expr – логическое выражение. Выражения expr1 и expr2 должны иметь общий тип (не обязательно совпадающий). Тернарный оператор сам по себе является выражением и типом этого выражения является как раз этот общий тип. Во многих случаях можно заменить условие if на тернарный оператор:
if(x > 2) y = 3; // 11 символов
x > 2 ? y = 3 : 0; // 10 символов
При этом могут получаться достаточно сложные конструкции:
if(x < y)
  s = "1";
else if(x == y)
  s = "draw";
else
  s = "2";
// 44 символа
эквивалентно
s = x < y ? "1" : x == y ? "draw" : "2";
// 26 символов
Полезным примером использования тернарного оператора является нахождение максимума/минимума двух чисел:
a>b?a:b // max(a, b)
a<b?a:b // min(a, b)
Рассмотрим нетривиальный пример:
if(x > 10) cout << y; // 16 символов
сокращаем до:
x > 10 ? cout << y : 0; // 15 символов
Однако этот код не компилируется, потому что cout << y и 0 имеют несовместимые типы: ostream и int соответственно. Мы можем схитрить и использовать запятую:
x > 10 ? cout << y, 0 : 0; // 17 символов
Выражения cout << y, 0 и 0 имеют одинаковый тип int, поэтому код корректен. Хотя в полученном коде на 1 символ больше, чем в изначальном, мы избавились от if, т.е. получили выражение, что открывает простор для дальнейших оптимизаций.

При использовании тернарного оператора часто возникает необходимость использовать в качестве expr1 и expr2 сразу списки выражений:
if(z > 5) { cout << x; x += 3; }
else { cout << y; y += 4; }
пытаемся сократить до
z > 5 ? cout << x, x += 3 : cout << y, y += 4;
Но если для expr1 использование списка выражений корректно, то для expr2 мы сталкиваемся с проблемой приоритетов операций: тернарный оператор имеет больший приоритет, чем оператор запятая и вышеуказанное выражение интерпретируется следующим образом:
(z > 5 ? cout << x, x += 3 : cout << y), y += 4;
Данную проблему всегда можно решить расстановкой дополнительных скобок:
z > 5 ? cout << x, x += 3 : (cout << y, y += 4);
Но иногда возможно более оптимальное решение. Например, если списком выражений является только expr2, то можно заменить условие тернарного оператора на противоположное, поменяв expr1 и expr2 местами:
z > 5 ? x += 3 : (cout << y, y += 4); // 24 символа
сокращается до
z < 6 ? cout << y, y += 4 : x += 3; // 22 символа

Тернарный оператор допускает вариант, когда выражения expr1 и expr2 оба имеют тип void. В этом случае, выражение, состоящее из тернарного оператора, также имеет тип void. Выражение имеет тип void, например, если оно представляет собой вызов функции, возвращающей void.

Если expr1 и expr2 оба являются lvalue-выражениями и имеют одинаковый тип, то всё выражение с тернарным оператором тоже является lvalue. lvalue – это грубо говоря то, чему можно присвоить значение. Например, lvalue являются следующие выражения:
x
++x
x += 4
m[x]
Из этого следует достаточно интересное свойство тернарного оператора: код
if(condition)
  x = 4;
else
  y = 4;
можно записать как
(condition ? x : y) = 4;
если x и y являются переменными одного типа.

5.3 Логические операторы && и ||.
Логические операторы && и || должны участвовать в выражениях вида
boolean_expr1 && boolean_expr2
boolean_expr1 || boolean_expr2
то есть оба операнда оператора должны являться логическими выражениями. Операторы && и || обладают интересным эффектом: если значения первого аргумента достаточно, чтобы узнать результат выражения, то второй аргумент не вычисляется:
a && b эквивалентно a ? b : false
a || b эквивалентно a ? true : b
Этот эффект позволяет использовать логические операторы как альтернативу if и тернарному оператору. Рассмотрим код из предыдущего примера:
x > 10 ? cout << y, 0 : 0; // 17 символов
Поскольку cout << y является логическим выражением, можно написать более лаконичный код:
x > 10 && cout << y; // 14 символов

5.4 for вместо while
Выражение while(...) занимает столько же символов, сколько и for( ;...; ). Однако у for есть два дополнительных места, куда можно вставлять выражения: перед первой точкой с запятой (выполняется перед началом цикла) и после второй точки с запятой (выполняется после каждой итерации). Благодаря этой возможности часто можно сэкономить пару символов:
cin >> n;
while(cin >> a)
  s += a, cout << s;
// 33 символа
сокращается до
for(cin >> n; cin >> a; cout << s)
  s += a;
// 31 символ

5.5 Краткая запись циклов
Рассмотрим следующий код:
int i, m[5];
int main()
{
  for(i=0; i<5; i++)
    cin >> m[i];
}
// 47 символов
Заметим, что переменная i уже равна 0, так как объявлена в глобальной области, а значит нет необходимости в инструкции i=0 в цикле. Также можно перенести инструкцию i++ внутрь тела и совместить её с инструкцией cin >> m[i]:
int i, m[5];
int main()
{
  for(; i<5; )
    cin >> m[i++];
}
// 43 символа

Рассмотрим следующий код:
int i, m[5];
int main()
{
  for(i=4; i>0; i--)
    cin >> m[i];
}
// 47 символов
Заметим, что инструкцию i=4 можно "исполнить" прямо на этапе создания переменной i, сразу инициализировав её значением 4. Также перенесём инструкцию i-- внутрь тела и совместим её с инструкцией cin >> m[i]:
int i=4, m[5];
int main()
{
  for(; i>0;)
    cin >> m[i--];
}
// 45 символов
Теперь заметим, что цикл продолжается до тех пор, пока i больше 0, то есть до тех пор, пока i не станет равно 0. Значит условие i>0 можно заменить на условие i != 0. Вспоминая совет 4.1, в свою очередь заменяем i != 0 на i:
int i=4, m[5];
int main()
{
  for(; i;)
    cin >> m[i--];
}
// 43 символа

Есть интересный способ сэкономить 1 байт. Пусть у нас есть два цикла подряд:
int i, m[5];
int main()
{
  for(; i<5; )
    cin >> m[i++];
  for(i=0; i<5; )
    cout << m[i++];
}
// 72 символа
Заметим, что во убрать инструкцию i=0 во втором цикле не получилось, так как i уже не равно 0. В этом случае выгодно объявить новую глобальную переменную j и использовать её:
int i, j, m[5];
int main()
{
  for(; i<5; )
    cin >> m[i++];
  for(; j<5; )
    cout << m[j++];
}
// 71 символ

Рассмотрим задачу "найти наибольшее из чисел". В первой строке файла расположено количество чисел N, в следующей строке записано N чисел. Пишем решение задачи:
int i, n, x, a;
int main()
{
  for(cin >> n; i<n; i++)
    cin >> x,
    x>a ? a=x : 0;
}
// 58 символов
Воспользуемся приёмом из совета 4.4:
int n, x, a;
int main()
{
  for(cin >> n; cin >> x;)
    x>a ? a=x : 0;
}
// 49 символов
Заметим, что у нас пропала необходимость в переменной n. Однако она есть во входном файле и её надо куда-то прочитать. Заметим, что на следующей инструкцией происходит чтение в переменную x и её предыдущее значение затирается. Это позволяет нам считать ненужное значение в переменную x:
int x, a;
int main()
{
  for(cin >> x; cin >> x;)
    x>a ? a=x : 0;
}
// 47 символов

При переносе инструкций инкремента внутрь кода следует быть очень внимательным, чтобы не сломать логику кода. Также можно напороться на неопределенное поведение (undefined behaviour). Пример кода с неопределенным поведением:
cout << a[x] + b[x++];
Это связано с тем, что оператор + не является точкой следования и компилятор может вычислять аргументы суммы a[x] и b[x++] в произвольном порядке: он может посчитать a[x] перед b[x++] и получить a[x] + b[x], а может посчитать b[x++] перед a[x] и получить b[x] + a[x+1]. Причем это поведение может зависеть от операционной системы, платформы, компилятора, версии компилятора, флагов компиляции и так далее. Для интересующихся C++ рекомендуется почитать о точках следования дополнительно, например, здесь. Впрочем, никто не мешает попробовать сдать на acmp код с неопределенным поведением, надеясь, что он скомпилируется именно так, как вам нужно.

6 Специфические приёмы


6.1 Битовая арифметика
Побитовые операции позволяют совершать некоторые интересные вещи.
  1. Выражение ~n эквивалентно выражению -n-1 и равняется 0 тогда и только тогда, когда n равно -1. Это позволяет заменять условие n != -1 на ~n, так же как n != 0 можно заменять на n (совет 4.1), Такие условия возникают в убывающих циклах в виде n >= 0 и n > 0 (совет 5.5).
    Также оператор ~ может быть полезен для сокращения выражений, где прибавляется/отнимается 1, например выражение a+b+1 можно сократить до a-~b, а выражение a-b-1 до a+~b.
  2. Выражения ~-n и -~n эквивалентны выражениям n-1 и n+1 соответственно. Унарные операторы имеют значительно больший приоритет, чем оператор сложения, что позволяет использовать это приём для избавления от скобочек: 3*(n+1) можно сократить на 2 символа до 3*-~n.
  3. Инструкция x ^= y ^= x ^= y; меняет значения переменных x и y местами.
  4. Выражение n & (n-1) равняется 0 тогда и только тогда, когда n является степенью двойки либо нулём. На самом деле есть еще один вариант, когда это выражение равно 0 - это минимальное возможное значение знаковых типов: -231 (INT_MIN) для int и -263 (LLONG_MIN) для long long. Это исключение возникает потому что знаковое число -231 представляется в памяти как беззнаковое число 231, которое является степенью двойки (для интересующихся гуглить "дополнительный код").
В двух следующих приёмах я буду подразумевать, что все числа являются неотрицательными. Для отрицательных чисел эти приёмы тоже применимы, но требуют некоторых замечаний и уточнений, описание которых заняло бы достаточно много места.
  1. Операции битового сдвига x >> n и x << n эквивалентны делению/умножению x на n-ую степень двойки (например, 3<<4 == 3*2*2*2*2 == 48). В частности, 1<<n равняется n-ой степени двойки (например, 1<<8 == 256).
    Это бывает удобно для создания больших массивов: например, если требуется создать массив на 1000000 элементов, можно просто создать чуть больший массив на 1<<20 == 1048576 элементов, сэкономив 2 символа.
    Следует отметить, что операторы битового сдвига имеют очень маленький приоритет, что иногда позволяет использовать их для сокращения: (x+y)/2 можно сократить на 1 символ до x+y>>1.
  2. В случаях, когда y является степенью двойки, выражение x%y можно заменить на x&y-1. Например, выражение x%2 можно заменить на x&1. Оператор & имеет намного меньший приоритет, чем оператор %, что иногда позволяет использовать его для сокращения: (x+1)%2 можно сократить до x+1&1. Кстати, конкретно этот пример можно сократить еще на один символ: ~x&1.

6.2 Числовые литералы
Литералами называются константы, записанные в коде. Литералы бывают 4 видов: целые числа (157, 0xFE), числа с плавающей запятой (0.2, 0.2E-01), символы ('c') и строки ("dog"). К литералам можно приписывать суффиксы, которые задают литералу конкретный тип:
4u // эквивалентно (unsigned int)4
4ll // эквивалентно (long long)4
Это может быть удобно, когда требуется перемножить числа по модулю, при этом результат умножения может выйти за рамки типа int:
(a * b) % p // переполнение int при умножении a на b
Выходом может быть замена типов переменных a и b на long long. Однако это может критически замедлить программу, поэтому приходится явно говорить компилятору, что необходимо проводить умножение не в int-ах, а в long long-ах. Для этого достаточно привести один из аргументов к long long:
((long long)a * b) % p // избавились от переполнения ценой 10 символов
Числовые литералы предоставляют более лаконичное решение:
(1ll * a * b) % p // избавились от переполнения ценой 4 символов
Это работает потому что 1ll изначально имеет тип long long и поэтому все умножения автоматически производятся над long long.

Аналогичный приём применим в случае, когда необходимо преобразовать число к double, например, при выполнении деления:
(double)a / b // 11 символов
можно сократить до
1.0 * a / b // 7 символов
Если слева или справа от точки у числа стоит 0, то его можно опустить:
.4 // то же, что 0.4
2. // то же, что 2.0
Это позволит сократить код еще сильнее:
1. * a / b // 6 символов

Другими полезными литералами являются числа с плавающей запятой, записанные в экспоненциальном (научном) формате: литерал 1e6 эквивалентен литералу 1000000.0. Это может быть удобно в коде, когда необходимо иметь дело с большими константами, например, когда требуется завести заведомо большое число: int M = 1e6 на 2 символа короче, чем int M = 1<<20. Нужно помнить о том, что литералы с плавающей точкой нельзя использовать при задании размера массивов, а использование этих литералов в арифметических выражениях может приводить к ошибкам округления.

6.3 Округление
При приведении вещественного числа к целому типу оно округляется в сторону нуля, то есть дробная часть просто отбрасывается:
int(x) // округление в сторону нуля
Однако иногда нам требуется округлить число к ближайшему целому, в этом случае используется следующий приём:
int(x + .5) // округление до ближайшего целого, работает при неотрицательном x
При делении одного целого числа на другое, оно делится нацело, то есть дробная часть деления просто отбрасывается:
x / y // деление с округлением в сторону нуля
Однако иногда нам требуется поделить с округлением вверх, в этом случае используется следующий приём:
(x+y-1) / y // деление с округлением вверх, работает при неотрицательных x,y
Например, чтобы поделить на 2 с округлением вверх, можно написать (x+1) / 2. Битовая арифметика позволяет сократить этот код до -~x / 2.

6.4 Указатели
В случаях, когда выполняется обход по массиву, бывает оптимальней использовать указатели. Рассмотрим простую задачу: на вход подается строка S длиной не более 100 символов и символ C. Требуется вывести строку, полученную из строки S удалением всех вхождений символа С. Пользуясь приемами, описанными в статье, пишем следующий код:
char s[101], c;
int i;

int main()
{
  for(cin >> s >> c; s[i]; i++)
    s[i] - c && cout << s[i];
}
// 71 символ
Использовав указатель p вместо индекса i, получаем более короткое решение:
char s[101], c, *p=s;

int main()
{
  for(cin >> s >> c; *p; p++)
    *p - c && cout << *p;
}
// 65 символов

6.5 Дефайны
Дефайны позволяют давать кускам кода имена и в дальнейшем вместо этих кусков кода вставлять эти имена. В обычном коде использование дефайнов зачастую сводится к простому определению констант:
#define N 3000
Однако дефайны гораздо мощнее: они позволяют определять любую последовательность токенов. Рассмотрим это на примере кода, который возник в совете 5.5:
int x, a;
int main()
{
  for(std::cin >> x; std::cin >> x;)
    x>a ? a=x : 0;
}
// 57 символов
Заметим, что в коде есть длинный повторяющийся кусок кода: std::cin >> x;. Задефайним его:
#define X std::cin >> x;
int x, a;
int main()
{
  for(X X)
    x>a ? a=x : 0;
}
// 55 символов
Несколько замечаний о дефайнах:
  1. Для определения того, насколько сократится код после применения определённого дефайна, я использую следующий алгоритм: вычисляем количество символов в определении дефайна, вычисляем количество применений дефайна, уменьшаем оба числа на 1, перемножаем их и вычитаем из результата 9. В приведенном примере в определении дефайна было 12 символов, он был применен 2 раза, отсюда получаем, что сокращение кода будет равно 11*1 - 9 = 2 символа.
  2. Определение дефайна может включать имена других дефайнов. То есть можно дефайнить фрагменты кода, в которых уже использовались другие дефайны.
  3. Иногда задефайниванию поддаются совсем небольшие куски кода. Например, если в коде по меньшей мере 6 раз встречается взятие индекса массива [i], то его выгодно задефайнить.
    Иногда для одного массива используется несколько индексов, например s[i] и s[j]. В этом случае полезно вспомнить, что s[i] для указателей и массивов эквивалентно *(s+i), а значит s[i] == *(s+i) == *(i+s) == i[s]. Поэтому мы можем заменить s[i] и s[j] на i[s] и j[s] и задефайнить [s].
    Часто выгодно объявить одномерный массив вместо двумерного, например int m[10000] вместо int m[100][100]. Казалось бы, что из-за этого придется вместо m[x][y] писать m[n*x+y], что длиннее на 1 символ. Однако заметим, что при каждом обращении к массиву будут возникать 4 символа m[n*, поэтому их можно задефайнить.
Иногда выгодно применять дефайны с параметрами (такие дефайны называются макросами). В макросах вам могут пригодится операторы препроцессора # и ##. О макросах вкратце здесь. Примером применения макросов может служить алгоритм Флойда-Уоршелла. Рассмотрим фрагмент кода этого алгоритма:
for(k=0; k<n; k++)
  for(i=0; i<n; i++)
    for(j=0; j<n; j++)
// 48 символов
Применим макрос:
#define F(x) for(x=0; x<n; x++)
F(k)
  F(i)
    F(j)
// 39 символов
Проводить сокращение кода дефайнами следует в последнюю очередь, когда все остальные оптимизации уже проведены, иначе можно легко запутаться в своем коде. Иногда получаемый код поддается сокращению дефайнами только после существенных переделок, возможно даже увеличивающих размер кода. Поэтому в некоторых случаях следует писать код сразу с оглядкой на последующее применение дефайнов.

6.6 [Устарело] Использование файловых потоков (только для VC)
На сайте в качестве примера программы на C++ приведен следующий код:
std::ifstream I("input.txt");
std::ofstream O("output.txt");
Эти строки можно переписать немного по другому:
std::fstream I("input.txt"), O("output.txt", std::ios_base::out);
Объяснение того, как это работает довольно обширно, поэтому я ограничусь следующим фактом: поток I обращается с файлом так, как это делает fopen с флагом "r+", а поток O – как fopen с флагом "w". Посмотрев заголовочные файлы, можно выяснить, что std::ios_base::out – это обычная константа, равная 2. И этот факт позволяет нам записать конечный вариант, который короче исходного на 12 символов:
std::fstream I("input.txt"), O("output.txt", 2);

11 комментариев:

  1. Я уже готов к строчкам типа a[y+i%2-~x*60] += 1-i++%2*2; и безумным дефайнам, но все обрывается только на шести банальных советах! Требуем продолжения!

    ОтветитьУдалить
  2. Точнее даже на пяти, шестой не дописан ((

    ОтветитьУдалить
  3. Очень преочень полезные советы. Спасибо автору.
    http://acmp.ru/index.asp?main=bstatus&id_t=148&lang=CPP Позиция 11 после оптимизации.
    Система оценки, конечно, странная. Код выполняющийся за 0,5 и поджирающий 3052 стоит выше, чем мой 0,111 1188. Всегда думал, что оптимизация кода должна приводить к ускорению работы программы и уменьшению потребляемой памяти, а не наоборот.

    ОтветитьУдалить
  4. Простите за глупый вопрос. Зачем сокращать код, если при этом время работы особо не снижается? Плюс к этому и читабельность падает. Если ты ACM программист, то для тебя важно время работы, а если web-developer, то читабельность.

    ОтветитьУдалить
    Ответы
    1. Специально, чтобы тесты получали рейтинг выше на acmp, ну сказано же в начале.

      Удалить
    2. еще можно поучаствовать в http://www.ioccc.org/ . Там можно посмотреть код с прошлых лет, но надо запастись противорвотным. ;)

      Удалить
  5. > Инструкция `x ^= y ^= x ^= y;` меняет значения переменных x и y местами.

    Выражение `x ^= y ^= x ^= y;` меняет значения переменных местами только в С++ и только начиная с С++17. Именно в С++17 гайки секвенсинга в операторах присваивания были затянуты до той степени, которая сделала это выражение работоспособным. В языке С (и в более ранних версиях С++) это выражение порождает то же самое неопределенное поведение, о которым вы говорили выше.

    При этом стоит иметь в виду, что практически ни один компилятор на текущий момент не поддерживает С++17: ни в GCC, ни в Clang, ни в MSVC++ новые правила секвенсинга в операторах присваивания пока не реализованы.

    ОтветитьУдалить
  6. хочется рвать xD

    ОтветитьУдалить