однострочники пайтон. Однострочники Python лаконичный и содержательный код by Кристи. Однострочники
 Скачать 4.44 Mb.
|
|
Рис. 6.3. Рекурсивное вычисление расстояния Левенштейна для слов 'cat' и 'chello' путем вычисления сначала меньших шагов задачи Чтобы рекурсивно вычислить расстояние Левенштейна для слов 'cat' и 'chel lo' , сначала мы решаем более простые задачи вычисления (рекур- сивно). 1. Вычисляем расстояние между суффиксами at и hello , поскольку если известно, как преобразовать at в hello , то можно легко преобразовать 224 Глава 6. Алгоритмы cat в chello , модифицируя сначала первый символ (или сохраняя его неизменным, если оба строковых значения начинаются с одного симво- ла). Если это расстояние равно 5, то можно сделать вывод, что расстоя- ние между cat и chello также не превышает 5, ведь можно получить одно из другого с помощью той же самой последовательности правок (оба слова начинаются с символа c , поэтому его редактировать не нужно). 2. Вычисляем расстояние между суффиксами at и chello . Если оно равно 6, то можно сделать вывод, что расстояние между cat и chello не превышает 6 + 1 = 7, поскольку можно просто убрать символ c в на- чале первого слова (одна дополнительная операция). А затем повторно использовать то же самое решение для получения chello из at 3. Вычисляем расстояние между cat и hello . Если оно равно 5, то мож- но сделать вывод, что расстояние между cat и chello не превышает 5 + 1 = 6, поскольку можно просто вставить символ c в начале второго слова (одна дополнительная операция). А поскольку это все возможные операции над первым символом (замена, удаление, вставка), то расстояние Левенштейна между cat и chello равно минимальному из трех случаев 1, 2 и 3. Теперь подробнее рассмотрим три случая в листинге 6.4. Во-первых, мы рекурсивно вычисляем расстояние редактирования между a[1:] и b[1:] . Если ведущие символы a[0] и b[0] различаются, то необ- ходимо исправить ситуацию, заменив a[0] на b[0] , так что мы увеличиваем расстояние редактирования на единицу. При совпадении ведущих символов решение более простой задачи ls(a[1:], b[1:]) совпадает с решением более сложной задачи ls(a, b) , как вы видели на рис. 6.3. Во-вторых, мы рекурсивно вычисляем расстояние между a[1:] и b . Допу- стим, нам известен результат вычисления (преобразования a[1:] в b ) — как теперь вычислить расстояние на один шаг дальше, от a до b ? Ответ: просто удалить первый символ a[0] из начала a , то есть произвести ровно на одну операцию больше. Благодаря этому мы свели более сложную задачу к более простой. В-третьих, мы рекурсивно вычисляем расстояние между a и b[1:] . До- пустим, нам известен результат вычисления (преобразования a в b[1:] ). Как теперь вычислить расстояние от a до b ? В данном случае мы просто проходим на шаг больше (от a до b[1:] до b ), вставляя символ b[0] в начале слова b[1:] , что увеличивает расстояние на единицу. Вычисление булеана с помощью функционального программирования 225 Наконец, мы просто берем минимальное расстояние редактирования из трех (замены первого символа, удаления первого символа и вставки перво- го символа). Данное однострочное решение опять демонстрирует важность навыков работы с рекурсией. Возможно, понимание рекурсии не дастся вам очень легко, но несомненно придет к вам по мере изучения множества задач на рекурсию, подобных этой. Вычисление булеана с помощью функционального программирования В этом разделе мы расскажем вам о важном математическом понятии бу- леана: множества всех подмножеств. Булеаны используются в статистике, теории множеств, функциональном программировании, теории вероятно- стей и алгоритмическом анализе. Общее описание Булеан (powerset) — это множество всех подмножеств заданного множе- ства s , включающее пустое множество {} , исходное множество s и все про- чие возможные подмножества исходного множества. Ниже даны несколько примеров. Пример 1: множество: s = {1} ; его булеан: P = {{},{1}} Пример 2: множество: s = {1, 2} ; его булеан: P = {{},{1},{2},{1,2}} Пример 3: множество: s = {1, 2, 3} ; его булеан: P = {{},{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}} 226 Глава 6. Алгоритмы Для вычисления булеана P n множества s, состоящего из n элементов, можно использовать булеан P n –1 подмножества s, состоящего из (n – 1) элемента. Пусть нам требуется вычислить булеан множества s = {1, 2, 3} 1. Зададим начальное значение булеана P 0 с нулем элементов как P 0 = {{}}. Другими словами, это булеан пустого множества. Он содержит только само пустое множество. 2. Для создания на основе булеана P n –1 множества, состоящего из (n – 1) элемента булеана P n , состоящего из n элементов, возьмем один (произвольный) элемент x из множества s и включим все полу- чающиеся подмножества в больший булеан P n с помощью следующей процедуры. 3. Проходим по всем множествам p в P n –1 и создаем новые подмноже- ства, состоящие из объединения x и p. В результате получаем новое временное множество множеств T. Например, если P 2 = {{}, {1}, {2}, {1,2}}, то мы создадим временное множество множеств T = {{3}, {1,3}, {2,3}, {1,2,3}} путем добавления элемента x ко всем множествам из P 2 4. Объединяем это новое множество множеств T с булеаном P n –1 и полу- чаем булеан P n . Например, булеан P 3 получается путем объединения временного множества T с булеаном P 2 следующим образом: P 3 = T ∪ P 2 5. Переходим на шаг 2 до тех пор, пока исходное множество s не окажется пустым. Ниже вас ждут более подробные пояснения этой стратегии. Функция reduce() Но сначала необходимо как следует разобраться с важной функцией Python, которую мы применим в нашем однострочнике: reduce() . Она встроена в Python 2, но создатели Python решили, что использовали ее настолько мало, что в Python 3 она включена не была, поэтому придется сначала им- портировать ее из библиотеки functools. Функция reduce() принимает три аргумента: reduce(функция, итериру- емый_объект, начальное_значение) . Аргумент функция определяет способ свертки двух значений x и y в одно (например, lambda x, y: x + y ). Таким об- разом можно в цикле свертывать два значения итерируемый_объект (второй аргумент) в одно до тех пор, пока в итерируемый_объект не останется только одно значение. Аргумент начальное_значение — необязательный, если его Вычисление булеана с помощью функционального программирования 227 не указать, Python будет использовать по умолчанию первое значение ите- рируемый_объект Например, при вызове reduce(lambda x, y: x + y, [0, 1, 2, 3]) производятся следующие вычисления: (((0 + 1)+ 2)+ 3) = 6 . Другими словами, сначала два значения x=0 и y=1 свертываются в их сумму x + y = 0 + 1 = 1 . Этот результат первого вызова лямбда-функции служит входными данными для второго ее вызова: x=1 и y=2 . В результате получается сумма x + y = 1 + 2 = 3 . На- конец, результат этого второго вызова лямбда-функции служит входными данными для третьего ее вызова: x=3 и y=3 . В результате получается сумма x + y = 3 + 3 = 6 В этом последнем примере, как вы могли заметить, значение x всегда было равно результату предыдущего вызова лямбда-функции. Аргумент x играет роль значения-накопителя, а аргумент y — обновляемого значения из итери- руемый_объект . Такое поведение нацелено на «свертку» в цикле всех значений из итерируемый_объект в одно значение. Необязательный третий аргумент задает начальное значение для x . Все это позволяет описать агрегатор для последовательностей, как показано ниже в листинге 6.5. Арифметические операции над списками Прежде чем заняться непосредственно однострочником, вам нужно понимать, как работают еще две операции над списками. Первая из них — оператор кон- катенации списков + , склеивающий два списка. Например, результат операции [1, 2] + [3, 4] — новый список [1, 2, 3, 4] . Вторая — оператор объединения | , производящий простую операцию объединения двух множеств. Например, результат выражения {1, 2} | {3, 4} — новое множество {1, 2, 3, 4} Код В листинге 6.5 приведено однострочное решение для вычисления булеана заданного множества s. Листинг 6.5. Однострочное решение для вычисления булеана заданного множества ## Зависимости from functools import reduce ## Данные s = {1, 2, 3} ## Однострочник 228 Глава 6. Алгоритмы ps = lambda s: reduce(lambda P, x: P + [subset | {x} for subset in P], s, [set()]) ## Результат print(ps(s)) Угадайте, что вернет этот фрагмент кода! Принцип работы Идея данного однострочника заключается в том, чтобы начать формиро- вание булеана с пустого множества и последовательно добавлять в него подмножества , пока их больше не останется. Изначально булеан содержит только пустое множество. На каждом шаге мы берем один элемент x из набора данных s и создаем новые подмноже- ства, получающиеся естественным образом путем добавления x в каждое из подмножеств булеана . Как вы уже видели чуть выше, размер булеана удваивается каждый раз, когда берется дополнительный элемент x из на- бора данных s . Таким образом можно наращивать булеан из n подмножеств по одному элементу набора данных за раз (но по n подмножеств за раз). Обратите внимание, что размер булеана растет экспоненциально: каждый новый элемент набора данных x приводит к удвоению размера булеана. Это неотъемлемое свойство булеанов: они стремительно заполняют любое хранилище — даже в случае относительно небольших наборов данных всего из нескольких десятков элементов. С помощью функции reduce() мы производим хранение текущего булеана в переменной P (изначально содержащей только пустое множество). С по- мощью спискового включения функция reduce() создает новые подмноже- ства — по одному для каждого существующего подмножества — и добавляет их в булеан P . В частности, она добавляет значение x из набора данных в каждое из подмножеств и тем самым удваивает размер булеана (который теперь содержит подмножества с элементом x набора данных и без него). Благодаря этому функция reduce() последовательно «сливает воедино» два элемента: булеан P и элемент x из набора данных. Поэтому результат нашего однострочника выглядит следующим образом: # Результат print(ps(s)) # [set(), {1}, {2}, {1, 2}, {3}, {1, 3}, {2, 3}, {1, 2, 3}] Реализация шифра Цезаря с помощью расширенного доступа по индексу 229 Данный однострочник наглядно демонстрирует важность понимания лямб- да-функций, списковых включений и операций над множествами. Реализация шифра Цезаря с помощью расширенного доступа по индексу и спискового включения В этом разделе мы расскажем вам о старинной методике шифрования — шифре Цезаря, — с помощью которого сам Гай Юлий Цезарь делал личные сообщения непонятными для врагов. К сожалению, шифр Цезаря слишком легко взламывается и никакой настоящей защиты не дает, но часто служит для развлечения и скрытия содержимого форумов (тех, которые можно найти в интернете, а не в Древнем Риме), которое необходимо защитить от глаз наивных пользователей. Общее описание В основе шифра Цезаря лежит идея сдвига шифруемых символов на фик- сированное количество позиций в алфавите. Далее мы рассмотрим один из частных случаев шифра Цезаря — алгоритм ROT13. ROT13 — простой алгоритм шифрования, используемый на многих форумах (например, Reddit) для защиты от спойлеров или скрытия смысла дискус- сии от новичков. Дешифровка алгоритма ROT13 проста — злоумышленник может взломать ваш код с помощью вероятностного анализа распределения букв в зашифрованном тексте, даже не зная, на сколько позиций сдвинуты символы. Никогда не следует использовать этот алгоритм для настоящего шифрования сообщений! Тем не менее существует немало приложений алгоритма ROT13: скрытие ответов на головоломки на интернет-форумах; скрытие возможных спойлеров на фильмы или книги; высмеивание других слабых алгоритмов шифрования: «56-битный алгоритм DES по крайней мере лучше, чем ROT13»; скрытие адресов электронной почты на сайтах от 99,999 % спам-ботов. Таким образом, ROT13 — скорее популярная дежурная шутка в интернет- культуре и образовательный инструмент, а не серьезный шифр. 230 Глава 6. Алгоритмы Этот алгоритм можно объяснить одной фразой: ROT13 = сдвиг шифруемой строки символов на 13 позиций (по модулю 26) в алфавите из 26 символов (рис. 6.4). Рис. 6.4. Таблица демонстрирует, как зашифровывается и расшифровывается каждый из символов алфавита при использовании алгоритма ROT13 Другими словами, каждый символ сдвигается на 13 позиций по алфавиту. При выходе за пределы последнего символа, z, происходит переход к перво- му символу алфавита, a. Код В листинге 6.6 мы создаем однострочник для шифрования строки s с по- мощью алгоритма ROT13! Листинг 6.6. Однострочное решение для шифрования строки с помощью алгоритма ROT13 ## Данные abc = "abcdefghijklmnopqrstuvwxyz" s = "xthexrussiansxarexcoming" ## Однострочник rt13 = lambda x: "".join([abc[(abc.find(c) + 13) % 26] for c in x]) ## Результат print(rt13(s)) print(rt13(rt13(s))) Воспользуйтесь рис. 6.4, чтобы взломать этот шифр: каковы результаты вы- полнения данного фрагмента кода? Реализация шифра Цезаря с помощью расширенного доступа по индексу 231 Принцип работы Наше однострочное решение шифрует каждую из букв по отдельности, сдви- гая ее на 13 позиций вправо по алфавиту, хранящемуся в переменной abc , после чего создает список этих зашифрованных букв и объединяет элементы этого списка в целую зашифрованную фразу x Рассмотрим подробнее способ шифрования каждой из букв. Для создания списка зашифрованных букв используется списковое включение (см. гла- ву 2), каждая буква c заменяется буквой, расположенной на 13 позиций даль- ше в алфавите. При этом важно предотвратить выход за пределы алфавита для букв, где индекс >= 13. Например, при сдвиге буквы z с индексом 25 на 13 позиций получается недопустимый для алфавита индекс 25 + 13 = 38. Для решения этой проблемы мы используем оператор сложения по модулю, чтобы даже при выходе за максимальный индекс 25 для буквы z шифрование продолжалось, если индекс = 0 (буква a ). И продолжаем сдвигать вправо на оставшиеся из 13 позиций, которые еще не были учтены до перехода в начало алфавита (рис. 6.5). Например, буква z сдвигается на 13 позиций до индекса 38 по модулю 26 (в виде кода Python: 38%26 ), то есть до индекса 12 (буквы m ). Рис. 6.5. Предотвращаем выход за пределы алфавита, начиная отсчет индекса заново с 0, в результате чего получается такая последовательность сдвига: 25 > 0 > 1 > … > 12 Вот главная часть кода, описывающая сдвиг каждого символа c на 13 по- зиций: abc[(abc.find(c) + 13) % 26] Во-первых, мы находим индекс символа c в алфавите abc . Во-вторых, сдви- гаем этот индекс, прибавляя целое число 13 к индексу символа c в алфавите abc , с учетом нашего приема с модулем 26 (как пояснялось в предыдущих абзацах). 232 Глава 6. Алгоритмы Результат выполнения кода однострочника выглядит следующим образом: ## Результат print(rt13(s)) # kgurkehffvnafknerkpbzvat print(rt13(rt13(s))) # xthexrussiansxarexcoming Резюмируя: вы изучили частный случай шифра Цезаря, алгоритм ROT13, при котором каждая буква в строке сдвигается на 13 позиций в алфавите. При повторном сдвиге еще на 13 позиций индекса (13+13=26) получается исходная буква, так что для шифрования и дешифрования применяется один алгоритм. Поиск простых чисел с помощью решета Эратосфена Поиск простых чисел играет важнейшую роль на практике, в частности в криптографии. Многие методы с открытым ключом безопасны (с точки зрения криптографии) лишь потому, что вычисление простых множителей больших чисел — трудоемкий и медленный процесс. Мы создадим одно- строчник, отыскивающий все простые числа в заданном диапазоне с помо- щью одного древнего алгоритма. Общее описание Простое число n — целое число, которое не делится без остатка ни на какое целое число, кроме самого себя и 1. Другими словами, для простого числа n не существует двух целых чисел a > 1 и b > 1, чье произведение равнялось бы ему: ab = n. Допустим, мы хотим проверить, является ли заданное число n простым. Начнем с «наивного» алгоритма поиска простых чисел (листинг 6.7). Листинг 6.7. « Наивная » реализация проверки заданного числа n на простоту def prime(n): for i in range(2,n): if n % i == 0: return False Поиск простых чисел с помощью решета Эратосфена 233 return True print(prime(10)) # False print(prime(11)) # True print(prime(7919)) # True Данный алгоритм проверяет, делится ли n на каждое из чисел от 2 до n–1 без остатка . Например, при проверке на простоту числа n = 10 алгоритм быстро обнаруживает, что выражение n % i == 0 равно True при i = 2 . Алгоритм нашел число i , являющееся делителем n , поэтому n не может быть простым числом. В данном случае алгоритм прерывает все дальнейшие вычисления и возвращает False Временная сложность проверки отдельного числа совпадает (точнее, линей- но зависит) с n : при наихудшем сценарии алгоритму понадобится n итераций цикла, чтобы проверить, простое ли n Пусть нам нужно вычислить все простые числа от 2 до определенного максимального числа m . Для этого можно просто повторить проверку из листинга 6.7 m–1 раз (листинг 6.8). Однако вычислительные затраты при этом колоссальны. |