Обработка данных: сортировка и отбор

Представь размеры файлов: 8, 3, 6, 3 и 5 Кбайт. Если нужно найти два самых маленьких, удобнее расположить числа по возрастанию: 3, 3, 5, 6, 8. Такое упорядочивание называют сортировкой. Повторяющаяся тройка не исчезает: это два файла одинакового размера.

В Python sorted(values) создаёт новый упорядоченный список и не меняет исходный. По умолчанию числа идут от меньшего к большему. Добавка reverse=True меняет направление на убывание. Здесь True означает «да, перевернуть порядок». Списки и их позиции подробно разобраны в уроке «Списки», а различие способов сортировки — в уроке «Сортировка и поиск».

1sizes = [8, 3, 6, 3, 5]2print(sorted(sizes))                # [3, 3, 5, 6, 8]3print(sorted(sizes, reverse=True))  # [8, 6, 5, 3, 3]4print(sizes)                        # [8, 3, 6, 3, 5]

На экзамене чисел бывает слишком много, чтобы переписывать их в программу. Часто первая строка файла сообщает количество следующих записей, а сами значения начинаются со второй. Такую первую строку называют заголовком. Если принять её за очередной размер, ответ изменится.

Пусть файл sizes.txt содержит четыре строки: сначала 3, затем 7, 2 и 5. Тройка здесь означает количество размеров, а не размер файла. int(line) превращает текст строки в число, append добавляет его в список. Чтение файла подробнее разобрано в уроке «Файлы».

1with open("sizes.txt", encoding="utf-8") as source:2    count = int(source.readline())3    sizes = []4    for line in source:5        sizes.append(int(line))6 7print(count)          # 38print(sorted(sizes))  # [2, 5, 7]

Чтобы выполнить код, создай рядом с ним файл с указанными четырьмя строками. readline() читает ровно первую; последующий цикл получает остальные. Сравни count с len(sizes): если они различаются, файл прочитан неверно или неполон. Если строка содержит несколько значений, метод split() разделяет её по пробелам; каждую часть затем превращают в число отдельно.

В другом файле одна строка может описывать сразу несколько свойств объекта. Например, [2, 92] означает номер записи 2 и её 92 очка. Числа должны перемещаться вместе: если отсортировать только очки, их связь с номерами потеряется. Для сортировки таких записей нужно указать поле сравнения — здесь очки.

Параметр key получает правило, которое извлекает из каждой записи сравниваемое значение. Запись lambda record: record[1] означает: «получи запись и верни её второй элемент». lambda — короткая запись функции без имени; здесь её единственная работа — выбрать очки. Добавка reverse=True ставит большие очки первыми. При равных очках sorted сохраняет прежний взаимный порядок записей. Это свойство называют устойчивой сортировкой. В опубликованном уроке о сортировке записей подробнее показано, как выбрать поле.

1records = [[1, 75], [2, 92], [3, 92],2           [4, 84], [5, 75], [6, 92]]3ordered = sorted(records, key=lambda r: r[1], reverse=True)4print(ordered)5# [[2, 92], [3, 92], [6, 92], [4, 84], [1, 75], [5, 75]]6print(ordered[2][0])  # 6

В ordered[2][0] сначала выбирается третья запись, затем её первый элемент — номер. Три записи с 92 очками остались в прежнем порядке: 2, 3, 6. Если вместо сортировки по одному полю развернуть весь результат, порядок равных записей поменяется и правило задачи нарушится.

На носителе осталось 13 Кбайт, а файлы занимают 8, 6, 5, 4, 3 и 2 Кбайт. Нужно поместить как можно больше файлов. Если сначала взять размер 8, места для других останется мало. Если начать с самых маленьких, поместятся 2, 3 и 4: вместе 9.

Почему три — максимум? Любые четыре файла занимают не меньше, чем четыре самых маленьких: 2 + 3 + 4 + 5 = 14. Четвёрка уже не помещается. Выбор самого маленького доступного значения на каждом шаге называют жадным выбором. Он доказан здесь для цели увеличить количество при одинаковой важности каждого файла; в другой задаче правило придётся обосновать заново.

1sizes = sorted([8, 6, 5, 4, 3, 2])2capacity = 133used = 04chosen = []5for size in sizes:6    if used + size <= capacity:7        chosen.append(size)8        used += size9 10print(chosen)       # [2, 3, 4]11print(len(chosen))  # 3

Знак <= допускает точное заполнение. Например, при вместимости 9 файлы 2, 3 и 4 занимают место ровно целиком и должны учитываться. Строгое < отбросило бы эту тройку. После первого неподходящего размера оставшиеся, ещё большие размеры тоже не поместятся; просмотр продолжается только ради простоты кода.

Часто спрашивают два числа: сначала наибольшее количество файлов, затем наибольший размер одного файла среди наборов с таким количеством. Это разные вопросы. Выбор 2, 3, 4 даёт три файла, но самый крупный из них имеет размер 4. Можно заменить 4 на 8: сумма 2 + 3 + 8 = 13, количество остаётся три, а второй ответ становится 8.

Сначала находим максимальное количество count. Чтобы оставить место одному крупному файлу, остальные count - 1 берём самыми маленькими. Любой другой набор этих остальных файлов занимает не меньше места. Затем проверяем кандидатов на место последнего. В примерах ниже хотя бы один файл всегда помещается; если в иной задаче это не гарантировано, случай нулевого количества нужно разобрать отдельно.

В следующем коде sizes[:count - 1] берёт начало списка до позиции count - 1, не включая её. Такой фрагмент списка называют срезом. Здесь получатся размеры 2 и 3. Функция sum(...) складывает все числа среза: sum([2, 3]) равно 5.

1sizes = sorted([8, 6, 5, 4, 3, 2])2capacity = 133used = 04count = 05for size in sizes:6    if used + size <= capacity:7        used += size8        count += 19 10small_total = sum(sizes[:count - 1])11best_last = 012for index in range(count - 1, len(sizes)):13    if small_total + sizes[index] <= capacity:14        best_last = sizes[index]15 16print(count, best_last)  # 3 8

Срезы подробнее разобраны в уроке о списках. Цикл рассматривает остальные размеры по возрастанию. Каждое новое подходящее значение улучшает best_last. Равные размеры не удаляются: два файла одного размера остаются двумя элементами списка.

Не все задачи 26 устроены как список размеров. В проекте демонстрационного варианта 2027 года ФИПИ предложен журнал запросов сервера: у каждой строки есть время, номер клиента и объём данных. Память ограничена; перед запросом, который уже не помещается, накопленное копируют и очищают. Эту временную память называют буфером: в нём лежат данные запросов до копирования, а готовые копии хранятся отдельно. Здесь важен порядок событий: перестановка строк по объёму меняет размеры копий. Числа ниже придуманы специально для урока.

Запись — несколько значений об одном событии. В коде запись представлена тройкой (время, клиент, объём). Тройки уже идут по времени; при равном времени сохраняется порядок строк файла. Словарь totals хранит сумму объёмов отдельно для каждого клиента: ключом служит его номер. Незнакомый ключ начинаем с нуля. Словари подробнее разобраны в уроке Python.

В строке for time, client, volume in requests три имени слева получают три значения очередной записи по порядку: время попадает в time, номер клиента — в client, объём — в volume. Аналогично запись time, group, points = line.split() раздаёт трём переменным три части строки, разделённой пробелами. Количество частей и переменных должно совпадать.

В наших коротких данных строки уже расположены по времени. Если в другом файле они перемешаны, сначала выясни, в каком порядке их требуется обработать. Для хронологического порядка можно применить sorted(requests, key=lambda record: record[0]): здесь поле с номером 0 — время. При одинаковом времени устойчивый способ сортировки Python сохранит порядок строк файла. Если условие задаёт другое правило для равных времён, следуй именно ему.

Вместимость памяти равна 10. Первый запрос занимает 4, второй — 5: вместе 9. Третий объём 3 уже не помещается. Перед ним создаётся копия размером 9, а 3 начинает новое заполнение. При точном равенстве, например 4 + 6 = 10, копия не нужна. В этом примере временем копии считается время запроса, который не поместился.

1requests = [2    ("09:00:00", 1, 4),3    ("09:01:00", 2, 5),4    ("09:02:00", 1, 3),5    ("11:59:59", 2, 8),6    ("12:00:00", 3, 6),7]8capacity = 109used = 010totals = {}11early_copies = []12for time, client, volume in requests:13    if used + volume > capacity:14        if time <= "11:59:59":15            early_copies.append(used)16        used = 017    used += volume18    if client not in totals:19        totals[client] = 020    totals[client] += volume21 22print(totals)        # {1: 7, 2: 13, 3: 6}23print(early_copies)  # [9, 3]

Время можно сравнивать как текст только потому, что все строки имеют одинаковый формат ЧЧ:ММ:СС с ведущими нулями. Момент 11:59:59 входит в ограничение «не позднее», а 12:00:00 уже нет. Четвёртый запрос вызывает раннюю копию размером 3. Пятый вызывает копию размером 8, но после полудня. Содержимое, оставшееся в памяти, ещё не является сделанной копией.

Большой файл невозможно проверить глазами целиком. Создай маленький набор, где ответ виден вручную. Для отбора выпиши все допустимые группы и сравни их количество и самый крупный элемент. Для журнала запиши после каждой строки, сколько занято в памяти, нужна ли копия и как изменилась сумма клиента. Только после этого запускай ту же программу на большом файле.

Сюжеты задания 26 бывают разными. В одном условии ищут свободные места в ряду, в другом — выбирают занятия без наложения по времени, в третьем — считают продажи одинакового товара. Там тоже придётся читать записи и проверять границы, но правило выбора будет другим. Сначала выясни, что означает строка файла и какие записи можно объединять или сравнивать. Лишь затем решай, нужна ли сортировка и по какому полю.

Если у двух клиентов одинаковая максимальная сумма, ответ без дополнительного правила неоднозначен. Условие должно указать, какой номер выбрать, либо гарантировать единственного лидера. То же относится к случаю, когда до границы времени сделано меньше двух копий. В задачах урока эти случаи определены заранее.