Сортировка вставками

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

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

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

Время сортировки вставками в среднем равно O(n²), где n — количество элементов списка.

Создаем бесконечный итератор

Функция cycle() из модуля itertools принимает на вход итерируемый объект и создает бесконечный итератор, циклически возвращающий элементы данного объекта.

Фишка в том, что когда элементы последовательности заканчиваются, итерация начинается вновь с первого элемента.

Но если вы проходитесь циклом по такому итератору, то важно предусмотреть выход из цикла, иначе он станет бесконечным (как у нас в первом случае на картинке).

Мы также можем воспользоваться islice(), который вернет итератор по подмножеству переданного объекта.

defaultdict

Класс defaultdict() модуля collections ни чем не отличается от обычного словаря за исключением того, что по умолчанию всегда вызывается функция, которая возвращает значение по умолчанию для новых значений. Другими словами Класс defaultdict() представляет собой словарь со значениями по умолчанию.

Подробнее с классом можно ознакомиться здесь.

Определяем язык текста

В данном посте покажем, как с помощью библиотеки langdetect определить язык текстового фрагмента. Для начала необходимо поставить библиотеку - pip install langdetect.

Заметим, что код импортирован на питон из гугловской библиотеки language-detection, поэтому качество распознавания языка находится на уровне.

По умолчанию поддерживается 55 языков.

Перевод текста с помощью Python

Перевод текстов с одного языка на другой становится все более распространенным явлением для различных веб-сайтов, поскольку они ориентированы на международную аудиторию. Пакет python, который помогает нам сделать это, называется translate.

Установка пакета - pip install translate.

В нашем примере мы переводим английскую фразу на испанский язык.

Работа с регистрами

Форматирование текста — это боль каждого data scientist’а. Слова и предложения в разных форматах создают много проблем при очистке данных. Однако и для этих задач в Python есть нужные функции.

Разбиение на фрагменты

Этот пример покажет, как разбить список на фрагменты и разделить его на меньшие части.

Рекурсия и Фибоначчи

Python, как и большинство других языков, даёт возможность вызова функции в теле самой этой функции. Такой принцип работы называется рекурсией.

В примере вы можете наблюдать функцию, которая использует рекурсию для вычисления чисел из ряда Фибоначчи — это ряд чисел, в котором первые два числа являются 0 и 1, а каждое последующее число — сумма двух предыдущих.

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

Хвостовая рекурсия

Это особый вид рекурсии, когда функция заканчивается вызовом самой себя без дополнительных операторов. Когда это условие выполняется, компилятор разворачивает рекурсию в цикл с одним стек-фреймом, просто меняя локальные переменные от итерации к итерации.

Так, классическое определение рекурсивного факториала return N * fact(N - 1) не поддерживает хвостовую рекурсию, потому что для каждого стек-фрейма придется хранить текущее значение N.

Чтобы сделать рекурсии хвостовой, добавляют параметры-аккумуляторы. Благодаря им функция знает о своем текущем состоянии. Пусть параметр acc по умолчанию равен 1. Тогда запись с хвостовой рекурсией будет выглядеть так(см картинку).