Объяснение генераторов Python и комбинаторного взрыва
Я рад показать вам весь новый мир генераторов на Python и, надеюсь, привнесу немного математики во все ваши жизни (потому что каждому всегда нужно немного больше математики в своей жизни), а также объясню, почему проблемы со счетом действительно компьютерам это сложно сделать, поскольку они приводят к таким массовым выходам с невероятно маленькими изменениями на входе (см. ХАОС). Математики нашли способы сделать это проще (глядя на коэффициенты и бесконечные ряды), но это более сложно, чем необходимо для нашей цели. Я буду часто использовать термин набор, и для целей этой статьи это просто набор объектов.
Начнем с генераторов. Их название уместно, потому что они абсолютно близки по функциональности к генераторам абстрактной алгебры. Если вам не нравится математика, пропустите следующий абзац.
Группы - это особые типы множеств в математике, к которым привязан некоторый оператор (например, сложение). Генератор группы - это то, что может создать каждый элемент набора. Например, возьмем остатки всех чисел после деления на 3. Итак, набор будет {0, 1, 2}, либо число делится на 3, имеет остаток 1 или 2. Возьмем любое число, например 3, он имеет остаток 0. Если мы прибавим к нему 1 (4), теперь он будет иметь остаток 1, если мы снова прибавим к нему 1 (5), теперь он имеет остаток 2. Мы просто создали каждый элемент, просто добавив 1, поэтому 1 является генератором этого конкретного набора. По сути, таковы генераторы в Python.
Генераторы - это способ определения способа итерации по набору (коллекции объектов). Вы можете создать бесконечное множество, если хотите, например, вам нужен генератор для всех целых чисел больше 0 (натуральные числа).
Теперь, если вы впервые имеете дело с генераторами, вы заметите новое ключевое слово в приведенном выше коде - yield. Это ключевое слово похоже на return в том смысле, что это значение, возвращаемое из вызова, но в отличие от return, когда функция затем извлекается из стека, компьютер отслеживает, где вы в последний раз остановились. Если вы снова запросите этот конкретный экземпляр генератора для следующего элемента, он будет продолжаться до тех пор, пока не достигнет другого yield или завершения. Это означает, что генератор может пройти через набор только один раз, поскольку он действительно знает только, как получить следующий элемент, и не отслеживает его положение по отношению к самому набору.
Причина создания этого поста заключается в том, что я натолкнулся на распространенный вопрос на техническом собеседовании в Интернете и решил использовать генератор для его решения. В вопросе говорилось:
По заданной строке «abcde» найдите и произведите все ее уникальные перестановки. Например, «bcdea» - это уникальная перестановка.
Сначала код:
Первый вопрос, который, вероятно, задают те, кто впервые столкнулся с генераторами, - зачем их использовать? Они ленивы.
Они получат следующий элемент в наборе только по запросу. Он не тратит много времени, пытаясь захватить все элементы, он просто захватывает следующий элемент, затем останавливается и ждет повторного запроса. Это делает время вычислений более модульным! Вы получите его тогда, когда вам это нужно!
Когда дело доходит до комбинаторного вопроса вроде этого, это может быть невероятно полезно, скажем, вам нужны только первые 10 перестановок? Первые 20? Вы можете использовать ту же функцию для любого количества (до завершения) перестановок. Это позволяет вам разбить эти массивные вычислительные задачи на небольшие части, так как поиск уникальных перестановок может быть огромной задачей для компьютеров.
При работе с генераторами следует помнить о том, что они требуют, чтобы у вас была какая-то способность знать, как получить следующий элемент в наборе. Должна быть какая-то связь со всеми элементами в наборе, чтобы вы могли создать код для поиска следующего!
Это действительно все, что касается генераторов в Python, это фантастические инструменты, которые позволяют вам добавить ленивую оценку в арсенал Python. Я надеюсь, что эта статья воодушевит вас поиграться с генераторами и посмотреть, насколько они на самом деле мощны!
Я оставляю вас с последним видео о комбинаторном взрыве:
Примечание: вот репо с некоторыми алгоритмами, которые я считаю крутыми и полезными! В нем приведены некоторые общие алгоритмы, используемые для перестановок - проверьте это здесь.
