Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 
Вернуться
Тема: Двоичный поиск в задаче Всероссийская олимпиада по информатике
1 2
  1  Егоров Илья Валерьевич, 15 сентября 2020 г. 22:20:05
      Одной фразой: я верю в будущее одновременно красивого и эффективного кода. То, что часто видится "либо то, либо это" — не особенность самого способа написания кода и предрасположенности к оптимизации, а людской крайности, когда эффективные решения пишутся теми, кому на чистоту как можно ближе к "да плевать", и собственно наоборот, когда поклонники решений ясных всячески избегают эффективности "лишней".
  2  Егоров Илья Валерьевич, 15 сентября 2020 г. 21:56:42
      Та же абстракция помогает понижать сложность получаемого кода и повышать ясность. Например, scanf может быть под капотом ужасен, да весь glibc попахивает, но этого человек не узнает, пока сам не захочет туда заглянуть. Грамотное разделение кода на слои и модули — вот что действительно влияет на ясность, а никак не оптимизации, которые проблеме ортогональны.
  3  Егоров Илья Валерьевич, 15 сентября 2020 г. 21:51:15
      И более того, от оптимизаций (не хаков, что я в которых раз специально выделю) нередко не зависит ясность кода. Приведение кода к виду ясному — это вещь, которая как правило не влияет напрямую на эффективность. Одно и то же решение 224 у меня была записано в разных стилях: сначала в стиле чистого Си, а затем в стиле C++ с разделением на неймспейсы и пользовательские типы. Выхлоп эквивалентен, один в один. Также заверю, что ясность кода — это не сложность. Сложные вещи могут быть описаны просто и красиво, равно как и наоборот.
  4  Егоров Илья Валерьевич, 15 сентября 2020 г. 21:44:50
      И еще раз скажу, что тут нет оптимизаций "низкоуровненных". Сказанное находится в рамках семантики языка (уже было сказано, что так называемая built-in функция вошла в C++20) и алгоритмов, а уж прилично знать язык — казалось бы, вещь необходимая для достижения той же ясности. Если бы я настаивал на ассемблерных вставках на пустом месте, использовании хака с домножением числа на булев результат иль еще чем подобном, то дело бы было совсем иное, именно это обычно подразумевается под низкоуровненщиной. В общем, вышла софистика.
  5  Хворых Павел, 15 сентября 2020 г. 21:22:00
      Чтобы не разводить оффтопик, отвечу только на одну из затронутых тем: оптимизации (тем более низкоуровневые) обычно ухудшают ясность, поскольку требуют более глубокого понимания от читающего. Если производительность не важна (что верно почти всегда), следует между ясностью и производительностью выбирать ясность. Например, отсортировать весь список вместо фрагмента списка может быть проще для восприятия и потенциально более устойчиво к багам — не придется помнить/пояснять, что в функцию обязательно должен прилетать наполовину отсортированный список.
  6  Егоров Илья Валерьевич, 15 сентября 2020 г. 19:51:19
      Немного оффтоп. Думаю, следует немного развить вскользь упомянутую тему. Парсинг чисел через while и парсинг чисел через конечный ряд ветвей — это 2 разных алгоритма, 2 разных задач.

Первое всего лишь "выпарсить некое десятичное число, состоящего из неизвестно какого кол-ва символов (возможно, и бесконечного)". O(n), амортизированно O(1).

Второе уровнем абстракции малость ниже, "выпарсить такое-то десятичное число, состоящее из минимум стольки-то символов, в среднем стольки-то и максимум стольки-то". O(1).

Если ограничиться примитивными типами, с помощью шаблонов и constexpr второй вариант можно свести к "выпарсить десятичное число такой-то разрядности". Этот вариант гораздо лучше разворачивается на обыденные потребности, нежели первый, излишне абстрактный вариант, поскольку наиболее точно описывает задачу и можно, скажем, 32-битный int выпарсить наиболее эффективно. Хороший пример грамотного обобщения. Первый вариант тоже имеет право на существование, но только в контексте длинной арифметики и/или особых условий (например, если вдруг в кэш второй не влезет).

Так что, можно сказать, я за выбор подходящего уровня абстракции. Чтоб и не высокий до небес и O(1) на столетие, но и не слишком низкий уровня "я готов не спать, лишь бы работало быстро".
  7  Егоров Илья Валерьевич, 15 сентября 2020 г. 19:00:44
      Компилятор — инструмент, а не какой-нибудь портативный гном-программист, переводящий код в ассемблер и могущий подправить какие захочет моменты. Так и получается, что подробность в коде решения задачи способствует эффективности кода, но она и не только ради этой самой эффективности приводится, повышение эффективности можно считать побочным эффектом. Хаки, как уже говорилось, к этому не относятся. Хаки есть попытка взять работу компилятора на себя (иль точнее "помочь" компилятору). Они и не приводятся.
  8  Егоров Илья Валерьевич, 15 сентября 2020 г. 18:54:30
      Под эту гребенку идет все упомянутое. Копирование по значению — будто бы в теле функции идет какая-то работа, для которой требуется это самое копирование. Т.е. конкретное намерение программиста, связанное с алгоритмом. static — явное указание "функция используется только в этом файле", что также документирует "не ищи ее использование извне". Эффективная расстановка ветвей (+likely/unlikely) — указание вероятности того или иного исхода, что в процессе наиболее ожидаемо (описывает задачу). Разворачивание while — вообще строгое приведение алгоритма парсинга чисел (что есть лишь пример) к O(1) с указанием максимальной длины числа. Все это компилятор не способен сам сделать, поскольку это непосредственная часть решения задачи. Побочный эффект: код получается подробным и хорошо анализируемым, четко отражает намерения программиста. Вот так, по-хорошему, и должен выглядеть код. В конце концов, это ж C++, известный своей дотошностью к подробностям.
  9  Егоров Илья Валерьевич, 15 сентября 2020 г. 18:38:00
      Так что я не про крайность "преждевременная оптимизация, да и не в критичных кусках кода". Нет, я про хороший софт, за который не стыдно. Тот, где вместо "отсортируем список на входе" идет "эй, на входе ж первая половина уже отсортирована, надо только вторую отсортировать". Асимптотическая сложность одна и та же, но второй случай точнее выражает специфику задачи и не делает бесполезную работу там, где оно не требуется.
  10  Егоров Илья Валерьевич, 15 сентября 2020 г. 18:32:02
      ...тей в лице дров и системного софта как такового, но и софта для научных расчетов. Выполняется процесс дней 14 или 12 — разница заметная. В приложениях графических важен отклик — это тоже к мелочам.
  11  Егоров Илья Валерьевич, 15 сентября 2020 г. 18:29:27
      Во-первых, Java тут особо и не к месту, поскольку она не пример плохой производительности, а, напротив, благодаря JIT с интринсиками спокойно обгоняет наивные решения на плюсах (обжорство по памяти — тема отдельная).

Во-вторых, олимпиадным задачам для "просто решить" действительно не нужны никакие особые оптимизации, но мною подразумевается программирование как таковое. А тут уж надо хотя бы владеть базовыми правилами "хорошего тона", в том числе применением упомянутого static. Человек может и обходиться без конкретики, но тогда софт так и будет писаться под существующие 8+ ядер и 16+ гигабайт памяти с долей монополии в рантайме и ужасным качеством кода, что процесс неизбежный, но все же неприятный и не сулящий большие надежды. Собственно, приводил я именно конкретику, своеобразное умение выказывать в коде бОльшую степень осведомленности в задаче, а не всякие хаки. Держаться вблизи четкого алгоритма решения задачи != делать вместо компилятора его работу. На первое времени тратится на порядок меньше, чем на второе, поскольку оно часть самого процесса написания программного обеспечение, так что умение описывать в решении конкретику не выходя за рамки абстракции — тоже хороший навык (не воду же в коде лить, как это привыкли на той же Java в силу "JIT за меня мои 1000+ классов aka ООП ради ООП сократит в небольшой быстрый код"). Ассемблер приводится для яркой демонстрации "как оно за капотом" и его знание не обязательно, но полезно для понимания "почему оно дает такой эффект". Развертки функций и циклов нет (развертка — совсем не то же, что упомянутое мною "разворачивание" вплоть до исчезновения цикла вообще; для развертки есть и -funroll-loops, а вот для разворачивания в конечный набор if-ов такого нет). built-in функции тоже не есть нечто совсем низкое, это всего лишь дополнительная фича, отсутствующая в стандарте, вроде халявной дополнительной библиотеки.

В-третьих, "заведомо низкоуровневые критичные к производительности задачи" имеются повсеместно. В эту категорию входит не только любимый пример ряда личнос
  12  Хворых Павел, 15 сентября 2020 г. 17:56:47
      Разумеется, константа, стоящая за асимптотикой, имеет значение. Но для её уменьшения не надо вручную развертывать функции, циклы и лезть на уровень built-in функций и ассемблера. В олимпиадных задачах ограничения всегда рассчитываются из той логики, что грамотно написанное решение без применения специфичных фич должно пройти. Причем не только на C++, но и на Java. В реальных задачах как правило плевать, будет функция работать 1 секунду или 2. А где не плевать, вопрос решается алгоритмической оптимизацией, переписыванием критичного фрагмента на более эффективный язык, покупкой нового сервера и много чем еще. Исключение - заведомо низкоуровневые критичные к производительности задачи, но такие еще надо поискать. Для таких исключений и нужны все эти низкоуровневые фичи, в нормальном коде их быть не должно.
  13  Егоров Илья Валерьевич, 15 сентября 2020 г. 16:55:55
      Из касающихся этой темы (важность не-асимптотической оптимизации) есть статьи вроде
https://habr.com/ru/post/309796/ + немного предвзятая https://habr.com/ru/post/478420/ (где, подобно сомнительным доводам сторонников индетерминизма, асимптотическая сложность не расширяется до рассматриваемой единицы, что приводит к софистике).
  14  Егоров Илья Валерьевич, 15 сентября 2020 г. 16:37:38
      На асимптотику остальное, конечно, не влияет, но все же имеет значение. И O(1) может быть таким себе, если не влезет в конкретные лимиты, поэтому асимптотика — далеко не единственное, о чем стоит беспокоиться. Зависит от задачи (а далеко не все задачи чисто олимпиадные с условно бесконечными для пользования ресурсами).
  15  Хворых Павел, 15 сентября 2020 г. 16:29:47
      Богдан, вы правы, все эти "примочки с помощью" нужны чуть чаще, чем никогда. Единственная ошибка в вашем коде - передача вектора по значению. При этом создается полная копия вектора, что приводит к работе метода за O(n) вместо O(log n). Остальное на асимптотику не влияет.
  16  Егоров Илья Валерьевич, 15 сентября 2020 г. 14:11:19
      ...это компилятору. Вызов встроенной __builtin_expect определим для краткости как likely(b) и unlikely(b) соответственно:

repeat<mid_digit_count>::call([&] {
~~if (likely(c > ' ')) add_digit();
});

repeat<(max_digit_count - mid_digit_count)>::call([&] {
~~if (unlikely(c > ' ')) add_digit();
});

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

Третий шаг — скорее для полноты, но это важная особенность, которую нельзя упускать. Зная минимальное кол-во цифр (полагаю, довольно очевидно, что даже в самом худшем случае оно не меньше 1), выделить и это явно:

repeat<min_digit_count>::call(add_digit);

repeat<(mid_digit_count - min_digit_count)>::call([&] {
~~if (likely(c > ' ')) add_digit();
});

repeat<(max_digit_count - mid_digit_count)>::call([&] {
~~if (unlikely(c > ' ')) add_digit();
});

Вот так можно, казалось бы на пустом месте, обойти стандартную библиотеку, а вместе с ней и ряд прочих, на порядок, просто тщательно прописывая семантику.
  17  Егоров Илья Валерьевич, 15 сентября 2020 г. 14:11:02
      ...также тем, что в C++20 ради этого введены атрибуты [[likely]] и [[unlikely]], практически эквивалентные по эффекту __builtin_expect(b, 1) и __builtin_expect(b, 0). Что это дает? А вот что: компилятор может таким определенным образом выстроить последовательность инструкций, чтоб это способствовало переходу в ожидаемую ветвь. Использовать этот инструментарий стоит с умом, да и только тогда, когда анализ поступаемых данных действительно хорошо проведен. Другое обстоятельство: данное указание совсем не эквивалентно инвертированию условия, т.е. использовать следует только после правильной расстановки веток. Да и к тому же, можно очень даже запросто получить обратный эффект, поэтому подкреплять соображения надо эмпирически.

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

while (c > ' ') {
~~x = x * 10 + c - '0';
~~c = getChar();
}

Первый шаг — зная верхний предел кол-ва проверок, развернуть цикл на ряд if-ов. Разворачивание спокойно абстрагируется простой шаблонной функцией. Для дальнейшей краткости обозначим добавление десятичной цифры функцией add_digit(). Код принимает вид:

repeat<max_digit_count>::call([&] {
~~if (c > ' ') add_digit();
});

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

Для примитивных типов, т.е. независимо от условий задачи, можно определить верхний предел как кол-во цифр максимального десятичного числа указанного типа, по модулю. Знаковость тоже имеет значение, что играет роль в 64-битном числе. Определить вспомогательную функцию для получения верхнего предела "по умолчанию" можно как последовательность ветвлений с is_same из type_traits, или же совсем абстрагироваться и напрямую вычислять максимум цифр.

Второй шаг — зная мат. ожидание для кол-ва цифр во входных данных, явно намекнуть на
  18  Егоров Илья Валерьевич, 15 сентября 2020 г. 14:10:33
      ...нюю связь, да и прибавится к этому целый букет особенностей определения inline функций, так что предпочтительно все же использовать static. Более того, для всех 4 комбинаций (static, static inline, inline и без) есть свои применения, что можно для эрудиции вычитать, например, в комментариях исходного кода TCMalloc, но это уже совсем далеко от темы решения олимпиадных задач. Вот так, всего лишь указывая область использования функции (будем ли использовать извне иль только в данной конкретной единице компиляции) получаем такой эффект.

Другой момент — порядок хождения по ветвлениям. Программист может знать какая ветка более вероятна, а вот компилятор отнюдь не знает. Рассмотрим пример:

if (a) {
~~/* true work */
} else {
~~/* false work */
}

Предсказатель ветвлений, как и компилятор, далек от совершенства. Глубоко ложно мнение, что в ~99% случаев предсказатель угадывает верно и якобы не стоит с этим заморачиваться. Напротив, все зависит от программиста.

Как бы то ни было, компилятор будет наивно предполагать, что чаще выполнение может идти в первую ветку, т.е. просто пропишет на ассемблере последовательность "как есть". А что, если заведомо известно, что около 80% данных ведет ко второй ветке, и при этом вполне вероятно хаотично? И все равно машина будет терять такты на прыжки и сопутствующий сброс конвейера, надеясь на те самые 20%, ведущие к первой ветке, поскольку ей этот факт не известен. А доказывает это простая проба: замена if (a) на if (!a) в случае, когда это ветвление является узким местом (привет, 224), дает ощутимый прирост, по крайней мере с хорошими замерами через perf на локальной машине, что также хорошо проглядывается в получаемом branch-misses. Еще более интересны цепочки ветвлений (с else if), где эффект особенно заметен, но и в силу разницы кол-ва проверок, ибо успешное хождение в ветку до else if этот самый else if отбрасывает.

В помощь к этому в GCC определена встроенная функция __builtin_expect, дающая компилятору подсказку "какой исход более вероятен". Подкреплю проблему
  19  Егоров Илья Валерьевич, 15 сентября 2020 г. 14:09:51
      Весь дальнейший текст скорее вам на будущее, этак на после 2 курса вуза (на котором обычно ассемблер и приводится).

Назвать это "помощью" компилятору можно весьма условно, да и корректно применение такого выражения в довольно редких случаях. Например, определение экземпляра пользовательского типа в глобальной области видимости (вместо того, чтоб делать это в теле main) для GCC дает хороший прирост, в то время как подобное отчего-то выдает малоприятные результаты для MSVC, ибо валит 224 на 50 тесте. Так вот, вынос этого случая на уровень заточенных под конкретный компилятор макросов и можно назвать "помощью" компилятору.

Ряд остальных случаев — всего лишь прописывание определенного уровня семантики. Компилятор не может без имеющейся у программиста информации что-то делать или же не делать. Для примера распишу как влияют некоторые упомянутые мною моменты.

Приведенный мною static, что кстати имеется и в показанном коде, можно назвать противоположностью extern. По умолчанию компилятор обязан все функции (за некоторым исключением) делать доступными извне, т.е. способными слинковаться когда кому-нибудь это потребуется, что есть "внешняя связь". Выливается это в то, что функция в получаемом выхлопе на ассемблере определяется явно: с меткой и ее телом, что в том примере при удалении static добавляет ровно 2 строки на ассемблере (метку и ret). Это препятствует хорошей оптимизации, поскольку компилятор так не может просто взять да смешать инструкции меж собой, а обязан в месте вызова функции прописать call. А вот static, напротив, указывает на "внутреннюю связь". Компилятор уже сможет (но и не обязан, что замечается в некоторых случаях) спокойно взять да скопировать тело функции в место вызова, перемешать инструкции, лишнее выбросить — в общем, оптимизировать так, будто бы разделения на функцию и не было (но в силу несовершенности компилятора и это не всегда верно, что играет в обе стороны). inline дает схожий эффект, ибо изначально для "вшивания" и предназначен, но такая функция формально все еще будет иметь внеш
  20  Зараник Богдан Юрьевич, 15 сентября 2020 г. 9:17:37
      Спасибо огромное! Слишком много умных и непонятных слов для меня) С 21-го учёба в ВУЗе => там чуть подучу С++ и перечитаю данный текст ещё не один раз! Я не разбираюсь в таких тонкостях: до сегодняшнего дня наивно полагал, что все эти примочки с "помощью" компилятору дают лишь незначительную выгоду, которой можно пренебречь. Ещё раз спасибо!!!
1 2

Чтобы оставить сообщение необходимо зарегистрироваться и авторизоваться!

Красноярский краевой Дворец пионеров, (c)2006 - 2020, E-mail: admin@acmp.ru