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

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

• Это практически полезные темы, часто встречающиеся на практике.  

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

• Сортировка подсчётом — простой алгоритм для небольших массивов.  

• Пример: сортировка оценок от 1 до 5.  

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

• Пример: ученик получил оценки 5, 4, 3, 2, 1.  

• Создаём массив с индексами от 1 до 5 и увеличиваем счётчики для каждой оценки.  

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

• Сортировка подсчётом требует O(n) времени и O(n) памяти.  

• Пример: вывод оценок занимает O(n) времени.  

• Можно оптимизировать память, используя нулевые элементы массива.  

• Пример реализации на Python для нахождения минимального и максимального значений.  

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

• Заменяем элементы в последовательности на минимальные значения.  

• Пример: проверка, можно ли получить число 2021 из 1202.  

• Считаем, сколько раз каждая цифра встречается в обоих числах.  

• Если цифры совпадают, то перестановка невозможна.  

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

• Преобразование числа в строку и обработка символов неэффективны.  

• Пример с числом 2021: использование остатка деления на 10 для получения последней цифры.  

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

• Сравнение массивов цифр для определения их одинаковости.  

• Сложность сортировки подсчета O(n) для небольших значений k.  

• Сложность O(n + k) для больших значений k.  

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

• Ограничения: размер доски до миллиарда и количество ладей до 200 тысяч.  

• Решение задачи с использованием словаря для хранения количества ладей на каждой горизонтали и вертикали.  

• Сложность решения O(n) для шахматной доски размером 200 тысяч на 200 тысяч.  

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

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

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

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

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

• Функция добавляет единицу к значению элемента, если ладья уже существует.  

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

• Сложность решения составляет O(n), где n - количество ладей.  

• Решение не зависит от размера доски и количества ладей.  

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

• Идея та же: создание словарей для диагоналей и подсчет ферзей.  

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

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

• Сложность: O(n), где n - длина строки.  

• Для каждого символа создается элемент в словаре с нулевым значением.  

• Словарь сортируется для аккуратного вывода.  

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

• Решение не идеально из-за большого количества вызовов функции print.  

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

• Оптимизация вывода не имеет смысла для больших текстов.  

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

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

• Важно поддерживать простоту и поддерживаемость кода.  

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

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

• При больших значениях н, алгоритм справа работает быстрее.  

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

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

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

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

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

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

• Алгоритмы с хорошей симтотической сложностью часто выбираются.  

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

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

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

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

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

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

• Сомнения в эффективности при длинных словах.  

• Решение: использовать сортировку подсчетом для уникальных символов.  

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

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

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

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

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

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

• Решение задачи с использованием арифметической прогрессии.  

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

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

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

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

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

• Строгие правила могут мешать поиску подходящей команды, поэтому важно учитывать принятые в команде стандарты.  

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

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

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