однострочники пайтон. Однострочники Python лаконичный и содержательный код by Кристи. Однострочники
 Скачать 4.44 Mb.
|
|
Рис. 6.1. Слово elvis — анаграмма слова lives Займемся этой задачей и найдем лаконичное решение в стиле Python для определения того, являются ли два слова анаграммами. Что ж, приступим к написанию кода. Поиск анаграмм с помощью лямбда-функций и сортировки 213 Код Наша задача — написать функцию is_anagram() , которая принимает на входе два строковых значения x1 и x2 и возвращает True , если они — анаграммы! Прежде чем продолжить чтение, на минуту задумайтесь об этой задаче. Как бы вы стали решать ее на Python? Одно из возможных решений приведено в листинге 6.1. Листинг 6.1. Однострочное решение для проверки того, являются ли два строковых значения анаграммами ## Однострочник is_anagram = lambda x1, x2: sorted(x1) == sorted(x2) ## Результат print(is_anagram("elvis", "lives")) print(is_anagram("elvise", "livees")) print(is_anagram("elvis", "dead")) Этот код выводит три строки. Какие? Принцип работы Два строковых значения — анаграммы, если у них совпадают отсортирован- ные последовательности символов, так что мы сортируем их и сравниваем поэлементно. Это несложно и не требует никаких внешних зависимостей. Просто создаем функцию is_anagram() путем описания лямбда-функции (см. главу 1) с двумя аргументами x1 и x2 , которая возвращает результат выражения sorted(x1) == sorted(x2) — True , если отсортированные после- довательности символов совпадают. Ниже представлен результат сортировки двух последовательностей символов: print(sorted("elvis")) # ['e', 'i', 'l', 's', 'v'] print(sorted("lives")) # ['e', 'i', 'l', 's', 'v'] Обе строки 'elvis' и 'lives' состоят из одних символов, так что их пред- ставления в виде отсортированного списка одинаковы. Результаты выше- приведенных трех операторов print : ## Результаты print(is_anagram("elvis", "lives")) # True print(is_anagram("elvise", "livees")) # True print(is_anagram("elvis", "dead")) # False 214 Глава 6. Алгоритмы В качестве небольшого примечания для опытных программистов скажем вот что: сложность сортировки последовательности n элементов на языке Python растет асимтотически, как функция от n log(n). Это означает, что наш однострочный алгоритм эффективнее «наивного» решения, состоящего в проверке наличия каждого символа в обоих строковых значениях и его удаления в этом случае. Сложность «наивного» алгоритма растет асимто- тически, как квадратичная функция n**2. Однако существует и другой эффективный способ решения этой задачи — создание гистограмм для обоих строковых значений на основе подсчета количества вхождений всех символов строки с последующим сравнением обеих гистограмм. Если размер алфавита не меняется, то сложность вычис- ления при таком подходе линейна и растет асимптотически как функция n. Оставляем реализацию этого алгоритма в качестве маленького упражнения для читателей! Поиск палиндромов с помощью лямбда- функций и негативных срезов В этом разделе вы познакомитесь еще с одним термином computer science, часто встречающимся в вопросах на собеседованиях: палиндромы. Мы про- верим с помощью однострочника, являются ли два слова палиндромами друг друга. Общее описание Для начала: что такое палиндром? Палиндром — это последовательность элементов (например, строка или список), которая читается одинаково от начала к концу и наоборот. Рассмотрим несколько забавных примеров па- линдромов (без учета пробелов). Mr Owl ate my metal worm. Was it a car or a cat I saw? Go hang a salami, I’m a lasagna hog. Rats live on no evil star. Hannah. Поиск палиндромов с помощью лямбда-функций и негативных срезов 215 Anna. Bob. Наше однострочное решение потребует некоторых знаний о срезах. Как вы знаете из главы 2, срезы в Python означают «вырезание» диапазона значений из различных типов последовательностей, например строк или списков. Для среза, начинающегося с индекса начало (включая его) и заканчивающего на индексе конец (исключая его), используется очень лаконичная нотация [начало:конец:шаг] . Третий параметр шаг позволяет задавать размер шага — количество элементов исходной последовательности, пропускаемых перед следующим элементом среза (например, шаг=2 означает, что срез будет включать только каждый второй элемент). При отрицательном размере шага последовательность обходится в обратном порядке. Вот и все, что нужно знать для создания простого и лаконичного одностроч- ного решения на Python. Код Наш код должен определять, совпадают ли символы заданной строки сим- волов в обратном порядке с исходной строкой, то есть определять, является ли эта строка палиндромом. Листинг 6.2. Однострочное решение, проверяющее, является ли строковое значение палиндромом ## Однострочник is_palindrome = lambda phrase: phrase == phrase[::-1] ## Результат print(is_palindrome("anna")) print(is_palindrome("kdljfasjf")) print(is_palindrome("rats live on no evil star")) Принцип работы Наше простое однострочное решение не требует для работы никаких внеш- них библиотек. Мы описываем лямбда-функцию, которая принимает один аргумент phrase — проверяемую строку символов — и возвращает булево значение, указывающее, остается ли последовательность символов такой же в обратном порядке. Для получения строки символов в обратном порядке мы используем срез (см. главу 2). 216 Глава 6. Алгоритмы Результаты этого фрагмента кода выглядят следующим образом: ## Результат print(is_palindrome("anna")) # True print(is_palindrome("kdljfasjf")) # False print(is_palindrome("rats live on no evil star")) # True Первая и третья строки символов — палиндромы, а вторая — нет. Далее мы займемся еще одним популярным в computer science понятием: пере- становками. Подсчет количества перестановок с помощью рекурсивных функций вычисления факториалов В этом разделе мы продемонстрируем простой и эффективный способ вы- числения факториала в одной строке кода для определения максимального количества возможных перестановок в наборе данных. Общее описание Рассмотрим следующую задачу: английская Премьер-лига состоит из 20 фут- больных команд, каждая из которых может занимать по итогам сезона одно из 20 мест в рейтинге. При фиксированном количестве в 20 команд можно вычислить, сколько существует возможных вариантов рейтинга. Обратите внимание, что вопрос не в том, сколько мест в рейтинге может занять одна команда (разумеется, ответ на этот вопрос — 20), а сколько вообще существу- ет рейтингов всех команд. На рис. 6.2 показаны всего лишь три возможных рейтинга. Говоря языком теории computer science, каждый конкретный рейтинг на- зывается перестановкой, то есть определенным порядком элементов множе- ства. Наша задача — найти количество возможных перестановок заданного множества. Количество перестановок играет важную роль в приложениях, связанных с игрой на тотализаторе, предсказанием результатов матчей и анализом игр. Например, если начальные вероятности каждого из 100 раз- личных рейтингов одинаковы, то вероятность каждого отдельного рейтинга равна 1/100 = 1 %. Это значение может использоваться в качестве базовой (априорной) вероятности для алгоритмов предсказания результатов игр. При таких допущениях вероятность выбранного случайным образом рейтинга оказаться правильным исходом в конце сезона равна 1 %. Подсчет количества перестановок с помощью рекурсивных функций 217 Рис. 6.2. Три возможных рейтинга футбольных команд английской Премьер-лиги Вычислить количество перестановок заданного множества из n элементов можно с помощью функции факториала n!. Из следующих нескольких аб- зацев вы узнаете почему. Определение факториала выглядит следующим образом: n! = n × (n – 1) × (n – 2) × . . . × 1. Например: 1! = 1 3! = 3 × 2 × 1 = 6 10! = 10 × 9 × 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1 = 3 628 800 20! = 20 × 19 × 18 × . . . × 3 × 2 × 1 = 2 432 902 008 176 640 000. 218 Глава 6. Алгоритмы Посмотрим, как работает эта функция. Пусть дано множество из 10 элемен- тов S = {s0, s1, s2, … , s9} и 10 корзин B = {b0, b1, b2, … , b9}. Мы хотим поместить в каждую корзину ровно один элемент из множества S. В нашем футболь- ном примере 20 команд играют роль элементов, а позиции рейтинга — роль корзин. Каждая конкретная перестановка множества S получается просто путем помещения всех элементов во все корзины. Количество различных способов распределения элементов по корзинам и будет общим количеством перестановок элементов множества S. Количество перестановок множества из десяти элементов (которые не- обходимо разместить по десяти корзинам) можно определить с помощью следующего алгоритма. 1. Берем первый элемент из множества S. Пустых корзин — десять, так что у нас десять вариантов того, куда поместить данный элемент. По- мещаем этот один элемент в какую-то корзину. 2. Одна корзина уже занята. Берем из множества S еще один элемент. Осталось девять пустых корзин, а значит, девять вариантов. 3. Наконец, берем из множества S десятый (последний) элемент. Девять корзин уже занято. Осталась только одна пустая корзина, а значит, только один вариант. В целом получаем 10 × 9 × 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1 = 10! вариантов. Каждое из потенциальных размещений элементов по корзинам соответствует одной перестановке элементов множества. Следовательно, количество перестано- вок элементов множества из n элементов равно n!. Рекурсивно функцию факториала можно определить следующим образом: n! = n × (n – 1)! Граничные случаи рекурсии задаются вот так: 1! = 0! = 1. Интуитивно эти значения понятны, поскольку у множества из одного эле- мента существует только одна возможная перестановка, как и у множества из нуля элементов (существует только один способ распределения нуля элементов по нулю корзин). Подсчет количества перестановок с помощью рекурсивных функций 219 Код Однострочник из листинга 6.3 вычисляет количество n! перестановок мно- жества из n элементов. Листинг 6.3. Однострочное решение для рекурсивного вычисления функции факториала ## Данные n = 5 ## Однострочник factorial = lambda n: n * factorial(n-1) if n > 1 else 1 ## Результат print(factorial(n)) Попробуйте догадаться, какой результат вернет этот код. Принцип работы В этом коде используется рекурсивное определение факториала. Вкратце формализуем наше интуитивное представление о рекурсии. Стивен Хокинг придумал лаконичный способ пояснить, что такое рекурсия: «Чтобы понять, что такое рекурсия, нужно сначала понять, что такое рекурсия». Словарь Merriam-Webster дает определение рекурсии как «методики про- граммирования компьютеров, при котором функция вызывает саму себя один или несколько раз до тех пор, пока не выполнится определенное усло- вие, причем остальные вызовы при каждом из этих повторов обрабатыва- ются, начиная с последнего вызова и заканчивая первым». Краеугольный камень этого определения — рекурсивная функция, то есть просто функция, вызывающая сама себя. Но если функция вызывает сама себя, то ее выпол- нение никогда не закончится. Поэтому задается определенное граничное условие. По его достижении последний вызов функции завершается и воз- вращает результат в предпоследний вызов. Предпоследний вызов, в свою очередь, возвращает результат в предпредпоследний вызов. Возникает цеп- ная реакция распространения результатов на верхние уровни рекурсии до тех пор, пока первый вызов не вернет вызывающей стороне окончательный результат. Возможно, эту идею непросто изложить в нескольких строках, но потерпите немного: мы обсудим ее далее на примере нашего однострочника. 220 Глава 6. Алгоритмы В общем случае создание рекурсивной функции f включает четыре этапа. 1. Разбиение исходной задачи на меньшие подзадачи. 2. Использование этих меньших подзадач в качестве входных данных для функции f (которая затем разобьет их на еще меньшие шаги и т. д.). 3. Описание граничного случая (base case) — минимального варианта входных данных, вычисление которого возможно без дальнейших вызовов функции f. 4. Указание способа объединения полученных меньших результатов в общий результат. Мы создали лямбда-функцию с одним аргументом n и присвоили ее перемен- ной factorial . Далее мы вызвали поименованную функцию factorial(n–1) для вычисления результата вызова функции factorial(n) . Значение n может представлять собой количество футбольных команд в премьер-лиге ( n=20 ) или любое другое значение, например, как в листинге 6.3 (см. выше). Попросту говоря, мы формируем более сложное решение задачи factorial(n) , умножая более простое решение factorial(n–1) на входной аргумент n По достижении граничного случая n <= 1 мы просто возвращаем «жестко зашитое» в код решение factorial(1) = factorial(0) = 1 Данный алгоритм демонстрирует: если сначала тщательно обдумать за- дачу, то часто можно найти простой, лаконичный и эффективный способ ее решения. Выбор простейшего решения — один из важнейших элементов создания собственных алгоритмов. Начинающие часто замечают, что пишут громоздкий и переусложненный код. В данном случае рекурсивное (однострочное) определение факториала ко- роче итеративного (однострочного) определения без рекурсии. В качестве упражнения попробуйте переписать этот однострочник без рекурсии и без внешних библиотек — это отнюдь не тривиально и явно потребует намного более длинного кода! Вычисление расстояния Левенштейна В этом разделе вы узнаете о важном алгоритме, используемом для вычис- ления расстояния Левенштейна. Разобраться в данном алгоритме сложнее, Вычисление расстояния Левенштейна 221 чем в предыдущих, так что заодно вы потренируете и свои навыки четкого анализа задачи. Общее описание Расстояние Левенштейна (Levenshtein distance) — метрика вычисления расстояния между двумя строками символов; другими словами, оно служит для количественной оценки подобия двух строк символов. Другое его на- звание, расстояние редактирования (edit distance), в точности описывает, что именно измеряется с его помощью: сколько правок символов (вставок, удалений и замен) необходимо для преобразования одной строки в другую. Чем меньше расстояние Левенштейна, тем более схожи строки. Расстояние Левенштейна нашло применение, в частности, в программе автоисправления в вашем смартфоне. Если вы введете в своем мессендже- ре Whatsapp helo, то смартфон обнаружит слово, не входящее в словарь, и выберет несколько наиболее вероятных слов для замены, после чего отсортирует их по расстоянию Левенштейна. Например, в данном случае слово с минимальным расстоянием Левенштейна, а значит максимальным подобием, — строка символов hello, так что телефон автоматически заменит helo на hello. Рассмотрим пример с двумя менее схожими строками 'cat' и 'chello' В табл. 6.1 приведена минимальная последовательность правок, необхо- димая для получения второй строки из первой, определяющая расстояние Левенштейна. Таблица 6.1. Минимальная последовательность правок для преобразования 'cat' в 'chello' Текущее слово Выполненная правка cat — cht Заменяем a на h che Заменяем t на e chel Вставляем l на позиции 3 chell Вставляем l на позиции 4 chello Вставляем o на позиции 5 222 Глава 6. Алгоритмы Таблица 6.1 демонстрирует преобразование строки символов 'cat' в 'chello' за пять шагов, так что расстояние Левенштейна равно 5. Код Теперь напишем однострочник Python для вычисления расстояния Левен- штейна между строками символов a и b , a и c , b и c (листинг 6.4). Листинг 6.4. Вычисление расстояния Левенштейна для двух строк символов в одной строке кода ## Данные a = "cat" b = "chello" c = "chess" ## Однострочник ls = lambda a, b: len(b) if not a else len(a) if not b else min( ls(a[1:], b[1:])+(a[0] != b[0]), ls(a[1:], b)+1, ls(a, b[1:])+1) ## Результат print(ls(a,b)) print(ls(a,c)) print(ls(b,c)) Попробуйте вычислить результаты работы этого фрагмента кода до запуска программы. Принцип работы Прежде чем углубляться в код, посмотрим на важный трюк Python, активно используемый в этом однострочнике. В Python у каждого объекта есть бу- лево значение, равное True или False . На самом деле большинство объектов равны True , и интуитивно понятно, что можно догадаться о том, что лишь немногие объекты равны False : числовое значение 0 равно False ; пустая строка '' равна False ; пустой список [] равен False ; пустое множество set[] равно False ; пустой ассоциативный массив {} равен False Вычисление расстояния Левенштейна 223 В качестве эмпирического правила: объекты Python считаются False , если они пусты или равны нулю. Вооружившись этой информацией, мы можем взгля- нуть на первую часть функции для вычисления расстояния Левенштейна: создадим лямбда-функцию, принимающую на входе два строковых значения a и b и возвращающую количество правок, необходимое для преобразования a в b . Существуют два тривиальных случая: если строковое значение a пусто, то минимальное расстояние редактирования равно len(b) , поскольку достаточно просто вставить все символы строкового значения b по одному. Аналогично, если пусто строковое значение b , то минимальное расстояние редактирования равно len(a) . Это значит, если одно из этих строковых зна- чений пусто, то можно сразу вернуть правильное расстояние редактирования. Пусть оба строковых значения не пусты. Мы можем упростить задачу, вы- числив расстояние Левенштейна меньших суффиксов исходных строковых значений a и b , как показано на рис. 6.3. |