6258 подписчиков

Парсинг Excel-файлов на Python на примере задачи из ЕГЭ по информатике

18 марта 202318 мар 2023

737

7 мин

Оглавление

Задача
Решение:
Код реализации решения через XLRD

Сегодня разберем с вами довольное сложное 22 задание. Здесь стоит дать пояснения. Составители ЕГЭ каждый раз выдумывают что-то новое, поэтому никогда не знаешь, что ожидать в следующий раз. Недавно на занятиях с учениками попалась задача, которая не решается обычными формулами, встроенными в Excel (во всяком случае я не знаю, как её автоматизировать средствами ТОЛЬКО Excel). И тут повезло, что таблица была небольшой, поэтому можно было решить задачу руками. Но я сразу же задумался над тем, а что если записей в ней было бы гораздо больше? Что если руками решать было бы не целесообразно, потому что это заняло бы бесконечно большое время, которого нет на экзамене? Как же тогда автоматизировать решение? Об этом мы сегодня с вами и поговорим... Заваривайте чай, здесь нужно будет посидеть и подумать.

Задача

В файле 22.xlsx (скачать с яндекс.диска) содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Будем говорить, что процесс B зависит от процесса A, если для выполнения процесса B необходимы результаты выполнения процесса A. В этом случае процессы могут выполняться только последовательно.

Информация о процессах представлена в файле в виде таблицы. В первой строке таблицы указан идентификатор процесса (ID), во второй строке таблицы  — время его выполнения в миллисекундах, в третьей строке перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс является независимым, то в таблице указано значение 0.

Определите минимальное время, через которое завершится выполнение всей совокупности процессов, при условии, что все независимые друг от друга процессы могут выполняться параллельно.

Типовой пример организации данных в файле:

Решение:

Рассмотрим упрощенную таблицу. По первым двум строкам видно, что процессы ID=1 и ID=2 независимые, они могут выполняться одновременно (параллельно), поэтому завершатся оба эти процесса за 4 миллисекунды. Процесс ID=3 зависит от выполнения процессов ID=1 и ID=2. Поэтому 3й процесс может выполнить только завершения 1го и 2го. Значит на завершение 3го процесса нужно 1 мс + 4 мс = 5 мс. Процесс ID=4 зависит от процесса ID=3, то есть ждет его завершения. Поэтому время до завершения 4го процесса складывается из времени, необходимого для его выполнения (это 7 мс), и времени ожидания зависимых процессов (в нашем случае 5 мс – ожидание завершения 3го процесса). Тогда время до завершения 4го будет 5 мс + 7 мс = 12 мс. Итак, самый длительный процесс 4й, поэтому все процессы завершатся за 12 мс.

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

Таблица с данными в задании предоставляется нам в виде файла с расширением .xlsx. Для решения необходимо будет отсортировать данные таким образом, чтобы процессы, от которых зависит наш текущий процесс, были описаны в таблице выше. Ну а в самом начале при такой сортировке должны оказаться несколько процессов, которые на зависят от других. Выполнить такую сортировку в Excel можно с помощью функции «Фильтр».

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

Таблица в примере более сложная. Давайте посмотрим на неё.

По таблице видно, что мы должны подождать 25 мс до выполнения всех процессов. Ведь это и есть время выполнения самого долгого процесса.

Как мы видим, можно решить «вручную», потому что таблица не слишком большая. Но что же делать, если таблица окажется очень большой? Тогда не получится сделать всё это от руки. Попробуем автоматизировать процесс с помощью Python. Нам понадобится считывать данные из excel-файла.

Первый метод, который можно осуществить, это парсинг с помощью библиотеки xlrd.
xlrd – это инструмент для чтения .xls файлов. Но тогда нам предварительно потребуется сохранить файл в расширении .xls вместо .xlsx.

Если эта библиотека отсутствует, то её можно установить с помощью команды (в терминал или командную строку, запущенную от имени администратора): pip install xlrd

Документация по библиотеке здесь: https://xlrd.readthedocs.io/en/latest/api.html#xlrd
Или здесь: http://ilnurgi1.ru/docs/python/modules_user/xlrd.html#

Замечание: Чтобы программа работала, файл (.xls) должен находиться в одной папке с программой.

Код реализации решения через XLRD

Открытие файла происходит через библиотеку xlrd (почитать тут или почитать тут). Далее формируется список процессов, где каждый процесс также представляет собой список, в котором:
1 элемент = ID/номер процесса
2 элемент = собственное время выполнения
3 элемент = строка, в которой написаны процессы, от которых зависит текущий процесс (разделяется ; )
4 элемент = полное время до выполнения с учетом всех зависимостей.

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

Что если нет возможности скачать и установить библиотеку xlrd ? Тогда можно воспользоваться стандартной библиотекой в Python. Для этого нам понадобиться наш файл .xlsx сохранить с расширением .csv. Структурно файл не изменится.

CSV – это вид файла, который позволит структурировать большие объемы файлов. Этот файл по умолчанию в windows открывается через Excel, но его можно легко открывать через текстовый редактор. Потому что по своей сути CSV является текстовым файлом, в котором каждый элемент отделяется от предыдущего каким-то разделителем (это может быть «;» или «,»). Данные CSV легко экспортировать в электронные таблицы обратно.

Замечание: Для парсинга/чтения CSV-файла необходимо знать какой именно разделить используется. Откройте файл в текстовом редакторе и посмотрите сами.

Замечание: Чтобы открыть файл через Python, нужно быть уверенным, что кодировки совпадут. В моем случае через Excel файл сохранился в .csv в кодировке Windows-1251. Посмотреть кодировку можно, например, в Notepad++:

Код реализации решения через CSV

Здесь логика такая же, как в предыдущем варианте. Только работать с CSV удобнее. Не нужно устанавливать эту библиотеку, она встроенная. Работаем с файлом как с обычным текстовым, в котором есть разделитель в виде точки с запятой. Открываем и считываем. Во втором варианте для хранения информации я выбрал список словарей. (Почитать про словари можно здесь). Потому что доступ по ключам в виде слов делает программу более понятной. Есть одна сложность при работе с ID. Нумерация ID начинается с 1, а нумерация элементов списка с нуля, поэтому образуется такой вот сложный индекс на строке 26.

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

Исходники на Github

github.com

GitHub - HaloMath/Parsing-Excel-files-in-Python: Parsing Excel files in Python on the example of a task from the Unified State Exam in computer science