Новости

Здесь вы найдете приемы и хитрости написания кода, регулярные выражения, примеры использования однострочников в различных сферах, а также полезные алгоритмы. Подробные пояснения касаются в том числе и важнейших понятий 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. Однострочное решение для проверки того, являются ли два строковых значения анаграммами

Этот код выводит три строки. Какие?

Принцип работы

Два строковых значения — анаграммы, если у них совпадают отсортированные последовательности символов, так что мы сортируем их и сравниваем поэлементно. Это несложно и не требует никаких внешних зависимостей. Просто создаем функцию is_anagram() 1 путем описания лямбда-функции (см. главу 1) с двумя аргументами x1 и x2, которая возвращает результат выражения sorted(x1) == sorted(x2) — True, если отсортированные последовательности символов совпадают. Ниже представлен результат сортировки двух последовательностей символов:

Обе строки 'elvis' и 'lives' состоят из одних символов, так что их представления в виде отсортированного списка одинаковы. Результаты вышеприведенных трех операторов print:

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

Принцип работы

Наше простое однострочное решение не требует для работы никаких внешних библиотек. Мы описываем лямбда-функцию, которая принимает один аргумент phrase — проверяемую строку символов — и возвращает булево значение, указывающее, остается ли последовательность символов такой же в обратном порядке. Для получения строки символов в обратном порядке мы используем срез (см. главу 2).

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

Первая и третья строки символов — палиндромы, а вторая — нет. Далее мы займемся еще одним популярным в computer science понятием: перестановками.

Приобрести книгу можно на сайте издательства:

https://www.piter.com/collection/new/product/odnostrochniki-python-lakonichnyy-i-soderzhatelnyy-kod