Эффективность реализаций императивных языков программирования в решении олимпиадных задач

 
 
Д.А. Слинкин  
 
 
 
 
 
 
 
ЭФФЕКТИВНОСТЬ РЕАЛИЗАЦИЙ  
ИМПЕРАТИВНЫХ ЯЗЫКОВ ПРОГРАММИРОВАНИЯ  
В РЕШЕНИИ ОЛИМПИАДНЫХ ЗАДА
Ч 
 
 
 
Монография 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Москва 
Шадринск 
Издательство «ФЛИНТА» 
ШГПУ 
2024 
2024 

УДК 37.016:004.42 
ББК 74.263.2 
С47 
 
Рецензенты: 
Пирогов В.Ю. – канд. физ.-мат. наук, профессор, 
кафедра "Программирования и автоматизации бизнес-процессов" ФГБОУ ВО 
"Шадринский государственный педагогический университет"; 
Полякова Е.Н. – канд. пед. наук, доцент,  
кафедра "Безопасность информационных и автоматизированных систем",  
директор института математики и интеллектуальных систем,  
ФГБОУ ВО "Курганский государственный университет" 
 
 
Слинкин Д.А.  
С47    
Эффективность 
реализаций 
императивных 
языков 
программирования в решении олимпиадных задач: монография / 
Д.А. Слинкин. — Москва : ФЛИНТА, 2024. — 150 с. — ISBN 978-59765-5654-6 (ФЛИНТА); ISBN 978-5-87818-739-8 (ШГПУ). — Текст : 
электронный. 
 
В монографии рассматриваются методы оценки эффективности 
использования различными языковыми реализациями императивных 
языков 
программирования 
основных 
ограничивающих 
атрибутов 
вычислительной системы при решении олимпиадных задач - времени 
исполнения программного кода и объема задействованной оперативной 
памяти. Разработанное в рамках монографии программное обеспечение 
позволит широкому кругу исследователей проверить полученные выводы 
на различных программно-аппаратных платформах и задачах различного 
уровня время- и ресурсоемкости. 
Результаты исследования могут быть использованы при формировании стратегий решения задач олимпиад по программированию. 
 
    УДК 37.016:004.42 
    ББК 74.263.2 
 
ISBN 978-5-9765-5654-6 (ФЛИНТА) 
ISBN 978-5-87818-739-8 (ШГПУ). 
© Слинкин Д.А., 2024 
© ШГПУ
, 2024 
 
 
 
 
2 

ОГЛАВЛЕНИЕ 
Введение ............................................................................................................ 5 
1. Практика проверки решений олимпиадных задач .................................... 7 
1.1. Системы проведения олимпиад и проверки решений 
........................... 7 
1.2. Выбор языков программирования ..........................................................11 
2. Методы оценки эффективности решений олимпиадных задач 
............. 18 
2.1. Оценка скорости выполнения программ .............................................. 18 
2.2. Оценка требований к объему оперативной памяти  
для программ 
................................................................................................... 45 
3. Анализ эффективности решений олимпиадной задачи. 
......................... 53 
3.1. Условие задачи "плац"............................................................................. 54 
3.2. Разработка алгоритмов решения 
............................................................ 57 
3.3. Поддержка рекурсии в реализациях языков программирования ....... 59 
3.4. Алгоритм rec4fill 
...................................................................................... 62 
3.5. Алгоритм rec2fill 
...................................................................................... 67 
3.6. Алгоритм stackfill .................................................................................... 70 
3.7. Алгоритм stackfill - расширенное исследование 
.................................. 77 
Заключение 
...................................................................................................... 96 
Список использованных источников 
............................................................ 98 
Приложения 
................................................................................................... 101 
Приложение 1. Оценка времяемкости и ресурсоемкости  
программного кода. ...................................................................................... 101 
Приложение 2. Вспомогательные программы 
........................................... 110 
3 

Приложение 3. Программы для решения олимпиадной задачи  
"плац" 
............................................................................................................. 124 
Приложение 4. Результаты исследования решений олимпиадной  
задачи  "плац" 
................................................................................................ 140 
 
 
 
 
4 

ВВЕДЕНИЕ 
 
Согласно стандартам "ГОСТ Р ИСО/МЭК 9126-93 Информационная 
технология. Оценка программной продукции. Характеристики качества и 
руководства по их применению" [2] и "ГОСТ 28806-90 Качество программных 
средств. Термины и определения" [3], оценка эффективности программного 
продукта определяется на основании его время- и ресурсоемкости. Первый 
набор атрибутов относится к временам отклика и обработки, к скоростям 
выполнения 
функций 
программного 
продукта. 
Второй 
- 
к 
объему 
используемых ресурсов (внутренних и внешних) и продолжительности такого 
использования.  
В 
рамках данной монографии мы рассмотрим методы оценки 
эффективности 
использования 
различными 
языковыми 
реализациями 
основных ограничивающих атрибутов   вычислительной системы при решении 
олимпиадных задач - времени исполнения программного кода и объема 
задействованной 
памяти, 
проанализируем 
возможности 
оптимизаций 
решений 
языковыми 
средствами, 
проведем 
практическую 
оценку 
эффективности набора решений одной из ресурсоемких олимпиадных задач.  
В Шадринском государственном педагогическом университете более 20 
лет проводятся олимпиады по программированию, к участию в которых мы 
приглашаем школьников и студентов различных направлений подготовки. В 
отличие от многих других олимпиад, мы не используем готовые решения, 
наши задачи создаются и предварительно прорешиваются оргкомитетом 
олимпиады самостоятельно. Задачи часто сопровождаются художественной 
фабулой - злободневной, фантастической или приключенческой, позволяющей 
создать для участника уникальную атмосферу сопричастности к решаемой 
проблеме. 
Мы 
разрешаем 
использовать 
императивные 
языки 
программирования, 
со 
статической 
и 
динамической 
типизацией, 
интерпретируемые и компилируемые: Pascal, C/C++, Python, PHP и др.  
Во многих случаях решения задач проверяются как на обычных тестах, не 
предполагающих задействование граничных условий, так и на крэш-тестах, 
объемных по входным или выходным данным, либо требующим применения 
оптимальных алгоритмов, которые позволяют резко снизить вычислительную 
сложность решения, чтобы уложится в олимпиадные ограничения по времени 
или объему памяти.  
В некоторых случаях выбор оптимального языка программирования 
позволяет решить одну задачу без оптимизации алгоритма, но при этом 
особенности выбранного языка диктуют высокий уровень усложнения 
5 

решения для другой задачи. С учетом разноплановости предлагаемых задач, 
все 
участники, 
специализирующиеся 
на 
каком-то 
одном 
языке 
программирования, находятся примерно в равных условиях, а преимущество 
получают 
те, 
кто 
владеет 
несколькими, 
желательно 
максимально 
отличающимися друг от друга языками. Дополнительно, определенное 
преимущество получают те участники, кто глубоко специализируется на 
компилируемых языках, что дает им, при прочих равных условиях, 
многократное превышение скорости исполнения программы по сравнению с 
интерпретируемыми языками. 
Таким образом, знание нескольких языков программирования, как 
минимум - одного компилируемого и одного интерпретируемого, позволяют 
эффективно решать задачи наших олимпиад. 
Оценка эффективности работы программ невозможна в отрыве от 
конкретной программно-аппаратной платформы, специфика которой, с одной 
стороны, влияет на полученные результаты, с другой - позволяет выявить 
особенности и закономерности как самой платформы, так и реализаций языков 
программирования, применяемых языковых средств и алгоритмов решений. В 
рамках данной монографии в качестве целевой платформы мы будем 
использовать компьютер с микропроцессором Intel(R) Core(TM) i7-1065G7 
CPU @ 1.30GHz и операционной системой Linux на базе девятой платформы 
ОС Альт [4]. На этой-же системе будем проверять работу всех программ и 
скриптов. Выбор в качестве платформы компиляции и выполнения программ 
ОС Linux, обусловлен, прежде всего, применением ee не только для наших 
олимпиад, но и для множества контест-систем и онлайн-компиляторов, таких 
как contest.yandex.ru, www.onlinegdb.com, www.jdoodle.com и многих других. 
 
 
6 

1. ПРАКТИКА ПРОВЕРКИ РЕШЕНИЙ ОЛИМПИАДНЫХ ЗАДА
Ч 
1.1. Системы проведения олимпиад и проверки решений 
Для проверки решений задач в режиме реального времени мы используем 
связку из двух виртуальных машин на базе ОС Linux. На первой развернута 
LMS Moodle [22], с заранее подготовленными условиями задач и средствами 
проверки решений в виде тестовых заданий на базе плагина CodeRunner [12]. 
Вторая содержит Jobe-сервер [32] с подготовленными интерпретаторами и 
компиляторами, на котором запускаются решения участников олимпиады. 
Указанный набор программного обеспечения реализует используемую нами 
автоматизированную локальную систему проведения олимпиад (в 
дальнейшем 
- 
АЛСПО). 
Локальность 
подразумевает 
возможность 
функционирования данной системы внутри локальной сети, без доступа к сети 
Интернет.  
Способы ввода и вывода данных в системе строго регламентированы: 
стандартный поток ввода и стандартный поток вывода. Использование файлов 
и стандартного потока ошибок не оценивается. Исходные данные подаются на 
стандартный поток ввода, результатом решения задачи считается набор строк 
стандартного потока вывода.  
Решения задач проверяются на наборах тестов, которые включают в себя  
1) тесты из условия задач 
2) сгенерированные тесты, включающие в себя случайный набор данных 
в определенных диапазонах 
3) тесты на проверку простых граничных условий 
4) тесты на проверку сложных граничных условий (крэш-тесты) 
Информация об особенностях тестов до участников не доводится. 
Участники информируются о том, что все тесты оцениваются одинаково, в 
процентах. Для организации ответственного подхода к проверке решений мы 
используем штрафной режим, позволяющий "бесплатно" проверить первых 
три варианта решения и снимающий по 1 проценту конечного результата за 
каждую последующую проверку.  
Ограничения на каждый тест: по времени - 1 секунда, по памяти - 256 
мегабайт. К сожалению, от классического олимпиадного ограничения по 
памяти в 16 мегабайт пришлось отказаться, так как интерпретируемые языки 
требуют наличия программы-интерпретатора в оперативной памяти, и 
невозможно разграничить внешними средствами объем памяти, который 
занимает интерпретатор, от объема памяти, который задействует в своих целях 
программа. 
7 

Участник может получить несколько типов результатов прохождения 
теста, из которых баллы присуждаются только за верно пройденный тест, 
остальные представляют собой различные варианты ошибок, от неверного 
результата до ошибок компиляции, времени исполнения или выхода за 
ограничения. 
В отдельных случаях мы проводим олимпиады с использованием 
автоматизированных 
внешних 
систем 
проведения 
олимпиад 
(в 
дальнейшем - АВСПО), в подавляющем большинстве случаев - с помощью 
Яндекс.Контест [8]. Принципы доступа к условиям задач, передачи решений, 
получения результатов проверки, обеспечение ресурсных ограничений схожи в 
таких системах с АЛСПО. Но по сравнению с локальным решением, 
использование внешней контест-системы обладает рядом как достоинств, так 
и недостатков.  
Среди достоинств Яндекс.Контест можно выделить: 
1. Отсутствие необходимости в развертывании и поддержке собственной 
программно-аппаратной серверной платформы. 
2. Специализацию на соревновательном процессе и, как следствие, 
отсутствие интерфейсных и функциональных элементов, сторонних для 
соревновательного процесса.   
3. 
Возможность 
использования 
более 
25 
реализаций 
языков 
программирования. 
4. Асинхронную проверку решений. 
Недостатками Яндекс.Контест являются: 
1. Функционирование в режиме "черного ящика".  
2. Невозможность проведения соревнований в локальной сети, при 
ограничениях доступа к сети Интернет. 
3. Невозможность модифицировать существующую реализацию языка 
программирования, изменить параметры компиляции/запуска программ.  
4. Невозможность добавить новую реализацию языка программирования 
В остальном, возможности Яндекс.Контест и АЛСПО коррелируют друг с 
другом, что позволяет, в общем случае, взаимозаменять их в зависимости от 
текущей ситуации, минимально модифицируя правила проведения олимпиад. 
 
В отдельных случаях мы используем полуавтоматическую систему 
проверки решений (в дальнейшем ПАСПР), представляющую собой набор 
программ-обработчиков на Bash и Free Pascal (Приложение 2). С помощью 
ПАСПР можно детально проанализировать поведение программ на каждом 
программном тесте. Для запуска программ с заданными лимитами на время и 
8 

память мы используем приложение runguard из состава jobe-сервера. Ссылки 
на программы-обработчики размещаются в каталоге с исходным кодом задач и 
набором тестов. Программы-обработчики обеспечивают (если требуется) 
компиляцию переданной программы и ее запуск, при необходимости 
неоднократный, проверяют корректность решения на предоставленных тестах, 
оценивают время ее работы, усредняют полученные результаты. 
Каталог с решениями каждой задачи содержит подкаталог tests, в 
котором, на произвольной глубине вложенности, находятся наборы пар 
тестовых заданий и ответов на них. Тестовые задания представляют собой 
файлы вида 01.in.txt, 02.in.txt и т.д, а ответы на них - файлы вида 01.out.txt, 
02.out.txt и т.д. Формат имени предполагает до 99 тестов на решение, но чаще 
всего их количество не превышает 20. При проверке олимпиадных решений 
файлы тестовых заданий направляются на стандартный ввод решения. 
Стандартный вывод решения сохраняется во временном файле, содержимое 
которого затем сравнивается утилитой с соответствующим ответом. В случае 
успеха сравнения тест считается успешно пройденным. Никакие другие 
результаты работы программ не оцениваются, завершение работы программы 
с кодом, отличным от нуля, считается ошибкой. 
 
ПАСПР используется в нескольких случаях: 
1. Для подготовки собственных решений составителями олимпиадных 
задач. Используемые скрипты позволяют оценивать не только корректность 
решений, но и ресурсные ограничения, а также обеспечивают многократный 
запуск решений с целью усреднения результатов проверок на ресурсные 
ограничения. Это упрощает процесс формирования проверочных тестов, в том 
числе креш-тестов, требующих для прохождения глубокой оптимизации 
алгоритма решения, без которой программа не преодолеет ресурсные 
ограничения. 
2. 
Для 
дополнительной 
оффлайн-проверки 
решений 
участников 
олимпиад, в случае возникновения претензий к системе или процессу 
автоматизированной проверки. Такие претензии часто возникают в ситуациях, 
когда 
решение, 
запускаемое 
и 
тестируемое 
участником 
олимпиады 
самостоятельно, на своем собственном компьютере, дает, с точки зрения 
участника, корректный результат и не выходит за пределы ограничений по 
времени и памяти, в то время как система автоматизированной проверки 
генерирует ошибки на том-же самом решении. В таком случае участник 
сможет провести проверку решения на тестах доступных примеров и своих 
9 

собственных тестах, с помощью того-же инструментария, которым пользуются 
составители олимпиадных задач. 
3. 
Для 
организации 
проведения 
олимпиад 
вне 
возможности 
использования АВСПО или АЛСПО. В таком случаем олимпиада обычно 
характеризуется минимальной автоматизацией проведения, отсутствием 
возможности проверки результатов в время, данное участникам для решения 
задач, сбором результатов и организацией проверки по окончании основного 
время олимпиады. В результате решения участников собираются единый пул и 
проверяются с помощью ПАСПР. Затем результаты проверки подвергаются 
дополнительной обработке для ранжирования участников. 
 
В полной мере обеспечить оценку эффективности реализаций языков 
программирования в решении олимпиадных задач нам позволит ПАСПР. В 
отличие от остальных рассмотренных систем, ПАСПР обладает максимальным 
потенциалом автоматизации, позволяет проводить массовую проверку готовых 
решений и получать результаты проверки в машинночитаемом формате, 
пригодном для дальнейшего анализа. 
 
10