Привет, Хаброжители! Краткость — сестра программиста. Эта книга научит вас читать и писать лаконичные и функциональные однострочники. Вы будете системно разбирать и понимать код на Python, а также писать выразительно и компактно, как настоящий эксперт.

Здесь вы найдете приемы и хитрости написания кода, регулярные выражения, примеры использования однострочников в различных сферах, а также полезные алгоритмы. Подробные пояснения касаются в том числе и важнейших понятий computer science, что поможет вашему росту в программировании и аналитике.

Вы узнаете о таких продвинутых возможностях Python, как списковые включения, срезы, лямбда функции, регулярные выражения, функции map и reduce, а также научитесь выполнять присваивание срезам.

Алгоритмы

Алгоритмы известны уже очень давно. Алгоритм — это просто набор инструкций наподобие кулинарного рецепта. Однако важность роли алгоритмов в обществе стремительно растет: алгоритмы и основанный на них процесс принятия решений проникают во все сферы по мере того, как компьютеры становятся все более важной частью нашей жизни.

В исследовании 2018 года подчеркивается, что «данные в виде наблюдений над нашим миром насквозь пропитывают современное общество… Эта информация может, в свою очередь, использоваться для принятия взвешенных — а в некоторых случаях даже полностью автоматизированных — решений… Вполне вероятно, что подобные алгоритмы в будущем будут активно участвовать в процессах принятия решений людьми, что необходимо для общественного признания, а значит, и широкомасштабного применения».

ПРИМЕЧАНИЕ
Больше информации об этом исследовании вы можете найти в статье The Growing Ubiquity of Algorithms in Society: Implications, Impacts, and Innovations авторов S. C. Olhede и P. J. Wolfe: royalsocietypublishing.org/doi/full/10.1098/rsta.2017.0364#d2696064e1.

По мере развития в обществе тенденций к автоматизации, искусственному интеллекту и повсеместному применению компьютеров социальная пропасть между теми, кто понимает алгоритмы, и теми, кто их не понимает, стремительно ширится. Например, в сфере логистики наблюдается масштабная тенденция к автоматизации, в том числе появляются беспилотные автомобили и грузовики, и профессиональные водители вынуждены принять тот факт, что алгоритмы постепенно отбирают у них работу.

Постоянная смена спектра востребованных навыков и специальностей в XXI столетии требует от молодежи понимания, умения настраивать и менять простые алгоритмы. И когда неизменно только изменение, основные идеи алгоритмов и теории алгоритмов формируют фундамент, на котором основываются многие грядущие изменения. Проще говоря, понимание алгоритмов гарантирует ваше процветание в ближайшие десятилетия.

Эта глава призвана расширить ваше понимание алгоритмов, делая упор скорее на интуитивном и всестороннем понимании основных идей и реализаций на практике, чем на теории. И хотя теория алгоритмов ничуть не менее важна, чем реализация их на практике и понимание на понятийном уровне, многие замечательные книги посвящены в основном теории. Прочитав данную главу, вы будете интуитивно понимать некоторые наиболее популярные в computer science алгоритмы и еще больше разовьете навыки практической реализации на языке Python. Это обеспечит вам надежный фундамент для будущих научно-технических прорывов.

ПРИМЕЧАНИЕ
Книга Томаса Кормена (Thomas Cormen) и др. Introduction to Algorithms (MIT Press, 2009)1 — замечательный источник дополнительной информации по теории алгоритмов.

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

Поиск анаграмм с помощью лямбда-функций и сортировки

Анаграммы — часто встречающийся при собеседованиях программистов вопрос на проверку кругозора в области компьютерных наук и умения разрабатывать собственные простые алгоритмы. В этом разделе мы расскажем о простом алгоритме для поиска анаграмм на языке Python.

Общее описание

Два слова являются анаграммами, если состоят из одинаковых символов и каждый символ первого из них встречается во втором ровно один раз. Ниже в списке и на рис. 6.1 даны несколько примеров:

• listen → silent;

• funeral → real fun;

• elvis → lives.

Займемся этой задачей и найдем лаконичное решение в стиле Python для определения того, являются ли два слова анаграммами. Что ж, приступим к написанию кода.

Код

Наша задача — написать функцию is_anagram(), которая принимает на входе два строковых значения x1 и x2 и возвращает True, если они — анаграммы! Прежде чем продолжить чтение, на минуту задумайтесь об этой задаче. Как бы вы стали решать ее на Python? Одно из возможных решений приведено в листинге 6.1.

Листинг 6.1. Однострочное решение для проверки того, являются ли два строковых значения анаграммами

## Однострочник
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 путем описания лямбда-функции (см. главу 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

В качестве небольшого примечания для опытных программистов скажем вот что: сложность сортировки последовательности 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.

• 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).

Результаты этого фрагмента кода выглядят следующим образом:

## Результат
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 %.


Вычислить количество перестановок заданного множества из n элементов можно с помощью функции факториала n!.. Из следующих нескольких абзацев вы узнаете почему. Определение факториала выглядит следующим образом:

Например:


Посмотрим, как работает эта функция. Пусть дано множество из 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!..

Рекурсивно функцию факториала можно определить следующим образом:

Граничные случаи рекурсии задаются вот так:

Интуитивно эти значения понятны, поскольку у множества из одного элемента существует только одна возможная перестановка, как и у множества из нуля элементов (существует только один способ распределения нуля элементов по нулю корзин).

Код

Однострочник из листинга 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 дает определение рекурсии как «методики программирования компьютеров, при котором функция вызывает саму себя один или несколько раз до тех пор, пока не выполнится определенное условие, причем остальные вызовы при каждом из этих повторов обрабатываются, начиная с последнего вызова и заканчивая первым». Краеугольный камень этого определения — рекурсивная функция, то есть просто функция, вызывающая сама себя. Но если функция вызывает сама себя, то ее выполнение никогда не закончится. Поэтому задается определенное граничное условие. По его достижении последний вызов функции завершается и возвращает результат в предпоследний вызов. Предпоследний вызов, в свою очередь, возвращает результат в предпредпоследний вызов. Возникает цепная реакция распространения результатов на верхние уровни рекурсии до тех пор, пока первый вызов не вернет вызывающей стороне окончательный результат. Возможно, эту идею непросто изложить в нескольких строках, но потерпите немного: мы обсудим ее далее на примере нашего однострочника.

В общем случае создание рекурсивной функции 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.

Данный алгоритм демонстрирует: если сначала тщательно обдумать задачу, то часто можно найти простой, лаконичный и эффективный способ ее решения. Выбор простейшего решения — один из важнейших элементов создания собственных алгоритмов. Начинающие часто замечают, что пишут громоздкий и переусложненный код.

В данном случае рекурсивное (однострочное) определение факториала короче итеративного (однострочного) определения без рекурсии. В качестве упражнения попробуйте переписать этот однострочник без рекурсии и без внешних библиотек — это отнюдь не тривиально и явно потребует намного более длинного кода!

Более подробно с книгой можно ознакомиться на сайте издательства
» Оглавление
» Отрывок

Для Хаброжителей скидка 25% по купону — Python