однострочники пайтон. Однострочники Python лаконичный и содержательный код by Кристи. Однострочники
 Скачать 4.44 Mb.
|
|
Листинг 6.8. Поиск всех простых чисел, не превышающих максимального числа m # Поиск всех простых чисел <= m m = 20 primes = [n for n in range(2,m+1) if prime(n)] print(primes) # [2, 3, 5, 7, 11, 13, 17, 19] Для создания списка всех простых чисел, не превышающих m , мы вос- пользовались списковым включением (см. главу 2). Включение в алгоритм цикла for означает необходимость m вызовов функции is_prime(n) , так что временная сложность ограничивается m**2 . Количество операций растет квадратично относительно m . Поиск всех простых чисел меньше m = 100 может потребовать до m**2 = 10000 операций! А теперь мы создадим однострочник, резко сокращающий подобные затраты времени. 234 Глава 6. Алгоритмы Код С помощью этого однострочника мы напишем алгоритм для поиска всех простых чисел, не превышающих максимального целого числа m , более эффективный, чем наша наивная реализация. Однострочник в листинге 6.9 основывается на древнем алгоритме под названием «решето Эратосфена», о котором я расскажу в этом подразделе. Листинг 6.9. Однострочное решение, реализующее решето Эратосфена ## Зависимости from functools import reduce ## Данные n=100 ## Однострочник primes = reduce(lambda r, x: r - set(range(x**2, n, x)) if x in r else r, range(2, int(n**0.5) + 1), set(range(2, n))) ## Результат print(primes) # {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, # 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97} Вероятно, вам понадобятся еще некоторые предварительные знания, чтобы понять происходящее. Принцип работы Откровенно говоря, я сомневался, включать ли этот однострочник в книгу из-за его запутанности, сложности и неудобочитаемости. Тем не менее именно такой код вы встретите на практике, и с помощью книги я хочу гарантировать, что вы сможете понять каждую его строку, даже если это займет немало време- ни. На одну из версий данного однострочника я натолкнулся на StackOverflow. Он является вольной интерпретацией древнего алгоритма под названием решето Эратосфена, предназначенного для вычисления простых чисел. ПРИМЕЧАНИЕ Я внес некоторые изменения в первоначальный однострочник StackOver- flow ради ясности. На момент написания данной книги первоначаль- ный однострочник можно было найти здесь: https://stackoverflow.com/ questions/10639861/python-prime-generator-in-one-line/. Поиск простых чисел с помощью решета Эратосфена 235 Алгоритм решета Эратосфена По существу, данный алгоритм создает огромный массив чисел, от 2 до m , заданного максимального целого числа. Все числа в массиве — кандидаты на роль простых чисел, то есть алгоритм считает их потенциально (но не обязательно) простыми. В ходе алгоритма кандидаты, которые не могут быть простыми, отсеиваются. И лишь оставшиеся после этого процесса фильтрации числа окончательно считаются простыми. Для этого алгоритм вычисляет и помечает в массиве те числа, которые не являются простыми. В конце его выполнения все непомеченные числа — заведомо простые. Данный алгоритм повторяет следующие шаги. 1. Начинает с первого числа 2 и увеличивает его на единицу на каждом шаге процесса до тех пор, пока не будет найдено простое число x. Мы знаем, что x простое, если оно осталось непомеченным, ведь в этом случае ни одно меньшее x число не является его делителем, а это и есть определение простого числа. 2. Помечаем все числа, кратные x, поскольку они также не являются простыми: делителем для них является число x. 3. Простая оптимизация: начинаем помечать кратные числа, начиная с числа x × x, а не 2x, поскольку все числа между 2x и x × x уже помече- ны. Существует простое математическое доказательство этого факта, которое я опишу далее. А пока просто поверьте, что можно начинать помечать с x × x. Этот алгоритм показан пошагово на рис. с 6.6 по 6.11. Изначально все числа от 2 до m = 100 не помечены (незакрашенные ячейки). Первое непомеченное число — 2 — простое. Переходим к следующему непомеченному числу, 3. Поскольку оно еще не помечено, значит, простое: мы пометили все числа, кратные числам меньше текущего числа 3, так что никакое меньшее число не является его делителем. И, по определению, число 3 — простое. Помечаем все числа, кратные 3, по- скольку они — не простые, начиная с числа 3 × 3, так как все кратные 3 числа между 3 и 3 × 3 = 9 уже помечены. 236 Глава 6. Алгоритмы Рис. 6.6. Начальное состояние решета Эратосфена Рис. 6.7. Помечаем все числа, кратные 2, как не простые. Игнорируем в оставшейся части алгоритма все помеченные числа Переходим к следующему непомеченному числу, 5 (которое тоже простое). Помечаем все числа, кратные 5. Начинаем с числа 5 × 5, поскольку все крат- ные 5 числа между 5 и 5 × 5 = 25 уже помечены. Поиск простых чисел с помощью решета Эратосфена 237 Рис. 6.8. Помечаем все числа, кратные 3, как не простые Рис. 6.9. Помечаем все числа, кратные 5, как не простые Переходим к следующему непомеченному числу, 7 (которое тоже простое). Помечаем все числа, кратные 7. Начинаем с числа 7 × 7, поскольку все крат- ные 7 числа между 7 и 7 × 7 = 49 уже помечены. 238 Глава 6. Алгоритмы Рис. 6.10. Помечаем все числа, кратные 7, как не простые Переходим к следующему непомеченному числу, 11 (которое тоже простое). Помечаем все числа, кратные 11. Мы должны начать с числа 11 × 11 = 121, но понимаем, что оно превышает наш максимум m = 100. Так что алгоритм завершается. Все оставшиеся непомеченными числа не делятся ни на какое число, а значит, являются простыми. Рис. 6.11. Помечаем все числа, кратные 11, как не простые Поиск простых чисел с помощью решета Эратосфена 239 Решето Эратосфена намного эффективнее, чем «наивный» алгоритм, по- скольку последний проверяет все числа независимо друг от друга, без учета всех предыдущих вычислений. Решето же Эратосфена, напротив, повторно использует результаты предыдущих шагов вычислений — частый прием во многих сферах оптимизации алгоритмов. Каждый раз, вычеркивая число, кратное простому, мы, по существу, избавляем себя от утомительной работы по проверке того, является ли это число простым: мы заранее знаем, что оно им не является. Наверное, вы недоумеваете, почему мы начинаем помечать числа с квадрата простого, а не самого простого. Например, в алгоритме на рис. 6.10 мы только что обнаружили простое число 7 и начали помечать с числа 7 × 7 = 49. Дело в том, что все остальные кратные числа (7 × 2, 7 × 3, 7 × 4, 7 × 5, 7 × 6) мы уже пометили на предыдущих итерациях, когда помечали числа, кратные всем числам, меньшим нашего текущего простого числа 7: 2, 3, 4, 5, 6. Пояснения к однострочнику Досконально понимая алгоритм, мы можем наконец приступить к изучению нашего однострочного решения: ## Однострочник primes = reduce(lambda r, x: r - set(range(x**2, n, x)) if x in r else r, range(2, int(n**0.5) + 1), set(range(2, n))) В этом однострочнике для удаления по одному всех помеченных чисел из начального множества чисел от 2 до n (в однострочнике: set(range(2, n)) ) используется функция reduce() Это множество служит начальным значением множества непомеченных значений r , поскольку изначально все значения не помечены. Далее одно- строчник проходит по всем числам x от 2 до квадратного корня из n (в одно- строчнике: range(2, int(n**0.5) + 1) ) и удаляет из множества r все числа, кратные x (начиная с x**2 ), но только если число x — простое, то есть не удалено на текущий момент из множества r Потратьте 5–15 минут, чтобы прочитать это объяснение снова, и вниматель- но изучите все части данного однострочника. Я обещаю, что вы потратите это время не напрасно и в результате существенно улучшите свои навыки понимания кода на языке Python. 240 Глава 6. Алгоритмы Вычисление последовательности Фибоначчи с помощью функции reduce() Знаменитый итальянский математик Фибоначчи (Лео нардо Пизанский) от- крыл числа Фибоначчи в 1202 году, неожиданно обнаружив, что они играют важную роль в различных сферах: математике, искусстве и биологии. В этом разделе я покажу вам, как вычислить их с помощью одной строки кода. Общее описание Ряд Фибоначчи начинается с чисел 0 и 1, а каждое последующее число равно сумме двух предыдущих элементов ряда. Ряд Фибоначчи представляет со- бой готовый алгоритм! Код В листинге 6.10 вычисляется список первых n чисел Фибоначчи, начиная с 0 и 1. Листинг 6.10. Вычисление последовательности Фибоначчи в одной строке кода на Python ## Зависимости from functools import reduce ## Данные n = 10 ## Однострочник fibs = reduce(lambda x, _: x + [x[-2] + x[-1]], [0] * (n-2), [0, 1]) ## Результат print(fibs) Взгляните на код и попробуйте угадать результаты его выполнения. Принцип работы Мы опять воспользовались замечательной функцией reduce() . Вообще говоря, она удобна, когда необходимо агрегировать вычисляемую на ходу информацию о состоянии, например на основе только что полученных чисел Фибоначчи вычислить следующее число Фибоначчи. С помощью Вычисление последовательности Фибоначчи с помощью функции reduce() 241 спискового включения реализовать подобное непросто (см. главу 2), ведь оно не позволяет обычно обращаться к только что созданным им значе- ниям. Мы передаем в функцию reduce() три аргумента, соответствую- щие reduce(функция, итерируемый_объект, начальное_значение) , чтобы последовательно добавлять новые числа Фибоначчи в объект-агрегатор, включающий по одному значению за раз из итерируемого_объекта , по за- даваемому функцией сценарию. АЛЬТЕРНАТИВНОЕ РЕШЕНИЕ Суммирование раз за разом двух чисел Фибоначчи — простая идея, ле- жащая в основе однострочника из листинга 6.10. В листинге 6.11 приведено другое красивое решение. Листинг 6.11. Однострочное решение для поиска чисел Фибоначчи другим путем n = 10 x = [0,1] fibs = x[0:2] + [x.append(x[-1] + x[-2]) or x[-1] for i in range(n-2)] print(fibs) # [0, 1, 1, 2, 3, 5, 8, 13, 21, 34] Этот фрагмент кода прислал один из подписчиков моей рассылки (не стесняйтесь присоединяться к ней по адресу https://blog.finxter.com/subscribe/ ), в нем используется списковое включение с побочным эффектом: перемен- ная x обновляется новым элементом ряда Фибоначчи (n-2) раз. Обратите внимание, что функция append() не возвращает значения, а только None , эквивалентное False . Таким образом, оператор спискового включения генерирует список целых чисел на основе следующей идеи: print(0 or 10) # 10 На первый взгляд кажется, что нельзя производить операцию or над двумя целыми числами, но, как вы помните, в основе типа Boolean лежит тип integer. Любое отличное от нуля целочисленное значение интерпретиру- ется как True . Таким образом, операция or позволяет просто возвращать второе целочисленное значение, вместо того чтобы преобразовывать его в булево значение True . Очень изящный фрагмент кода Python! 242 Глава 6. Алгоритмы Объектом-агрегатором тут служит простой список с двумя начальными значениями: [0, 1] . Напомним, что объект-агрегатор передается функции в качестве первого аргумента (в нашем примере x ). Второй аргумент — следующий элемент из итерируемого_объекта . Мы за- дали (n–2) фиктивных значения в качестве начального значения итериру- емый_объект , чтобы заставить функцию reduce() выполнить функцию (n–2) раз (чтобы найти первые n чисел Фибоначчи — первые два, 0 и 1, мы уже знаем). Чтобы показать, что фиктивные значения итерируемого_объекта нас не интересуют, мы воспользовались «мусорным» параметром _ и просто до- бавляем новые числа Фибоначчи, вычисленные как сумма двух предыдущих чисел Фибоначчи, в конец списка агрегатора x Резюмируя: вы научились работать еще с одним паттерном однострочников Python, а именно созданием с помощью функции reduce() списка, с дина- мическим использованием только что обновленных или добавленных эле- ментов для вычисления его новых элементов. Этот удобный паттерн очень часто встречается на практике. Рекурсивный алгоритм бинарного поиска В этом разделе вы узнаете о простом алгоритме, который обязан знать любой специалист по computer science: алгоритме бинарного поиска. У бинарного поиска есть множество важных приложений во многих реализациях простых структур данных: множеств, деревьев, ассоциативных массивов, хеширован- ных множеств, хешированных таблиц, хеш-карт и массивов. Эти структуры данных используются в любой нетривиальной программе. Общее описание Если коротко, алгоритм бинарного поиска (binary search algorithm) произво- дит в отсортированной последовательности l поиск конкретного значения x путем многократного сокращения размера этой последовательности вдвое, до тех пор, пока не останется только одно значение. Либо это будет искомое значение, либо его вообще не было в последовательности. Далее мы рассмо- трим эту общую идею подробнее. Например, представьте, что нужно найти в отсортированной последова- тельности значение 56. При «наивном» алгоритме мы бы начали с первого Рекурсивный алгоритм бинарного поиска 243 элемента списка, проверили, не равен ли он 56, и перешли к следующему, и так до тех пор, пока не проверили бы все элементы или нашли искомое зна- чение. В наихудшем случае алгоритм проверяет все элементы списка. Отсор- тированный список из 10 000 значений требует примерно 10 000 операций для проверки всех элементов списка на равенство искомому значению. На языке теории алгоритмов можно сказать, что сложность вычисления линейна относительно количества элементов списка. Алгоритм не использует всю доступную информацию, чтобы добиться максимальной эффективности. Первая часть полезной информации — то, что список отсортирован! С помо- щью этого факта можно создать алгоритм, которому, чтобы абсолютно точно выяснить, присутствует ли в списке искомый элемент, достаточно проверить лишь несколько элементов списка. Алгоритм бинарного поиска обходит лишь log 2 (n) элементов (логарифм по основанию 2). Для поиска в том же спи- ске из 10 000 элементов достаточно всего лишь log 2 (10 000) < 14 операций. При бинарном поиске предполагается, что список отсортирован в порядке возрастания. Алгоритм проверяет сначала элемент в середине списка. Если это срединное значение больше искомого, значит, все значения от середины и до последнего элемента списка больше требуемого. Искомое значение не входит в эту половину списка, так что одной операции достаточно, чтобы сразу отбросить половину элементов. Аналогично, если искомое значение больше срединного, то можно отбросить первую половину элементов списка. А затем эта процедура сокращения вдвое фактического размера списка проверяемых элементов повторяется на каждом шаге алгоритма. На рис. 6.12 приведен наглядный пример. Рис. 6.12. Пример работы алгоритма бинарного поиска 244 Глава 6. Алгоритмы Если подсписок содержит четное количество элементов, то явного срединно- го элемента не существует. В этом случае мы округляем индекс срединного элемента. Нам нужно найти значение 56 в отсортированном списке из восьми цело- численных значений, просмотрев при этом как можно меньше элементов. Алгоритм бинарного поиска проверяет расположенный посередине (с учетом округления) элемент x и отбрасывает половину списка, в которой 56 заве- домо не может быть. У этой проверки могут быть три исхода: элемент x больше 56. Алгоритм игнорирует правую часть списка; элемент x меньше значения 56. Алгоритм игнорирует левую часть списка; элемент x равен 56, как на последней строке рис. 6.12. Поздравляем — мы нашли искомое значение! В листинге 6.12 показана реализация алгоритма бинарного поиска. Листинг 6.12. Алгоритм бинарного поиска def binary_search(lst, value): lo, hi = 0, len(lst)-1 while lo <= hi: mid = (lo + hi) // 2 if lst[mid] < value: lo = mid + 1 elif value < lst[mid]: hi = mid - 1 else: return mid return -1 l = [3, 6, 14, 16, 33, 55, 56, 89] x = 56 print(binary_search(l,x)) # 6 (индекс найденного элемента) Этот алгоритм получает в качестве аргумента список и значение для поис- ка, после чего последовательно делит пополам область поиска с помощью двух переменных lo и hi , задающих интервал элементов списка, в котором может находиться искомое значение: lo задает начальный индекс данного интервала, а hi — конечный. Мы проверяем, какой из вышеупомянутых случаев имеет место для срединного элемента, и подгоняем интервал поиска соответствующим образом, модифицируя значения lo и hi Рекурсивный алгоритм бинарного поиска 245 И хотя это вполне нормальная, удобочитаемая и эффективная реализация алгоритма бинарного поиска, она занимает отнюдь не одну строку! Код А теперь мы реализуем алгоритм бинарного поиска в одной строке кода (листинг 6.13)! Листинг 6.13. Однострочная реализация алгоритма бинарного поиска ## Данные l = [3, 6, 14, 16, 33, 55, 56, 89] x = 33 ## Однострочник bs = lambda l, x, lo, hi: -1 if lo>hi else \ (lo+hi)//2 if l[(lo+hi)//2] == x else \ bs(l, x, lo, (lo+hi)//2-1) if l[(lo+hi)//2] > x else \ bs(l, x, (lo+hi)//2+1, hi) ## Результат print(bs(l, x, 0, len(l)-1)) Угадайте, какие результаты вернет этот фрагмент кода! Принцип работы Благодаря тому, что бинарный поиск естественным образом подходит для реализации рекурсивного подхода, изучение данного однострочника укрепит ваше понимание этого важного понятия теории computer science. Отмечу, что я разбил данное однострочное решение на четыре строки ради удобства чтения, хотя, конечно, вы можете записать его в одной строке кода. В данном однострочнике используется рекурсивный способ реализации алгоритма бинарного поиска. Мы создаем новую функцию bs с помощью оператора lambda с четырьмя аргументами: l , x , lo и hi . Первые два аргумента l и x представляют собой переменные, содержащие отсортированный список и значение для поиска. Аргументы lo и hi задают минимальный и максимальный индекс текущего подсписка, в котором производится поиск значения x . На каж- дом уровне рекурсии код проверяет подсписок, заданный индексами lo и hi , все уменьшающийся по мере увеличения индекса lo и уменьшения индекса hi . После конечного количества шагов условие lo>hi становится |