Тренировки по алгоритмам от Яндекса. Лекция 4: «Словари и сортировка подсчётом»

• Лекция посвящена словарям, сортировке и подсчётам.  

• Обсуждаются практические применения в различных сферах деятельности.  

• Планируется обсуждение сортировки подсчётом, словарей и оптимизации.  

• Алгоритм сортировки подсчётом эффективен для массивов с небольшими числами.  

• Пример применения: сортировка школьных оценок от 1 до 5.  

• Стандартные алгоритмы сортировки работают медленно для таких задач.  

• При каждом встречном значении увеличивается счётчик.  

• Создаётся массив с индексами от 0 до количества значений.  

• Массив заполняется нулями, затем в нём увеличивается счётчик для каждого значения.  

• Последовательность оценок обрабатывается: при встрече значения счётчик увеличивается.  

• После обработки последовательности выводится отсортированный массив.  

• Пример: счётчик для пятёрки увеличивается три раза.  

• Время и память для создания массива: O(n) и O(k) соответственно.  

• Вывод отсортированного массива требует O(n) времени.  

• Возможность переноса интервала для экономии памяти.  

• Пример с температурой: интервал от 15 до 30 преобразуется в интервал от 0 до 14.  

• Перенос интервала усложняет отладку, но может быть полезен в некоторых случаях.  

• Использование функций min и max для определения количества возможных значений.  

• Создание массива из k нулей.  

• Перебор элементов, вычитание минимального значения и увеличение счётчика.  

• Изменение последовательности на месте.  

• Проверка возможности получения одного числа из другого путём перестановки цифр.  

• Пример: числа 2021 и 1202.  

• Решение: подсчёт количества повторений каждой цифры.  

• Сортировка подсчётом применима не только к числам, но и к цифрам и буквам.  

• Для сортировки букв можно определить их порядковый номер в алфавите и превратить в число.  

• В латинском алфавите 26 различных чисел, которые можно отсортировать и восстановить буквы.  

• Число можно преобразовать в строку и обрабатывать символы.  

• Можно отбрасывать последние цифры числа, деля его нацело на 10.  

• Пример: число 2021 делится нацело на 10, остаётся 202.  

• Отбрасывание цифр возможно только для чисел без ведущих нулей.  

• Число 0221 не подходит для такого метода, так как после обработки трёх цифр оно станет равным нулю.  

• Числа без ведущих нулей позволяют эффективно обрабатывать цифры.  

• Цифры добавляются в массив от 0 до 9.  

• Сравниваются массивы цифр для двух чисел.  

• Если количество цифр в массивах разное, числа состоят из разных цифр.  

• Вспомогательная функция создаёт массив для подсчёта вхождений цифр.  

• Пока число больше нуля, узнаётся последняя цифра и увеличивается количество вхождений для этой цифры.  

• Возвращается массив с количеством вхождений каждой цифры.  

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

• Числа встречаются с одним и тем же значением достаточно часто.  

• Сложность сортировки: O(n + k), где k — количество уникальных значений.  

• Словари — ассоциативная структура, позволяющая по ключу узнавать значение.  

• Реализованы как множества в Python, C++ или хэш-сеты в других языках.  

• Ключ должен быть неизменяемым объектом для эффективного вычисления хэша.  

• По значению в словаре искать нельзя, требуется перебирать все значения.  

• Сложность доступа по ключу выше, чем по индексу.  

• Словарь эффективен для разреженных данных, когда редкие элементы встречаются редко.  

• Задача: определить количество пар ладей,  

• Декомпозиция задачи для упрощения кода.  

• Получение массива координат пар номер строки и номер столбца.  

• Создание пустых словарей для подсчёта ладей в строке и столбце.  

• Функция получает номер строки или столбца и ключ для добавления ладьи.  

• Если в строке или столбце ещё нет ладьи, создаётся элемент словаря.  

• При добавлении ладьи значение элемента увеличивается на единицу.  

• Перебор ключей в словаре и прибавление значения минус один к парам.  

• Отсутствие ключей для нулей упрощает обработку.  

• Возврат суммарного количества пар.  

• Сложность решения зависит от количества ладей, а не от размера доски.  

• Операции добавления, увеличения и перебора выполняются за O(m).  

• Ферзи ходят по диагоналям, что усложняет задачу.  

• Диагонали определяются суммой и разностью координат ладей.  

• Использование четырёх словарей для диагоналей.  

• Создание словаря для подсчёта символов в строке.  

• Подсчёт количества вхождений каждого символа.  

• Сортировка ключей словаря и вывод гистограммы.  

• Нахождение максимального значения в словаре.  

• Перебор значений словаря в отсортированном порядке.  

• Вывод пробелов и решёток в зависимости от количества вхождений символа.  

• Много вызовов функции print снижает эффективность.  

• Предложение использовать список для более эффективного вывода.  

• Сложность задачи в худшем случае O(n^2).  

• Важность оставления задела под будущую оптимизацию.  

• Иногда проще реализовать менее эффективный алгоритм, чем тратить много времени на разработку.  

• Возможность быстрой переделки тормозящей части при необходимости.  

• Обсуждаются два алгоритма: линейный за 1000n и за 2nlogn.  

• Алгоритм с константой 1000 лучше при n > 2^500.  

• Логарифм от 2^500 равен 500, что делает алгоритм с константой 1000 предпочтительнее.  

• В реальных задачах ограничение n не всегда чётко понятно.  

• Пример с сортировкой оценок показывает разнообразие систем оценивания.  

• Для сервисов с большим количеством пользователей ограничение n может быть выше.  

• Важность потребления памяти: алгоритмы с одинаковой асимптотической сложностью могут потреблять разное количество памяти.  

• Время на реализацию и сложность поддержки также важны.  

• Возможность параллельного запуска алгоритмов может значительно повысить производительность.  

• Недостаток квалифицированных сотрудников может ограничить реализацию сложных алгоритмов.  

• Стоимость оборудования может быть ключевым фактором при выборе алгоритма.  

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

• Задача: сгруппировать слова по общим группам.  

• Очевидное решение: сортировка букв и использование словаря для группировки слов.  

• Проблема: сортировка длинных слов может занять много времени.  

• Использование сортировки подсчётом для оптимизации.  

• Вынесение функции подсчёта ключа для слова в отдельную функцию.  

• Профилирование для выявления проблемных участков.  

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

• Пример с подбором строки, которая ломает оптимизацию.  

• Цель: найти строку, которая сломает оптимизацию, и получить подарок от автора курса.  

• Оптимизация кода может привести к созданию сложных и непонятных функций.  

• Такой код сложно читать и поддерживать.  

• Рекомендуется разбивать длинные функции на более мелкие части.  

• Человек может одновременно обрабатывать около семи вещей.  

• Логические блоки кода должны быть выделены, даже если они используются один раз.  

• Количество строк кода должно соответствовать размеру экрана.  

• Ладьи не могут бить друг друга, если между ними нет других фигур.  

• Для решения задачи используется арифметическая прогрессия.  

• Формула арифметической прогрессии: n * n - 1 / 2.  

• На разных языках программирования существуют различные способы замены конструкций.  

• Важно быть готовым использовать эффективные решения в зависимости от языка.  

• На Python можно вывести данные быстрее, чем через стандартный `print`.  

• Для больших файлов данных можно использовать бинарный вывод или собственные буферы.  

• В задачах на собеседовании это не всегда необходимо.  

• В разных командах и компаниях приняты разные стандарты именования переменных.  

• Строгие правила могут помешать найму в подходящую команду.  

• Необходимо адаптироваться к правилам команды.  

• Алгоритмические задачи на стажировку часто не требуют проектирования иерархии классов.  

• Знание алгоритмов проверяется как хард-скил, а знание архитектуры — как софт-скил.  

• Разбиение на функции — основной элемент архитектуры в алгоритмических задачах.  

• Иногда проще написать простой код для одноразового использования, чем оптимизировать архитектуру.  

• Важно найти баланс между простотой и эффективностью кода.  

• Завершение лекции и прощание с аудиторией.