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

В задании 26 дают файл с данными о сотнях объектов — файлах, товарах, заявках — и правила, по которым их выбирают или обслуживают. Вот задача, которую мы решим в этой теме:

«Входной файл 26-12.txt содержит заявки пассажиров, которые сдают багаж в камеру хранения. В заявке указаны время сдачи багажа и время освобождения ячейки (в минутах от начала суток). Ячейки пронумерованы начиная с 1. Багаж кладут в свободную ячейку с наименьшим номером; освободившуюся ячейку можно занять, начиная со следующей минуты после её освобождения. Если свободных ячеек нет, пассажир уходит. В первой строке файла — количество ячеек K, во второй — количество пассажиров N, в каждой из следующих N строк — время сдачи и время освобождения. Определите, сколько пассажиров сдадут багаж, и номер ячейки, в которую положит багаж последний из них.»

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

Начнём с файла, записей и сортировки — на них держатся все задачи темы. Тема состоит из шести подтем и дополнительного урока — у каждой своя страница:

1. Записи, сортировка и рейтинг — ты сейчас здесь: чтение файла, ключ сортировки, рейтинг.
2. Жадный выбор — больше всего файлов на диске, скидки.
3. Цепочки коробок и пары — матрёшка, грузы и контейнеры, детали двух видов.
4. Ряды, серии и группы — свободные места в рядах, линии на экране.
5. Интервалы и события — мероприятия в зале, простои, одновременная нагрузка.
6. Моделирование процесса — камера хранения, очереди; решим задачу темы.
7. Пары, окно и сложные цепочки — дополнительный урок для редких задач.

Что в задаче считается одним объектом и как хранить его в программе?

Объект — то, о чём одна строка файла: файл, товар, заявка. Его характеристики хранят вместе, одной записью, и сортируют записи целиком. В задаче темы объект — заявка пассажира: время сдачи и время освобождения.

Выбери объект и посмотри, из каких полей состоит его запись:

файл

размер

товар

цена, тип

мероприятие

время начала, время окончания

участник

идентификатор, баллы, штраф

занятое место

номер ряда, номер места

Сведения об одном объекте будем называть записью. Например, meeting = (120, 180) — одна запись о мероприятии: оно началось на 120-й минуте и закончилось на 180-й. Здесь используется кортеж: несколько значений, объединённых в одну последовательность. Отдельные элементы кортежа нельзя заменить присваиванием — для неизменяемой записи это удобно.

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

meetings = [(10, 50), (20, 30)]starts = sorted(m[0] for m in meetings)finishes = sorted(m[1] for m in meetings)print(*zip(starts, finishes))print(*sorted(meetings))

Мероприятий (10, 30) и (20, 50) не было: раздельная сортировка их выдумала. Исключение — условие прямо говорит о двух независимых наборах. Например, массы грузов и вместимости контейнеров могут быть двумя отдельными списками, несмотря на то что записаны в одних строках; такую задачу разберём в подтеме 3.

Как понять, что именно нужно сделать лучшим и что важнее, если критериев несколько?

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

Эти три вещи определяют алгоритм. Ограничение — правило, которое нельзя нарушать, например: суммарный размер файлов ≤ вместимость диска. Цель — величина, которую нужно сделать как можно больше или как можно меньше: количество сохранённых файлов → max. Вариант, удовлетворяющий ограничениям, называется допустимым. Лучший допустимый вариант по указанному критерию называется оптимальным.

Рассмотрим условие:

Сохранить максимальное количество файлов. Среди таких вариантов найти максимально возможный размер самого большого сохранённого файла.

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

Лучший вариант — Б. Вариант В проигрывает по первому, более важному критерию, и его 100 уже ничего не решает.

Такое сравнение называют лексикографическим: сначала сравнивают первый показатель, при равенстве — второй, затем третий и так далее. Термин связан со сравнением слов в словаре: сначала первая буква, при равенстве — следующая. Python сравнивает кортежи именно так, поэтому вариант можно записать парой «количество, размер»:

variants = [(6, 30), (6, 45), (5, 100)]print(max(variants))

Для любой задачи полезно заранее ответить на семь вопросов:

1. Что является объектом? Файл, товар, заявка…
2. Какие у него характеристики? Размер, цена, время…
3. Можно ли менять порядок — или порядок задан условием?
4. Что нельзя нарушать? Вместимость, совместимость, сроки…
5. Что оптимизируем первым? Количество, стоимость, длину…
6. Что оптимизируем при равенстве? Размер, номер, остаток…
7. Что именно выводим? Количество, значение, ID, позицию…

Порядок чисел в ответе и порядок критериев — разные вещи. В задаче могут сначала требовать максимального общего количества товаров, а в ответ просить количество товаров типа А и остаток денег.

Задачи бывают двух видов: в одних ты сам выбираешь лучший вариант, в других обязан выполнить описанную процедуру — например, принять пассажиров в порядке прихода, как в задаче темы. Первому виду посвящены подтемы 2–5, второму — подтема 6.

Как прочитать файл задачи темы?

Строго по описанию формата: в 26-12.txt сначала два числа в отдельных строках — K и N, — потом N строк по два числа. Вот начало файла:

301000397 404378 408753 822…

30 ячеек, 1000 пассажиров, первый сдаёт багаж в минуту 397 и забирает в 404. Читаем так же, строку за строкой:

with open('26-12.txt') as f:    k = int(f.readline())    n = int(f.readline())    requests = []    for i in range(n):        start, finish = map(int, f.readline().split())        requests.append((start, finish)) print(k, n, requests[:3])

with open(...) as f открывает файл и сам закроет его после блока. f.readline() читает очередную строку, и следующее чтение продолжает со следующей. split() делит строку '397 404' на части, map(int, ...) превращает их в числа, а start, finish = ... раскладывает по двум переменным. Заявка сохраняется кортежем — одной записью.

Универсального заголовка у файлов задания 26 нет: где-то в первой строке два числа, где-то они в разных строках, где-то заголовка нет вовсе. Сначала читай описание формата — выбери вариант:

вместимость и количество

S, n = map(int, f.readline().split())

количество и вместимость

n, S = map(int, f.readline().split())

два числа в разных строках

k = int(f.readline()), затем n = int(f.readline())

три числа в первой строке

n, m, k = map(int, f.readline().split())

Зачем сортировать записи и как задать, по какому полю?

Сортировка даёт порядок, на который опирается рассуждение: в отсортированном списке каждое следующее число не меньше предыдущего. Записи сравниваются по первому полю, при равенстве — по второму; другое поле задаёт ключ.

После a.sort() список [19, 8, 22, 12, 15] становится [8, 12, 15, 19, 22]. Поэтому, например, если очередной файл уже не помещается в оставшееся место, все следующие, ещё более крупные файлы тоже не поместятся. Для убывания пишут a.sort(reverse=True); sorted(a) создаёт новый отсортированный список и не меняет a.

Записи-кортежи обычная сортировка сравнивает по очереди: сначала первые числа, вторые — только при равенстве первых. Если нужно сортировать по второму числу, задают ключ — функцию, которая для каждой записи говорит, по какому значению её сравнивать. Короче всего это записать через lambda:

records = [(3, 8), (1, 9), (3, 2)]print(*sorted(records))print(*sorted(records, key=lambda record: record[1]))

Во второй строке записи упорядочены по второму числу: 2, 8, 9. Та же функция с именем выглядела бы так: def second_value(record): return record[1] и key=second_value.

Заявки задачи темы обрабатывают в порядке прихода — по времени сдачи. Это первое поле записи, поэтому хватает обычной сортировки:

requests.sort()print(requests[:3])

from math import log2 for n in (1000, 100_000):    print(n, round(n * log2(n)), n * (n - 1) // 2)

Как перевести правила рейтинга — «больше баллов выше, при равенстве меньше штраф» — в сортировку?

Записать правила ключом-кортежем по порядку важности: поле «чем больше, тем выше» — с минусом, «чем меньше, тем выше» — как есть.

Пусть записи имеют вид (student_id, score, penalty), а правила такие:

1. Больше баллов — выше.
2. При равенстве меньше штраф — выше.
3. При полном равенстве меньше ID — выше.

students = [    (31, 80, 12),    (7, 95, 20),    (19, 95, 12),    (4, 95, 12)]students.sort(key=lambda x: (-x[1], x[2], x[0]))print(*[s[0] for s in students])

Почему перед баллами минус? Потому что 95 > 80, но −95 < −80. Обычная сортировка по возрастанию поставит -95 раньше -80, значит, участник с 95 баллами окажется раньше участника с 80. Почему 4 раньше 19? Баллы и штраф совпадают, решает третий показатель.

reverse=True переворачивает порядок всего ключа. Если направления полей различаются, меняют знак у конкретных числовых показателей. С key=lambda x: (x[1], -x[2], -x[0]) и reverse=True получился бы тот же порядок, но такую запись легко перепутать; ключ с минусами читается как сами правила.

Нужно различать три числа:

• ID участника — значение из файла;
• индекс в списке — позицию, с которой работает Python;
• место в рейтинге — обычно индекс плюс один.

students[2][0] — это ID участника на третьем месте, здесь 7.

А если рейтинг строится по показателям, которых нет в файле, — сумме, среднему, числу двоек?

Сначала вычислить показатели для каждого участника, сложить их в запись вместе с ID и уже её сортировать.

Пусть за каждый вопрос викторины участник получил баллы: положительные за верный ответ, отрицательные за неверный, ноль — если не отвечал. Для одного участника:

scores = [5, -2, 0, 3, -1]total = 0positive = 0answered = 0for score in scores:    total += score    if score > 0:        positive += score    if score != 0:        answered += 1print(total, positive, answered)

Здесь total — сумма всех баллов, positive — сумма положительных баллов, answered — количество ненулевых ответов. После этого все показатели сохраняют вместе с ID в одну запись и сортируют записи.

Иногда показатели делят участников на группы. Например, в рейтинге сессии сначала идут студенты без двоек по убыванию среднего балла, затем студенты с двойками по возрастанию числа двоек, а внутри групп — по возрастанию ID. Среднее четырёх оценок не нужно делить: при одинаковом числе экзаменов больше среднее — больше сумма. Ключ записывает обе группы сразу:

marks = [    (10, 4, 4, 4, 5), (3, 5, 5, 4, 2),    (6, 5, 4, 4, 4), (1, 2, 2, 3, 3),    (8, 5, 5, 5, 4), (2, 3, 2, 4, 5),] def rating_key(r):    twos = r[1:].count(2)    if twos == 0:        return (0, -sum(r[1:]), r[0])    return (twos, 0, r[0]) print(*[r[0] for r in sorted(marks, key=rating_key)])

Первый элемент ключа — число двоек: у сдавших он 0, поэтому они впереди. Второй — сумма с минусом, только для сдавших; у несдавших там 0, и при равном числе двоек решает ID. Студенты 6 и 10 набрали по 17, поэтому выше тот, у кого меньше ID.

Кто проходит, если «проходят первые 30 %», а у следующего участника те же баллы, что у последнего прошедшего?

Решает точная формулировка: доля — это целая часть, а «и все с такими же показателями» сдвигает границу дальше, пока показатели совпадают.

Две разные формулировки:

Проходят первые 25 участников рейтинга.

и:

Проходят все, набравшие не меньше баллов, чем участник на 25-м месте.

Во втором случае пройти может больше 25 человек. Если граница задана долей — «первые 30 % мест», — её считают целой частью: k = n * 30 // 100. Затем, если условие добавляет «а также все с такими же показателями, как у последнего из них», границу сдвигают дальше, пока показатели совпадают. В таблице ниже записи — пары «сумма, количество ответов», уже упорядоченные:

table = [(90, 6), (85, 7), (80, 5), (80, 5),         (80, 6), (75, 4), (70, 8), (70, 9),         (60, 5), (55, 7)]k = len(table) * 30 // 100last = table[k - 1]while k < len(table) and table[k] == last:    k += 1print(len(table) * 30 // 100, k)

Первые 30 % — это 3 участника, последний из них — (80, 5). Четвёртый с теми же показателями тоже проходит, а (80, 6) на пятом месте — нет: сумма та же, но число ответов другое. Равенство для прохода иногда определяется только баллами, хотя сама таблица дополнительно упорядочена по ID. Какие показатели должны совпасть, решает условие, и смешивать эти правила нельзя.

Похожее правило — проходной и полупроходной балл. Мест S; группы с одинаковой суммой баллов берут целиком сверху, пока группа помещается в оставшиеся места. Сумма последней целиком поместившейся группы — проходной балл. Следующая сумма, группа которой уже не помещается целиком, — полупроходной балл: из этой группы оставшиеся места делят по дополнительным показателям, например по баллу за математику.

Пусть мест 4, а суммы — 250, 240, 240, 235, 235, 235: группы 250 и 240 занимают три места, проходной балл 240; трое с 235 на одно место целиком не помещаются, и 235 — полупроходной балл.

• Записьполя одного объекта — вместе, сортируют целиком
• Чтение файластрого по описанию формата
• Критериивторой решает только среди равных по первому
• Ключkey=lambda x: (-x[1], x[2], x[0])
• Показателисначала вычислить, потом сортировать
• Граница проходадоля — целая часть; равные последнему