Метка: pyway

Пары из списка

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

a = [1, 2, 3, 4, 5, 6]

for x1, x2 in zip(a, a[1:]):
    print(x1, x2)

Вывод:

1 2
2 3
3 4
4 5
5 6

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

Генерируем Bitcoin-адрес на Python

Тема криптовалют снова начинает будоражить интернет. Супер, что вам не надо идти в отделение банка с паспортом и выстаивать очередь, чтобы открыть счет. Сгенерировать кошелек Bitcoin — дело нескольких строк кода на Python.

Нам понадобятся библиотеки base58 и ecdsa. base58 – это кодирование бинарных данных 58-ю печатными символами (цифрами и латинскими буквами, кроме 0, O, I, l, которые похожи друг на друга). ecdsa – библиотека криптографии на эллиптических кривых.

pip install base58 ecdsa

Импортируем то, что нужно:

import hashlib
import ecdsa
from binascii import hexlify
from base58 import b58encode

Нам нужен приватный ключ, из него мы вычислим публичный ключ, а из него – адрес кошелька Bitcoin. (Обратная процедура не возможна без полного перебора до конца времен). Приватный ключ – это 32 байта данных, которые мы получим из криптографически-надежного источника случайных чисел. Вообще можно придумать свой приватный ключ самостоятельно, если так хочется. Для генерации случайного приватного ключа мы воспользуемся библиотекой ecdsa:

private_key = ecdsa.SigningKey.generate(curve=ecdsa.SECP256k1)

Вычислим этой же библиотекой публичный ключ и добавим спереди байт 0x4 (это признак «несжатого» публичного ключа; есть и другие форматы).

public_key = b'\04' + private_key.get_verifying_key().to_string()

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

Схема генерации адреса BTC из публичного ключа.

Для получения адреса из публичного ключа вычисляем сначала RIPEMD160(SHA256(public-key)):

ripemd160 = hashlib.new('ripemd160')
ripemd160.update(hashlib.sha256(public_key).digest())

Дополняем его префиксом 0x0 (главная сеть Bitcoin):

r = b'\0' + ripemd160.digest()

Вычисляем контрольную сумму (нужна, чтобы наши денюжки не пропадали, если мы ошибемся в каком-то символе адреса). Контрольная сумма это первые 4 байта от SHA256(SHA256(r)):

checksum = hashlib.sha256(hashlib.sha256(r).digest()).digest()[0:4]

Получаем адрес кошелька, закодировав в base58 сложенные r и checksum:

address = b58encode(r + checksum)

Выведем результат:

print(f'private key: {hexlify(private_key.to_string())}')
print(f'public key uncompressed: {hexlify(public_key)}')
print(f'btc address: {address}')

Генерация приватного ключа из своего источника случайностей, например, os.urandom:

def random_secret_exponent(curve_order):
    while True:
        bytes = os.urandom(32)
        random_hex = hexlify(bytes)
        random_int = int(random_hex, 16)
        if random_int >= 1 and random_int < curve_order:
            return random_int


def generate_private_key():
    curve = ecdsa.curves.SECP256k1
    se = random_secret_exponent(curve.order)
    from_secret_exponent = ecdsa.keys.SigningKey.from_secret_exponent
    return from_secret_exponent(se, curve, hashlib.sha256).to_string()

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

Полный пример кода генерации кошельков.

Проверить ключи и адрес можно здесь. (Нажимаем Skip, дальше Enter my own…)

Подробнее по теме можно почитать здесь.

Специально для канала @pyway. Подписывайтесь на мой канал в Телеграм @pyway 👈 

Доступ к атрибутам

Скрин из Готики 1: страж не пускает в замок героя

Атрибуты объекта в Python – это именованные поля (данные, функции), присущие данному объекту (экземпляру, классу). Самый простой доступ к атрибутам – через точку:

class Foo:
     def init(self):
         self.x = 88  # установка значения атрибута      
 f = Foo()
 print(f.x)  # доступ к атрибуту через точку

Если мы обратимся к атрибуту, которого нет, то получим ошибку AttributeError. Мы можем переопределить это поведение путем реализации магических методов __getattr__ или __getattribute__.

__getattr__ вызывается, если атрибут не найден обычным способом (не был задан ранее через точку, функцию setattr, или через __dict__). Если атрибут найден, то __getattr__ НЕ вызывается.

📎 Пример. Возвращаем -1 для любого несуществующего атрибута.

class Test:
    def __getattr__(self, item):
        print(f'__getattr__({item})')
        return -1  

t = Test()
# зададим x и y
t.x = 10
setattr(t, 'y', 33)

print(t.x)  # 10
print(t.y)  # 33  
print(t.z)  # __getattr__(z) -1

Метод __getattribute__ вызывается, когда мы пытаемся получить любой атрибут, не зависимо от того, есть он или нет. Этот метод, вызывается прежде __getattr__. Он немного хитрее. Если __getattribute__ кидает AttributeError, то будет вызвана __getattr__.

📎 Пример. Мы можем запретить чтение каких-то атрибутов:

class Test:
    def __getattr__(self, item):
        print(f'__getattr__({item})')
        return -1

    def __getattribute__(self, item):
        print(f'__getattribute__({item})')
        if item == 'y':  # запретим получать y
            raise AttributeError
        return super().__getattribute__(item)


# зададим x и y
t = Test()
t.x = 10
t.y = 20

print(t.x)  # __getattribute__(x) 10
print(t.y)  # __getattribute__(y) __getattr__(y) -1
print(t.z)  # __getattribute__(z) __getattr__(z) -1

⚠️ Внимание! В __getattribute__ мы можем вызвать super().__getattribute__(item) или object.__getattribute__(self, item), что посути тоже самое, но не следует делать return self.__dict__[item] или return self.__getattribute__(item) или return getattr(self, item), так как это приведет к бесконечной рекурсии.

💡 Также есть магический метод __setattr__(self, key, value), вызываемый при obj.key = value или setattr(obj, 'key', value). У него нет более длинно-названного брата-близнеца.

Для полноты картины еще есть встроенная функция getattr(object, name[, default]). Вызов getattr(x, 'y') аналогичен обращению через точку: x.y В первом случае ‘y’ – это строка, что позволяет нам динамически получать атрибуты объектов, в отличие от точки, которая требует фиксированного имени на этапе написания кода. В случае, если атрибут недоступен мы получим AttributeError при незаданном default или получим default (без возникновения ошибки), если default был задан третьим аргументом.

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

Встроенная сортировка 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.