🔀 Встроенная сортировка Python

В Python сортировка производится встроенной функцией sorted. Первым аргументом она принимает итерируемый объект. Это может быть список, кортеж, генератор, итератор и т.п. Возвращает отсортированный список.

>>> sorted([4, 2, 3, 1, 0])
[0, 1, 2, 3, 4]

>>> sorted((3, 1, 2))
[1, 2, 3]

>>> sorted(x * x for x in range(-5, 6))
[0, 1, 1, 4, 4, 9, 9, 16, 16, 25, 25]

Для словаря вернет сортированный список ключей:

>>> sorted({1: "abc", 3: "foo", -1: "baz"}) 
[-1, 1, 3] 

Если хотим значение, надо прямо это указать:

>>> sorted({1: "abc", 3: "foo", -1: "baz"}.values())
['abc', 'baz', 'foo']

Можно сортировать в обратном порядке:

>>> sorted([4, 2, 3, 1, 0], reverse=True)
[4, 3, 2, 1, 0]

Если сортируемые элементы – списки, словари или объекты, то воспользуемся параметром key. Мы передаем в key нечто вызываемое (имя функции, lambda и т.п), и при сортировки элементы сравниваются по результату вызова key на элементе. Результатом key должно быть число, строка или что-то другое сравнимое между собой.

📎 Пример. Сортировка списка строк по длине строки:

>>> sorted(["foo", "bazooka", "", "game"], key=len)
['', 'foo', 'game', 'bazooka']

📎 Пример. Сортировка списка кортежей по 0 или 1 элементу каждого.

>>> people = [("Bill", "Gates"), ("Tim", "Cook"), ("Donald", "Trump")]

>>> sorted(people, key=lambda t: t[0])
[('Bill', 'Gates'), ('Donald', 'Trump'), ('Tim', 'Cook')]

>>> sorted(people, key=lambda t: t[1])
[('Tim', 'Cook'), ('Bill', 'Gates'), ('Donald', 'Trump')]

Для этой же цели удобно использовать функцию operator.itemgetter:

>>> import operator
>>> sorted(people, key=operator.itemgetter(0))
[('Bill', 'Gates'), ('Donald', 'Trump'), ('Tim', 'Cook')]

Еще полезные функции из operator:
attrgetter(name) – для получение значения атрибута объекта с именем name
methodcaller(name[, args…]) – для получения результата вызова метода name у объекта. Опционально с аргументами args.

Вот пример использования этих функций:

import operator

class Item:
    def __init__(self, name, price, qty):
        self.name = name
        self.price = price
        self.qty = qty

    def total_cost(self):
        return self.price * self.qty

    def __repr__(self):
        return f'({self.name} ${self.price} x {self.qty} = ${self.total_cost()})'


items = [
    Item("iPhone", 999, 5),
    Item("iMac", 2999, 2),
    Item("iPad", 599, 11)
]

def print_items(title, item_list):
    print(title)
    print(*item_list, sep=', ', end='\n\n')


print_items('Original:', items)

items_by_price = sorted(items, key=operator.attrgetter('price'))
print_items('Sorted by price:', items_by_price)

items_by_total_cost = sorted(items, key=operator.methodcaller('total_cost'))
print_items('Sorted by total cost:', items_by_total_cost)

"""
Original:
(iPhone $999 x 5 = $4995), (iMac $2999 x 2 = $5998), (iPad $599 x 11 = $6589)
Sorted by price:
(iPad $599 x 11 = $6589), (iPhone $999 x 5 = $4995), (iMac $2999 x 2 = $5998)
Sorted by total cost:
(iPhone $999 x 5 = $4995), (iMac $2999 x 2 = $5998), (iPad $599 x 11 = $6589)
"""

Для списков (list) определен метод sort(), который модифицирует исходный список, выстраивая элемента по порядку.

>>> arr = [3, 4, 1, 2, 5, 6, 0]
>>> arr.sort()
>>> arr
[0, 1, 2, 3, 4, 5, 6]

Сортировка в Python – устойчива. Это значит, что порядок элементов с одинаковыми ключами будет сохранен в сортированной последовательности:

>>> names = ["John", "Tim", "Bill", "Max"]
>>> sorted(names, key=len)
['Tim', 'Max', 'John', 'Bill']

Tim и Max — оба длины 3, Tim был перед Max, так и осталось. John остался перед Bill. Зачем это нужно? Чтобы можно было сортировать сначала по одному признаку, потому по другому (если первый совпадает).

📎 Пример. Первичный признак – оценка ученика. Вторичный – имя. Внимание: сначала сортируем по вторичному, потому по первичному:

>>> students = [(3, "Xi"), (5, "Kate"), (5, "Max"), (3, "Fil"), (5, "Abby")]
>>> students_by_name = sorted(students, key=operator.itemgetter(1))
>>> sorted(students_by_name, key=operator.itemgetter(0))
[(3, 'Fil'), (3, 'Xi'), (5, 'Abby'), (5, 'Kate'), (5, 'Max')]

Внутри Python использует Timsort – гибридный алгоритм сортировки, сочетающий сортировку вставками и сортировку слиянием. Смысл в том, что в реальном мире часто встречаются частично отсортированные данные, на которых Timsort работает ощутимо быстрее прочих алгоритмов сортировки. Сложность по времени: O(n log n) в худшем случае и O(n) – в лучшем.

⚠️ CPython: не пытайтесь модифицировать сортируемый список во время сортировки. Эффект непредсказуем.

Специально для канала @pyway.

🎲 Великий random

Генераторы случайных чисел (аббр. ГСЧ или RNG) можно разделить на псевдослучайные генераторы (pseudo random number generator – PRNG) и настоящие генераторы (true random number generator – TRNG). Настоящие случайное число может быть получено, например, честным бросанием (без мухлежа) игрального кубика. Но, цифровая техника, в т.ч. и компьютер — вещь точная и детерминированная. И нет так очевидно, где нам там брать случайные числа. Да, бывают аппаратные ГСЧ, построенные на аналоговых шумах или квантовых эффектах, но они не всегда доступны простым пользователям. Однако математики разработали алгоритмы, по которым можно с помощью простых и точных операций (типа сложения и деления) получать «иллюзию» случайности.

Давайте для начала рассмотрим линейный конгруэнтный метод и попробуем сконструировать свой рандом. Все начинается с зерна (seed). x[0] = seed. Следующие случайное число будет равно x[i + 1] = (a * x[i] + b) mod c. Каждое из них будет в пределах [0..c). Вот реализация:

class MyRandom:
    def __init__(self, seed=42):
        self._state = seed

    def random(self):
        self._state = (5 * self._state + 9) % 17
        return self._state


r = MyRandom(42)
print([r.random() for _ in range(10)])
# [15, 16, 4, 12, 1, 14, 11, 13, 6, 5]

r2 = MyRandom(24)
print([r2.random() for _ in range(10)])
# [10, 8, 15, 16, 4, 12, 1, 14, 11, 13]

r3 = MyRandom(42)
print([r3.random() for _ in range(10)])
# [15, 16, 4, 12, 1, 14, 11, 13, 6, 5]

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

Но, если мы не хотим повторяемости, то можно инициализировать генератор какой-то меняющейся от запуска к запуску переменной (например, временем):

import time
r4 = MyRandom(int(time.time()))
print([r4.random() for _ in range(10)])
# [3, 7, 10, 8, 15, 16, 4, 12, 1, 14]

Для получение случайных величин в Python есть несколько способов. Мы рассмотрим следующие:

• Встроенный модуль random
• numpy.random из библиотеки NumPy
• Функцию os.urandom
• Встроенный модуль secrets
• Встроенный модуль uuid

Модуль random

Самый популярный вариант: модель встроенный random. Модуль random предоставляет набор функций для генерации псевдослучайных чисел. Реализована генерация на языке Си (исходник) по более хитрому алгоритму «вихрь Мерсенна», разработанному в 1997 году. Он дает более «качественные» псевдослучайные числа. Но они по-прежнему получается из начального зерна (seed) путем совершения математических операций. Зная seed и алгоритм можно воспроизвести последовательность случайных чисел; более того существуют алгоритмы позволяющие вычислить из последовательности чисел ее seed. Поэтому такие алгоритмы не пригодны для генерации конфиденциальных данных: паролей, и ключей доступа. Но он вполне сгодится для генерации случайностей в играх (не азартных) и прочих приложений, где не страшно, если кто-то сможет воспроизвести и продолжить последовательностей случайных чисел. Воспроизводимость случайностей поможет вам в задачах статистики, в симуляциях различных процессов.

Приступим:

>>> import random

random.seed(new_seed) – сброс ГСЧ с новым seed:

>>> random.seed(4242)
>>> random.random()
0.8624508153567833
>>> random.random()
0.41569372364698065

>>> random.seed(4242)
>>> random.random()
0.8624508153567833
>>> random.random()
0.41569372364698065

Когда мы второй раз задали тот же seed, ГСЧ выдает точно такие же случайные числа. Если мы не задаем seed, то ГСЧ будет скорее всего инициализирован системным временем, и значения будут отличаться от запуска к запуску.

random.randint(a, b) – случайное целое число от a до b (включительно):

>>> random.randint(5, 8)
5
>>> [random.randint(5, 8) for _ in range(10)]
[6, 8, 5, 8, 6, 6, 8, 5, 5, 6]

random.randrange(a, b, step) – случайное целое число от a до b (не включая b) с шагом step. Аргументы имеют такой же смысл, как у функции range. Если мы зададим только a, получим число в [0, a) с шагом 1; если задаем a и b, то в число будет в диапазоне [a, b):

>>> [random.randrange(10) for _ in range(5)]
[9, 3, 7, 0, 4]
>>> [random.randrange(10, 20) for _ in range(5)]
[15, 10, 15, 12, 18]
>>> [random.randrange(10, 20, 2) for _ in range(5)]
[14, 14, 18, 16, 16]

random.choice(seq) – выбирает из последовательности seq случайный элемент. Последовательность должна иметь длину (len). Например list, tuple, range – подойдут, а произвольные генераторы – нет.

>>> alist = [1, 2, 3, 4, 5, 6]
>>> random.choice(alist)
5
>>> random.choice(alist)
3
>>> random.choice(alist)
1

random.choices(population, weights=None, *, cum_weights=None, k=1) – позволяет выбрать k элементов из population. Выбранные элементы могут повторяться. Можно задать веса каждого элемента через weight, или кумулятивные веса через cum_weights. Веса определяют вероятность соответствующего элемента быть выбранным. Если мы не задали никакие веса, то любой элемент считается равновероятным. Кумулятивные веса – это значит, каждый следующий вес является суммой предыдущего и некоторой добавки, которая и есть вес соответствующего элемента. Пример: weights=[10, 5, 30, 5] эквивалентно cum_weights=[10, 15, 45, 50], причем последний вариант предпочтительнее, так как с кумулятивными весами функция работает быстрее.

>>> random.choices([1, 2, 3], k=10)
[1, 3, 1, 1, 2, 2, 1, 3, 3, 1]

📎 Пример. Выбор с весами (80% шанс получить 1, 15% для 2 и 5% для 3):

>>> random.choices([1, 2, 3], k=10, weights=[80, 15, 5])
[1, 1, 1, 1, 2, 1, 3, 1, 1, 1]

📎 Пример. Генерация случайной строки:

>>> import string
>>> ''.join(random.choices(string.ascii_letters, k=10))
'ncNAzTldvg'

random.shuffle(x) – перемешивает саму последовательность x, ничего не возвращает.

>>> x = [10, 20, 30, 40]
>>> random.shuffle(x)
>>> x
[10, 40, 20, 30]
>>> random.shuffle(x)
>>> x
[20, 30, 10, 40]

Если последовательность неизменяема (например, кортеж), то используйте random.sample(x, k=len(x)), которая вернет перемешанный список, не трогая исходную последовательность.

>>> random.sample(x, k=len(x))
[40, 30, 10, 20]

random.random() – случайное вещественное число от 0.0 до 1.0, не включая 1.0, т.е. в диапазоне [0, 1). Равновероятное распределение.

>>> random.random()
0.8505907349159074
>>> random.random()
0.49760476981102786

random.uniform(a, b) – случайное вещественное число на промежутке [a, b], равноверотяно.

>>> random.uniform(5, 7)
6.812839982463059
>>> random.uniform(5, 7)
6.564395491702289
>>> random.uniform(5, 7)
5.875898672403455

random.gauss(mu, sigma) и random.normalvariate(mu, sigma) нормальные распределения с медианой μ и с среднеквадратичным отклонением σ .

Нормальные распределения

random.triangular(low, high, mode) – треугольное разпределние от low до high с модой mode ∈ [low, high].

Треугольные распределения

random.betavariate(alpha, beta)бета-распределение.

Бета-распределения

random.expovariate(lambd)экспоненциальное распределение.

random.gammavariate(alpha, beta)гамма-распределение (не путать с гамма-функцией).

Гамма-распределения

random.lognormvariate(mu, sigma)логнормальное распределение. Если случайная величина имеет логнормальное распределение, то её логарифм имеет нормальное распределение.

Логнормальные распределения

random.vonmisesvariate(mu, kappa) – распределение вон Мизеса (также известное как круглое нормальное распределение или распределение Тихонова) является непрерывным распределением вероятности на круге.

Распределения вон Мизеса

random.paretovariate(alpha)распределение Парето.

Распределения Парето

random.weibullvariate(alpha, beta)распеделение Вейбулла.

Распределения Вейбулла

Внутри модуля random скрывается класс Random. Можно создавать экземпляры этого класса, которые не будут делить состояние с остальными функциями random. Этот класс содержит методы с аналогичными названиями, что и функции модуля:

>>> my_random = random.Random(42)
>>> my_random.normalvariate(1, 2.5)
1.6133158542696586
>>> my_random.random()
0.27502931836911926
>>> my_random.choice([1, 2, 3])
1

Класс Random пригодится вам, если нужна гарантированная воспроизводимость случайных чисел, ведь из этого ГСЧ только вы берете случайные числа, и никакая более часть программы не нарушит эту последовательность.

Класс random.SystemRandom() – альтернативные класс для случайных чисел, который берет случайные числа не из встроенного алгоритма, а из системного os.urandom, о котором будет рассказано в конце статьи.

Случайные числа в библиотеке NumPy

ГСЧ из NumPy пригодится на случай необходимости генерации случайных многомерных массивов.

numpy.random.seed(n) – задать seed для ГСЧ.

rand(d0, d1, …, dn) – многомерный массив случайных вещественных чисел в диапазоне [0, 1). Размерности указываются через запятую.

>>> import numpy as np
>>> np.random.rand(3, 2)
array([[0.10249247, 0.21503386],
       [0.40189789, 0.23972727],
       [0.28861301, 0.12995166]])

randn(d0, d1, …, dn) – тоже, что и rand, но случайные числа будут распределены нормально вокруг 0 со СКО = 1.

>>> np.random.randn(3, 2)
array([[ 1.13506644,  1.1115104 ],
       [-0.43613352, -0.03630799],
       [ 0.69787228,  1.24875159]])

randint(low[, high, size, dtype]) – случайные целые числа в диапазоне [low, high) в многомерном массиве размера size (целое число или кортеж размерностей).

>>> np.random.randint(10, 20, 5)
array([18, 18, 10, 19, 15])
>>> np.random.randint(10, 20, (3, 2))
array([[10, 13],
       [12, 14],
       [19, 14]])

random_integers(low[, high, size]) – случайные целые числа в диапазоне [low, high] в многомерном массиве размера size (целое число или кортеж размерностей).

>>> np.random.random_integers(10, 20, (3, 2))
array([[10, 20],
       [16, 14],
       [12, 18]])

randint никогда не возвращает верхнюю границу диапазона (high), random_integers – может вернуть и high.

random_sample([size]), random([size]), ranf([size]), sample([size]) – эти четыре функции называются по-разному, но делают одно и тоже. Возвращают многомерный массив случайных вещественных чисел в диапазоне [0, 1). Размерности указываются числом для 1D массива или кортежем для массива большего ранга.

>>> np.random.ranf(3)
array([0.60612404, 0.04881742, 0.17121467])
>>> np.random.sample(4)
array([0.71248954, 0.8613707 , 0.72469335, 0.62528553])
>>> np.random.random_sample((3, 4))
array([[0.39140157, 0.17538846, 0.55895275, 0.58363394],
       [0.52779193, 0.90067421, 0.63571978, 0.62386877],
       [0.52287003, 0.49077399, 0.57247767, 0.15221763]])

numpy.random.choice(a, size=None, replace=True, p=None) – случайно выбирает из 1D массива один и несколько элементов.

a – одномерный массив или число. Если вместо массива – число, то оно будет преобразовано в np.arange(a).

size – размерность возвращаемой величины. По умолчанию size=None, дает один единственный элемент, если size – целое число, то вернется 1D-массив, если size — кортеж, то вернется массив размерностей из этого кортежа.

replace – допускается ли повтор элементов, т.е. «возвращаем ли мы выбранный шар обратно в корзину». По умолчанию – да. Если мы запретим возврат, то мы не сможем извлечь больше элементов, чем есть в исходном массиве.

p – массив вероятностей для каждого элемента быть выбранным. Если не задано, распределение вероятностей равномерно.

📎 Пример. Допуская повторы:

>>> np.random.choice([1, 2, 3, 4], 3)
array([1, 3, 3])

📎 Пример. Не допуская повторы:

>>> np.random.choice([1, 2, 3, 4], 3, replace=False)
array([1, 3, 4])

📎 Пример. Задаем вероятности:

>>> np.random.choice([1, 2, 3, 4], 4, p=[0.1, 0.7, 0.0, 0.2])
array([2, 2, 1, 2])

📎 Пример. Выбор строк:

>>> np.random.choice(["foo", "bar", "dub"])
'dub'
>>> np.random.choice(["foo", "bar", "dub"], size=[2, 2])
array([['bar', 'bar'],
       ['bar', 'dub']], dtype='<U3')

bytes(length) – возвращает length случайных байт.

>>> np.random.bytes(10)
b'\x19~\xd0w\xc2\xb6\xe5M\xb1R'

shuffle(x) и permutation(x) – перемешивают последовательность x. shuffle модифицирует исходную последовательность, а permutation – возвращает новую перемешанную последовательность, не трогая исходную.

>>> x = np.arange(10)
>>> x
array([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])

>>> np.random.shuffle(x)
>>> x
array([8, 6, 0, 3, 1, 2, 4, 9, 7, 5])

>>> y = np.random.permutation(x)
>>> y
array([4, 8, 7, 5, 9, 3, 6, 0, 2, 1])

>>> x
array([8, 6, 0, 3, 1, 2, 4, 9, 7, 5])

Также в NumPy имеется еще более богатый выбор различных распределений случайных величин, чем у обычного random. Не будет подробно останавливаться на каждой функции, так как это уже больше статистика, чем программирование. Из названия функций легко понять, какое распределение они представляют. Главная особенность, что у каждый из этих функций есть аргумент size – кортеж размерностей возвращаемого многомерного массива или целое число, если нужен одномерный массив:

  • beta(a, b[, size])
  • binomial(n, p[, size])
  • chisquare(df[, size])
  • dirichlet(alpha[, size])
  • exponential([scale, size])
  • f(dfnum, dfden[, size])
  • gamma(shape[, scale, size])
  • geometric(p[, size])
  • gumbel([loc, scale, size])
  • hypergeometric(ngood, nbad, nsample[, size])
  • laplace([loc, scale, size])
  • logistic([loc, scale, size])
  • lognormal([mean, sigma, size])
  • logseries(p[, size])
  • multinomial(n, pvals[, size])
  • multivariate_normal(mean, cov[, size, …)
  • negative_binomial(n, p[, size])
  • noncentral_chisquare(df, nonc[, size])
  • noncentral_f(dfnum, dfden, nonc[, size])
  • normal([loc, scale, size])
  • pareto(a[, size])
  • poisson([lam, size])
  • power(a[, size])
  • rayleigh([scale, size])
  • standard_cauchy([size])
  • standard_exponential([size])
  • standard_gamma(shape[, size])
  • standard_normal([size])
  • standard_t(df[, size])
  • triangular(left, mode, right[, size])
  • uniform([low, high, size])
  • vonmises(mu, kappa[, size])
  • wald(mean, scale[, size])
  • weibull(a[, size])
  • zipf(a[, size])

📎 Пример. Генерация двух коррелирующих временных рядов из двумерного нормального распределения (multivariate_normal):

import numpy as np
import matplotlib.pyplot as plt


def corr2cov(p: np.ndarray, s: np.ndarray) -> np.ndarray:
    """Ковариационная матрица от корреляции и стандартных отклонений"""
    d = np.diag(s)
    return d @ p @ d


# Начало с корреляционной матрицы и стандартных отклонений
# 0.9 это корреляция между А и B, а корреляция
# самой переменной равна 1.0
corr = np.array([[1., 0.9],
                [0.9, 1.]])

stdev = np.array([3., 1.])
mean = np.array([5., -5.])
cov = corr2cov(corr, stdev)

# `size` это длина временных рядов для 2д данных
data = np.random.multivariate_normal(mean=mean, cov=cov, size=5000)

x, y = data.T

f, (ax1, ax2) = plt.subplots(1, 2)

ax1.plot(x, y, 'x')

ax2.plot(x[:100])
ax2.plot(y[:100])
plt.show()
Коррелирующие временные ряды

Криптографически безопасный ГСЧ

Криптографически безопасный ГСЧ (КБГСЧ) – по-прежнему псевдослучайный и детерминированный генератор, однако он использует широкий набор источников энтропии в системе. Энтропия – мера неопределенности, хаотичности системы. Случайности могут быть получены из

  • Различных системных идентификаторов
  • Времен возникновения разных системных событий в ядре и драйверах
  • Движения мыши, нажатия клавиш и т.п.
  • Аппаратный ГСЧ, например встроенный в процессоры Intel Ivy Bridge.

КБГСЧ в Python базируется на функции os.urandom(), которая в свою очередь использует:

  • Чтение из /dev/urandom на Unix-like системах.
  • CryptGenRandom() функцию на Windows.

Для os.urandom нет понятия seed. Последовательность случайных байт не должна быть воспроизводима. Аргумент функции – число случайных байт.

📎 Пример.

>>> import os
>>> x = os.urandom(10)

# объект типа bytes
>>> x  
b'\xf0\xba\xf8\x86\xb6\xc4Aa*\xe7'

# тоже самое как 16-ричная строка
>>> x.hex()  
'f0baf886b6c441612ae7'

# тоже самое как список чисел
>>> list(x)   
[240, 186, 248, 134, 182, 196, 65, 97, 42, 231]

В стандартной библиотеке Python несколько модулей используют функцию os.urandom:

  • random.SystemRandom() – все функции обычного Random, но источник случайностей – os.urandom
  • модуль secrets – удобства для генерации случайных токенов, ключей и т.п.
  • uuid – генерация токенов по стандарту UUID (Universally Unique IDentifier)

Модуль secrets

По сути – обертка над os.urandom.

  1. secrets.token_bytes – тоже самое, что и os.urandom (по умолчанию, если размер не указан дает 32 байта).
  2. secrets.token_hex – тоже самое, только возвращает 16-ричную строку.
  3. secrets.token_urlsafe – случайная строка, пригодная для URL адресов.
  4. secrets.choice – безопасная версия random.choice

📎 Пример. Укоротитель ссылок:

from secrets import token_urlsafe

DATABASE = {}


def shorten(url: str, nbytes: int = 5) -> str:
    token = token_urlsafe(nbytes=nbytes)
    if token in DATABASE:
        # если уже есть такая ссылка – генерируем еще одну рекурсивно
        return shorten(url, nbytes=nbytes)
    else:
        DATABASE[token] = url
        return 'https://bit.ly/' + token


print(shorten('https://google.com'))
print(shorten('https://yandex.ru'))

# https://bit.ly/vZ1VZug
# https://bit.ly/x966uWI

Ссылки в примеры получились длиннее (7 символов), чем мы просили (5 байт). Это объясняется тем, что внутри token_urlsafe использует кодировку base64, где каждый символ представляет 6 бит данных; чтобы закодировать 5 * 8 = 40 бит, понадобилось как минимум 7 6-битных символов (7 * 6 = 42 бита).

Модуль uuid

UUID (Universally Unique IDentifier) – универсальный уникальный идентификатор, уникальность которого «гарантирована» в пространстве и времени. Имеет длину 128 бит (16 байт). Наиболее интересен для нас вариант uuid4, так как он использует случайность из os.random.

>>> uuid.uuid4()
UUID('cd955a9e-445d-47de-95e2-3d8de8c61696')

>>> u = uuid.uuid4()
>>> u
UUID('7dfb1170-af20-4218-9b76-bc4d7ae6a309')

>>> u.hex
'7dfb1170af2042189b76bc4d7ae6a309'

>>> u.bytes
b'}\xfb\x11p\xaf B\x18\x9bv\xbcMz\xe6\xa3\t' 

>>> len(u.bytes)
16

Вероятность коллизии (вероятность получить два одинаковых uuid4) крайне мала. Если бы мы каждую секунду генерировали по одному миллиарду uuid, то через 100 лет едва ли обнаружился хоть один дубликат.

Производительность

Резонный вопрос: почему бы не использовать random.SystemRandom() (или os.urandom) везде, где можно?
Оказывается, есть существенное препятствие. Пул энтропии КБГСЧ ограничен. Если он исчерпан, то придется подождать, пока он заполнится вновь. Проведем небольшой бенчмарк на пропускную способность генераторов случайных чисел:

import random
import timeit

r_secure = random.SystemRandom()
r_common = random.Random()
n_bits = 1024


def prng():
    r_common.getrandbits(n_bits)


def csprng():
    r_secure.getrandbits(n_bits)


setup = 'import random; from __main__ import prng, csprng'

if __name__ == '__main__':
    number = 50000
    repeat = 10
    data_size_mb_bytes = number * repeat * n_bits / (8 * 1024**2)
    for f in ('prng()', 'csprng()'):
        best_time = min(timeit.repeat(f, setup=setup, number=number, repeat=repeat))
        speed = data_size_mb_bytes / best_time
        print('{:10s} {:0.2f} mb/sec random throughput.'.format(f, speed))

Результаты:

prng() 1794.74 mb/sec random throughput.
csprng() 94.13 mb/sec random throughput.

Почти в 20 раз обычный ГСЧ быстрее, чем КБГСЧ.

Вывод: нужна безопасность – обязательно используем secrets, random.SystemRandom, uuid.uuid4 или просто os.urandom, а если нужно много и быстро генерировать неконфиденциальные случайные данные – random и numpy.random.

Специально для канала @pyway.

​​🗓 Календарь

Когда под рукой нет календаря, но есть Python:

import calendar; calendar.TextCalendar().pryear(2019)

Или из командной строки:

python -c 'import calendar; calendar.TextCalendar().pryear(2019)'
Календарь

Хотите по-русски (если вдруг еще не)?

import locale
locale.setlocale(locale.LC_ALL, 'ru_RU')
import calendar 
calendar.TextCalendar().pryear(2019)

А еще можно узнать, високосный ли год:

>>> calendar.isleap(2019)
False
>>> calendar.isleap(2020)
True

Или какой сегодня день недели?

>>> calendar.day_name[calendar.weekday(2019, 2, 19)]
'вторник'

Больше функций календаря ищите в документации к модулю calendar.

Специально для канала @pyway.

👀 global и nonlocal

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

def foo():
    print('x is', x)

x = 5
foo()  # напечает x is 5

Однако если в функции есть присваиваниие x после использования переменной x, то возникнет ошибка:

def foo():
    print('x is', x)
    x = 10

x = 5
foo()  # UnboundLocalError: local variable 'x' referenced before assignment

Обатите внимание, что присваивание бывает в следующих ситуациях:

x = …
x += …, x -= … и т.п.
• for x in …:
• with … as x:

Чтобы избежать ошибки, мы должны явно указать перед использованием x, что она относится к глобальной области видимости:

def foo():
    global x  # <-- тут
    print('x is', x)
    x = 10
    print('x is now', x)

x = 5
foo()  # ошибок не будет

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

def make_inc():  # внешняя ф-ция
    total = 0     # счетчик
    def helper():  # внутр. ф-ция 
        total += 1  # тут присваивание переменной
        return total 
    return helper  

f = make_inc()

print(f())  # UnboundLocalError: local variable 'total' referenced before assignment

Тут нужно другое ключевое слово – nonlocal, которое укажет, что нужно искать переменную во внешней области видимости. Такой пример будет работать, как задумано:

def make_inc():
    total = 0
    def helper():
        nonlocal total  # <- тут
        total += 1
        return total
    return helper

f = make_inc()
print(f())

Почему мы редко видим global и nonlocal?
nonlocal – специфичная вещь, обычно вместо нее создают класс.
global потакает плохим практикам программирования. Менять глобальные переменные внутри функций – плохая практика.

📎 Пример.

def foo():
    global x
    print('x is', x)
    for x in range(2):
        ...
x = 5
foo()  # x is 5
foo()  # x is 1 (испортили из-за for)

Нет ошибок выполнения, но есть логическая ошибка! После первого вызова foo() мы испортили глобальную переменную x, она стала 1 (последним значением в цикле). Надо было просто называть переменные разными именами, и global не понадобится!

Специально для канала @pyway.

@ Оператор умножения матриц

А вы знали, что помимо обыденных операторов +, -, *, / и прочих, есть еще операторы @ и @=? Нет, это не про декораторы. Задуманы эти операторы были для умножения матриц и появились в версии Python 3.5. Однако встроенного типа «матрица» в Python нет, и ни один из встроенных типов эти операторы не реализует. Поэтому, быть может, о нем и не рассказывают на курсах.

Однако оператор @ рекомендуется для умножения матриц в библиотеке numpy:

>>> import numpy as np
>>> a = np.array( [ [1, 2], [-2, 3] ] )
>>> b = np.array( [ [3, 0], [1, -3] ] )
>>> a @ b
array([[ 5, -6],
       [-3, -9]])
>>> np.matmul(a, b)
array([[ 5, -6],
       [-3, -9]])

⚠️ Обратите внимание, что это именно np.matmul, а не np.dot!

Также вы можете написать реализацию операторов @ и @= для своих классов. Для этого вам понадобятся магические методы matmul__, __imatmul__, __rmatmul__ . Смотрите пример по ссылке.

Специально для канала @pyway.

🔐 Храним секреты правильно

Наверное, каждый когда-то писал в своем коде:

DB_HOST = 'localhost'
DB_USER = 'root'
DB_PASSWORD = 'l33thAxor666'

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

Для хранения секретов и паролей придет на помощь библиотека keyring.

В зависимости от ОС и среды она использует:
• macOS Keychain
• Freedesktop Secret Service
• KDE4 & KDE5 KWallet
• Windows Credential Locker
• и другие бэкенды…

Мы храним в скрипте или конфиге только название системы и логин (можете использовать произвольные):

>>> import keyring
>>> keyring.set_password("my_system", "my_username", "password")
>>> keyring.get_password("my_system", "my_username")
'password'

Другие пользователи системы не смогут прочитать эти данные. Но от вашего имени можно получить доступ к ним даже из терминала:

$ keyring set my_system my_username
Password for 'my_username' in 'my_system':
$ keyring get my_system my_username
qwerty

Считать пароль безопасно с клавиатуры можно с помощью модуля getpass (он строен в Python). Вводимые символы не будут видны на экране:

>>> import getpass
>>> password = getpass.getpass(prompt="Enter super password:")
Enter super password:
>>> password
'qwerty'

Специально для канала @pyway.

🔢 Приоритет операций

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

2 * 2 + 2 = 6

Рассмотрим таблицу приоритета операций в языке Python. Сверху таблицы самые приоритетные операции, снизу – операции с низким приоритетом.

ОперацияОписание
( )Скобки
**Экспонента (возведение в степень)
+x, -x, ~xУнарные плюс, минус и битовое отрицание
*, /, //, %Умножение, деления, взятие остатка
+, —Сложение и вычитание
<<, >>Битовые сдвиги
&Битовое И
^Битовое исключающее ИЛИ (XOR)
|Битовое ИЛИ
==, !=, >, >=, <, <=,
is, is not,
in, not in
Сравнение, проверка идентичности,
проверка вхождения
notЛогическое НЕ
andЛогическое И
orЛогическое ИЛИ

Как видно, скобки самые главные. Скобки решают все.

Если в одном выражении идут операторы одинакового приоритета, то вычисления выполняются слева направо.

Исключение составляет оператор **. Он право-ассоциативный. Т.е. в цепочке из двух ** сначала выполнится правый, а потом левый.

>>> 3 ** 4 ** 2
43046721
>>> 3 ** (4 ** 2)
43046721
>>> (3 ** 4) ** 2
6561

Обратите внимание на приоритеты not, and и or.

not a or b and c   ===   (not a) or (b and c)

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

В случае с операторами сравнения, помните про цепочки сравнений!

         x < y < z
это ни   (x < y) < z,
ни       x < (y < z),
а        x < y and y < z

Специально для канала @pyway.

⛓ Цепочки сравнений

Распространенная ситуация: проверка того, что переменная находится в заданных пределах. Можно было бы использовать логический оператор and:

if x >= 5 and x < 20:

Однако Python предоставляет нам синтаксическое удобство, которое выглядит более «математичным». Такая запись и короче, и понятнее:

if 5 <= x < 20:

В качестве операторов сравнения могут быть любые из списка в любых сочетаниях:

">", "<", "==", ">=", "<=", "!=", "is" ["not"], ["not"] "in"

Т.е. запись вида a < b > c вполне законна, хоть и трудна для понимания.

Формально, если мы имеем N операций OP1…OPN и N + 1 выражений (a, b … y, z), то запись вида:

a OP1 b OP2 c … y OPN z 

Это эквивалентно записи:

a OP1 b and b OP2 c and … and y OPN z

📎 Примеры:

x = 5
print(1 < x < 10)
print(x < 10 < x*10 < 100)
print(10 > x <= 9)
print(5 == x > 4)
a, b, c, d, e, f = 0, 5, 12, 0, 15, 15
print(a <= b < c > d is not e is f)

Специально для канала @pyway.

Итераторы и генераторы

В чем разница между итератором и генератором? Этот вопрос можно часто услышать на собеседованиях.

Итератор – более общая концепция, чем генератор.

Итератор – это интерфейс доступа к элементам коллекций и потоков данных. Он требует реализации единственного метода – «дай мне следующий элемент». Если вы пишите свой итератор на Python 3 вам нужно реализовать в классе метод __next__. Если элементы исчерпаны итератор возбудит исключение StopIteration.

📎 Пример. Итератор счетчик – выдает числа от low до high:

class Counter:
    def __init__(self, low, high):
        self.current = low
        self.high = high
    def __iter__(self):
        return self
    def __next__(self): 
        if self.current > self.high:
            raise StopIteration
        else:
            self.current += 1
            return self.current - 1

Генератор – это итератор

Генератор – это итератор, но не наоборот. Не любой итератор является генератором.

Есть два способа получить генератор:

📎 1. Генераторное выражение (что-то типа list comprehension, но возвращает генератор, а не список). Используются круглые скобки:

>>> g = (2 * i for i in range(5))
>>> type(g)
<class 'generator'>
>>> next(g)
0
>>> next(g)
2

📎 2. Генераторные функции. Это функции, где есть хотя бы одно выражение yield. Когда мы запускаем генератор, функция выполняет до первого выражения yield. То, что мы передали в yield будет возвращено наружу. Генератор при этом встанет «на паузу» до следующей итерации. При следующей итерации выполнение генератора продолжится до очередного yield.

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

Пример. Генератор чисел Фибоначчи (бесконечный):

def fib():
    a, b = 0, 1
    while 1:
        yield a
        a, b = b, a + b

>>> fib_g = fib()
>>> next(fib_g)
0
>>> next(fib_g)
1
>>> next(fib_g)
1
>>> next(fib_g)
2
>>> next(fib_g)
3
>>> next(fib_g)
5

Вызвав генераторную функцию fib() мы получили генератор. Затем мы итерируем этот генератор функцией next().

Передача данных в генератор

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

send() – отправить данные в генератор. Переданное значение вернется из той конструкции yield, на которой возникла последняя пауза генератора. При этом генератор будет прокручен на один шаг, как если бы мы вызвали next:

val = yield i  # генератор вернет i, но внутри получит val из аргумента метода send

Пример. Этот генератор просто выдает числа от 0 и далее, при этом печатает в поток вывода все, что мы ему отправляем.

def my_gen():
    i = 0
    while True:
        val = yield i
        print('Got inside generator:', val)
        i += 1

>>> g = my_gen()
>>> next(g)
0
>>> g.send("hello")
Got inside generator: hello
1
>>> g.send("world")
Got inside generator: world
2

Обратите внимание, что первый раз нельзя посылать в генератор данные, пока мы не прокрутили его до первого yield. Нужно либо взывать next(g) или g.send(None) – это одно и тоже.

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

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

>>> g = my_gen()   # my_gen из прошлого примера

>>> g.throw(TypeError, 'my error')
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 1, in my_gen
TypeError: my error

close() – закрыть генератор. Бросает внутри генератора особое исключение GeneratorExit. Это исключение, даже если оно не обработано, не распространится в код, вызвавший close(). Но, если мы поймали это исключение внутри генератора, то после закрытия генератора нельзя уже делать yield, рискуя получить RuntimeError. Остальные виды исключений будут распространяться из генератора в код, его вызывающий. Попытка итерировать закрытый итератор приведет к исключению StopIteration (закрытый генератор – пустой итератор).

>>> g = my_gen()
>>> next(g)
0
>>> next(g)
Got inside generator: None
1
>>> g.close()
>>> next(g)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
StopIteration

Бонус

Как взять из итератора (в том числе из генератора) N первых значений?

Можно, конечно, написать свою функцию. Но зачем, если она уже есть в стандартном модуле itertools. Этот модуль содержит множество вспомогательных функций для работы с итераторами. Нам понадобится itertools.islice. Первый аргумент – итератор (ну или генератор), остальные три – как в range.

>>> list(itertools.islice(fib(), 10))
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

>>> list(itertools.islice(fib(), 10, 20, 2))
[55, 144, 377, 987, 2584]

В первом примере мы передаем в функцию itertools.islice наш генератор чисел Фибоначчи и число чисел, которые надо вычислить (в нашем случае – 10).

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

Во втором примеры аргументов 4 штуки. В этом случае второй аргумент – начальный номер = 10, третий – конечный номер = 20 – (не включительно), и четвертый – шаг = 2. (Очень похоже на range, не так ли?)

Специально для канала @pyway.

Python: is

Новички часто путаются в конструкциях is и ==. Давайте разберемся, что к чему.

Сразу к сути: == (и его антагонист !=) применяются для проверки равенства (неравенства) значения двух объектов. Значение, это непосредственно то, что лежит в переменной. Значение числа 323235 – собственно число 323235. Тавтология. Но на примерах станет яснее.

Оператор is (и его антагонист is not) применяются проверки равенства (неравенства) ссылок на объект. Сразу отметим то, что на значение (допустим 323235) может быть копировано и храниться в разных местах (в разных объектах в памяти).

>>> x = 323235
>>> y = 323235
>>> x == y
True
>>> x is y
False

Видите, значение переменных равны по значению, но они ссылаются на разные объекты. Я не случайно взял большое число 323235. Дело в том, что в целях оптимизации интерпретатор Python при старте создает некоторые количество часто-используемых констант (от -5 до 256 включительно).

Следите внимательно за ловкостью рук:

>>> x = 256
>>> y = 256
>>> x is y
True
>>> x = 257
>>> y = 257
>>> x is y
False
>>> x = -5
>>> y = -5
>>> x is y
True
>>> x = -6
>>> y = -6
>>> x is y
False 

Поэтому новички часто совершают ошибку, считая, что писать == – это как-то не Python-way, а is – Python-way. Это ошибочное предположение может быть раскрыто не сразу.

Python старается кэшировать и переиспользовать строковые значения. Поэтому весьма вероятно, что переменные, содержащие одинаковые строки, будут содержать ссылки на одинаковые объекты. Но это не факт! Смотрите последний пример:

>>> x = "hello"
>>> y = "hello"
>>> x is y
True
>>> x = "hel" + "lo"
>>> y = "hello"
>>> x is y
True
>>> a = "hel"
>>> b = "lo"
>>> x = a + b
>>> y = "hello"
>>> x == y
True
>>> x is y
False

Мы составили строку из двух частей и она попала в другой объект. Python не догадался (и правильно) поискать ее в существующих строках.

Суть is (id)

В Python есть встроенная функция id. Она возвращает идентификатор объекта – некоторое число. Гарантируется, что оно будет различно для различных объектах в пределах одного интерпретатора. В реализации CPython – это просто адрес объекта в памяти интерпретатора.

Так вот:

a is b

Это тоже самое, что:

id(a) == id(b)

И все! Пример для проверки:

>>> x = 10.40
>>> y = 10.40
>>> x is y
False
>>> x == y
True

>>> id(x)
4453475504
>>> id(y)
4453475600
>>> id(x) == id(y)
False

>>> x = y
>>> x is y
True
>>> id(x)
4453475600
>>> id(y)
4453475600

Значения переменных равны, но их id – разные, и is выдает False. Как только мы к x привязали y, то ссылки стали совпадать.

Для чего можно применять is?

Если мы точно знаем уверены, что хотим проверять именно равенство ссылок на объекты (один ли это объект в памяти или разные).

Еще можно применять is для сравнения с None. None – это встроенная константа и двух None быть не может.

>>> x is None
False
>>> x = None
>>> x is None
True

Также для Ellipsis:

>>> ... is Ellipsis
True
>>> x = ...
>>> y = ...
>>> x is y
True

Я не рекомендую применять is для True и False.

Потому что короче писать if x:, чем if x is True:.

Можно применять is для сравнения типов с осторожностью (без учета наследования, т. е. проверка на точное совпадение типов):

>>> x = 10.5
>>> type(x) is float
True

С наследованием может быть конфуз:

>>> class Foo: ...
...
>>> class Bar(Foo): ...
...
>>> f = Foo()
>>> b = Bar()
>>> type(f) is Foo
True
>>> type(b) is Bar
True
>>> type(b) is Foo
False
>>> isinstance(b, Foo)
True

Не смотря на то, что Bar – наследник Foo, типы переменных foo и bar не совпадают. Если нам важно учесть наcледование, то пишите isinstance.

Нюанс: is not против is (not)

Важно знать, что is not – это один целый оператор, аналогичный id(x) != id(y). А в конструкции x is (not y) – у нас сначала будет логическое отрицание y, а потом просто оператор is.

Пример уловки:

>>> x = 10
>>> x is not None
True
>>> x is (not None)
False

Сравнение пользовательских классов

Далее речь пойдет об обычных == и !=. Можно определить магический метод __eq__, который обеспечит поведение при сравнении классов. Если он не реализован, то объекты будет сравниваться по ссылкам (как при is).

>>> class Baz: ...
...
>>> x = Baz()
>>> y = Baz()
>>> x == y
False
>>> x = y
>>> x == y
True

Если он реализован, то будет вызван метод __eq__ для левого операнда.

class Foo:
 def __init__(self, x):
  self.x = x
 def __eq__(self, other):
  print('Foo __eq__ {} and {}'.format(self, other))
  return self.x == other.x

>>> x = Foo(5)
>>> y = Foo(5)
>>> x == y
Foo __eq__ <__main__.Foo object at 0x109e9c048> and <__main__.Foo object at 0x109e8a5c0>
True

Метод __ne__ отвечает за реализацию !=. По умолчанию он вызывает not x.__eq__(y). Но рекомендуется реализовывать их оба вручную, чтобы поведение сравнения было согласовано и явно.

Вопрос к размышлению: что будет если мы сравним объекты разных классов, причем оба класса реализуют __eq__?

Что будет, если мы реализуем __ne__, но не реализуем __eq__?

А еще есть метод __cmp__. Это уже выходит за рамки статьи про is. Почитайте самостоятельно…

Специально для канала @pyway.