Тренировки по алгоритмам 5.0 Лекция 3: Множества и словари

• Лекция посвящена множествам и словарям.  

• Рассматриваются три основные темы: устройство множеств, примеры задач и разборы.  

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

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

• Множества могут быть конечными или бесконечными.  

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

• Рассматривается множество чисел от 0 до 9.  

• Используется массив для хранения элементов.  

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

• Массив становится неэффективным для больших чисел.  

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

• Пример: остаток от деления на 10 для чисел от 0 до 9.  

• Хэш-функция преобразует большое число в маленькое.  

• Массив большого размера можно использовать для хранения множества.  

• Пример из жизни: проверка гостей на мероприятии по списку.  

• Хэш-функция равна остатку от деления числа на десять.  

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

• Пример: добавление числа 17 в список с хэш-функцией 7.  

• Проверка наличия числа в множестве: линейный поиск по списку с соответствующим значением хэш-функции.  

• Удаление элемента: линейный поиск, затем перемещение или удаление последнего элемента списка.  

• Хэш-функция может быть любой, главное, чтобы она отображала большое число в ограниченное множество.  

• Вывод всех элементов множества: обход всех возможных значений хэш-функции и вывод содержимого списков.  

• Пример: вывод чисел 17 и 27.  

• Реализация множества называется хэш-таблицей.  

• Множество может быть упорядоченным или неупорядоченным.  

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

• В данном случае элементы упорядочены по значению хэш-функции и порядку добавления.  

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

• Инициализация: создание десяти пустых списков.  

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

• Операция поиска: линейный поиск по списку.  

• Операция удаления: поиск элемента, перемещение последнего элемента списка и удаление.  

• Хэш-функция переводит большое множество в числа от 0 до N.  

• Хэш-таблица: набор списков разной длины.  

• Коллизии: случаи, когда разные элементы имеют одинаковое значение хэш-функции.  

• Пример коллизии: добавление чисел 17 и 87 с одинаковым значением хэш-функции 7.  

• В компьютерах все можно интерпретировать как числа.  

• Хэш-функции эффективны для неизменяемых объектов.  

• В Python неизменяемые строки не могут быть изменены после создания.  

• Изменяемые объекты требуют пересчета хэш-функции при каждом изменении.  

• В Python хэш-функции рассчитываются только для неизменяемых объектов.  

• Хэш-функции должны быть равномерно распределены.  

• Равномерное распределение ускоряет поиск.  

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

• Коэффициент заполнения показывает, сколько элементов в среднем в каждом списке.  

• При достижении коэффициента заполнения таблица расширяется.  

• Перестроение таблицы уменьшает коэффициент заполнения.  

• Можно уменьшать размер множества при низком коэффициенте заполнения.  

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

• Сложность добавления элементов оценивается как O n^2.  

• В худшем случае таблица расширяется на каждом шаге.  

• Практическая сложность может быть ниже из-за логарифмического роста.  

• Добавление элементов в таблицу происходит поэтапно.  

• Расширение таблицы происходит при достижении определенного количества элементов.  

• В среднем, добавление одного элемента занимает логарифмическое время.  

• Не каждое расширение таблицы требует n операций.  

• На первом шаге требуется одна операция, на втором - две и так далее.  

• В итоге, суммарное количество действий при расширении равно 2n.  

• Амортизированная сложность - это среднее время выполнения одной операции.  

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

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

• Словари устроены аналогично множествам, но с ключами и значениями.  

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

• В случае малого количества значений, лучше использовать массив.  

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

• Реализация: идем по числам и добавляем их в множество.  

• Сложность алгоритма - O n, так как проходимся по всему списку.  

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

• Злоумышленники могут использовать случайные начальные размеры таблиц.  

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

• Проверка, является ли длинное число числом Фибоначчи.  

• Числа Фибоначчи растут быстро, но явной формулы для проверки нет.  

• Решение: использовать множество из 40 тысяч чисел Фибоначчи.  

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

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

• Хранение остатков чисел Фибоначчи вместо самих чисел.  

• Вычисление суммы чисел Фибоначчи по модулю п.  

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

• Проверка остатка длинного числа среди множества остатков чисел Фибоначчи.  

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

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

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

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

• Добавление модулей при необходимости.  

• Проверка остатков по всем модулям для точного ответа.  

• Применение хэш-таблицы для хранения остатков.  

• Решение задачи без работы с длинными числами.  

• Ограничения вероятностного алгоритма и его применение в реальных системах.  

• На шахматной доске размером m на n находится m ладей.  

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

• Поле может быть до миллиарда на миллиард, что делает перебор пар ладей неэффективным.  

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

• Если ладьи бьют только до ближайшей, формула проста: количество ладей минус один.  

• Если ладьи бьют друг друга, формула сложнее: количество способов выбрать две ладьи из k.  

• Создаем словари для горизонталей и вертикалей.  

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

• Количество пар ладей равно количеству ладей минус один.  

• Есть словарь слов с ударными буквами и текст.  

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

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

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

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

• Если слово не найдено, проверяем, что в нем ровно одно ударение.  

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

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

• Если слово не найдено, проверяем количество ударений и увеличиваем счетчик ошибок.  

• Можно решать задачу с множествами или словарями.  

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

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

• На лит-коде задачи проще, чем на собеседованиях.  

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

• Лит-код полезен для стандартных задач, но тренировки предпочтительнее для сложных задач.  

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

• Бинарное дерево поиска может быть полезно для предотвращения деградации при атаке специальными значениями.  

• На собеседованиях важно правильно оценивать сложность функций, особенно для хэш-таблиц.  

• Сложность добавления элементов в хэш-таблицу зависит от реализации.  

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

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

• Остатки от деления можно считать по модулю любого числа.  

• Операции можно разбить на кусочки и считать по модулю нужного числа.  

• Пример с числами Фибоначчи объясняет, почему используются три модуля для уменьшения вероятности коллизий.  

• Модуль выбирается в зависимости от числа для проверки.  

• Строку можно интерпретировать как число в 256-битной системе счисления.  

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

• Радость от решения сложных задач.  

• Устранение списывающих участников.  

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

• Не стоит переживать, если не вошли в топ-200.  

• Главное – знание алгоритмов, а не бонусы.  

• Решение задач помогает подготовиться к собеседованиям.  

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

• Неправильное решение может пройти все тесты, но это редкость.  

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

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

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

• Хорошее решение должно укладываться в тайм-лимит.  

• Не стесняйтесь использовать нестандартные методы, если они работают.