Задачник Базовый курс EN

Свёрнутые стеки

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

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

Выведите общее число проб и k функций с наибольшим «всего»; при равенстве выше та, у которой больше «сама», а дальше — по имени в порядке байтов.

Вход

В первой строке n и k (1 ≤ n ≤ 10⁵, 1 ≤ k ≤ 100). Дальше n строк: цепочка и число проб (от 1 до 10⁶) через пробел. Имена функций непустые, не содержат точки с запятой и могут содержать пробелы, поэтому число проб отделено последним пробелом в строке. Все цепочки вместе — не больше 4 МБ.

Выход

В первой строке — общее число проб. Дальше не больше k строк: имя функции, «всего» и «сама» через пробел.

Примеры

Пример 1

Вход

6 5
main;load;read 30
main;sort;qsort;qsort;partition 25
main;sort;qsort;partition 20
main;sort;qsort;qsort;qsort;partition 10
main;report;format 10
main;sort;qsort 5

Выход

100
main 100 0
qsort 60 5
sort 60 0
partition 55 55
read 30 30

Ограничения

Время · Python: 6000 мс
Время · Go: 1500 мс
Память: 256 МБ
Проверка: 8 тестов

Разбор

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

1Подсказка 1

«Сама» — это просто последняя функция в цепочке. Вся трудность во «всего»: что будет, если функция стоит в цепочке дважды?

2Идея

Заведём два словаря: имя → «всего» и имя → «сама». Для каждой строки прибавим её число к «сама» последней функции, а к «всего» — каждой функции цепочки, но каждой по одному разу: сначала соберём имена цепочки во множество. Потом отсортируем имена по правилу из условия.

3Разбор

Почему по одному разу? «Всего» отвечает на вопрос: сколько времени прошло, пока функция была на стеке, то есть сколько ушло бы, если бы её вызов исчез вместе со всем, что она делает. Проба, которая застала рекурсивную функцию на глубине трёх вызовов, — всё равно одно мгновение. Если прибавлять за каждое появление, рекурсивная сортировка в примере получит 105 проб из 100, а в профиле рекурсивного кода «всего» вообще перестанет что-то значить. Так считают и настоящие инструменты: колонка cum в pprof и «total» в графах пламени.

Второй и третий тесты — настоящие профили отчёта о землетрясениях из статьи о профилировщиках, на Python и на Go. В профиле Python имена модулей вроде <frozen importlib._bootstrap> содержат пробелы — поэтому число отделяется последним пробелом, а не первым.

3+Решение

4Сложность

O(L + F log F), где L — длина входа, F — число разных функций: один проход по всем именам и сортировка.

5Типичные ошибки

Рекурсия считается дважды. Функция получает больше проб, чем было всего; четвёртый тест — рекурсия глубиной до сорока.
Разрезать по первому пробелу. Ломается на именах с пробелами во втором тесте.
Порядок при равенстве. Сначала «всего», потом «сама», потом имя — пятый тест состоит из ничьих.

Алгоритмы задачи

TEC Приём Профилировщики Не гадать, где программа тратит время, а посмотреть: выборочный профилировщик, cProfile и pprof, граф пламени. доля функции ± √(p(1−p)/N) 1 задача DS Структура данных Хеш-таблица Поиск, вставка и удаление по ключу в среднем за O(1): ключ превращается в номер ячейки массива. O(1) в среднем 2 задачи