Деление с остатком преподнесло сюрприз

Деление с остатком – часто используемая операция в программировании. Начиная от классических заданий для начинающих на вычисление минут и секунд:

total_seconds = 119
seconds = total_seconds % 60
minutes = total_seconds // 60
print(f'{minutes}:{seconds}')  # 1:59

Заканчивая тем, что на остатках построена львиная доля криптографии. Нахождения остатка часто называют modulo (или коротко mod). 

При делении a на b неполное частное q и остаток r связаны формулой:

a = b · q + r, где b ≠ 0

В Python 3 частное и остаток вычисляются операторами:

q = a // b
r = a % b

Именно двойной слэш, одинарный слэш – деление без остатка (до конца). Иногда двойной слэш называют целочисленным делением, что не очень справедливо, потому что мы можем без проблем делить числа с запятой. Если оба числа целые (int), то частное будет тоже целым числом (int), иначе float. Посмотрите примеры:

10 / 3 == 3.3333333333333335
10 // 3 == 3
10.0 / 3.0 == 3.3333333333333335
10.0 // 3.0 == 3.0 
10.0 % 3.0 == 1.0
10 % 3 == 1

2.4 // 0.4 == 5.0
2.4 / 0.4 == 5.999999999999999
2.4 % 0.4 == 0.3999999999999998

Последние три примера немного обескураживают из-за особенностей вычислений с плавающей точкой на компьютере, но формула a = b · q + r всегда остается справедлива.

Поговорим об отрицательных числах. Математически остаток не должен быть меньше нуля и больше или равен модулю делителя b: 0 ≤ r < |b|. Однако, Intel в своих процессорах случайно либо намеренно ввела отрицательные остатки в реализации ассемблерных команд деления. Компиляторы языков C и С++, являясь платформо-зависимыми, обычно полагаются на процессорное поведение. Пример на С++. И вообще посмотрите на эту огромную таблицу, каждый язык программирования пляшет, как хочет. Не будем спорить, кто из них прав. Просто узнаем, как у нас в Python:

a, b = [10, -10], [3, -3]
for x in a:
  for y in b:
    print(f'{x} // {y} = {x // y}')
    print(f'{x} % {y} = {x % y}')
    print()

10 // 3 = 3
10 % 3 = 1

10 // -3 = -4
10 % -3 = -2

-10 // 3 = -4
-10 % 3 = 2

-10 // -3 = 3
-10 % -3 = -1

Формула выполняется всегда, но результаты отличаются для С++ и Python, где при делении на положительное число – остаток всегда положителен, а на отрицательное число – отрицателен. Если бы мы сами реализовали взятие остатка, то получилось бы так:

def mod_python(a, b):
  return int(a - math.floor(a / b) * b)

# на С++ работает так:
def mod_cpp(a, b):
  return int(a - math.trunc(a / b) * b)

Где floor – ближайшее целое число не превышающее аргумент: floor(-3.3) = -4, а trunc – функция отбрасывания целой части: trunc(-3.3) = -3. Разница проявляется между ними только для отрицательных чисел. Отсюда и разные остатки и частные – все зависит от того, с какой стороны числовой оси мы приближаемся к частному.

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

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

exit и компания

Выхода нет. Человек стучится в закрытую дверь, одиноко стоящую в поле (хотя может ее обойти).
>>> exit

У каждого, наверное, было: пишешь в интерпретаторе exit, а он:

>>> exit
Use exit() or Ctrl-D (i.e. EOF) to exit

Что же такое exit? Оказывается это такой класс, а текст — это всего лишь его repr:

>>> type(exit)
<class '_sitebuiltins.Quitter'>
>>> repr(exit)
'Use exit() or Ctrl-D (i.e. EOF) to exit'

А еще есть quit – он тоже из этой семьи:

>>> type(quit)
<class '_sitebuiltins.Quitter'>

Что же приходит при вывозе такого класса? Просто бросается исключение SystemExit, которое, между прочим, можно поймать. Попробуйте:

try:
    # выбери любое из:
    exit()
    quit()
except SystemExit:
    print('Невозможно покинуть Омск')

Есть еще sys.exit, который тоже бросает SystemExit, что может быть пойман.

🛑 Вывод: нельзя надеятся на exit() для гарантированного завершения программы, ведь ваш код может быть обернут в try / except Exception, который может подавить SystemExit. Как же быть? Есть способ – это os._exit, который завершит программу на системном уровне:

import os
try:
    os._exit(-1)
except SystemExit:
    print('Невозможно покинуть Омск')
finally:
    print('Я свободен!')

Ни первый, ни второй print не сработают!

✋ Надо упомянуть еще os.abort(), которая также немедленно завершает программу сигналом SIGABRT, что еще дополнительно приводит к созданию дампа памяти. Причем, не будет вызван даже обработчик сигнала, установленный через signal.signal(). Функция os.abort() подходит только для аварийного завершения приложения.

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

​​Сортировка пузырьком

Сегодня простая, но важная тема. Алгоритм сортировки пузырьком, его проходят на курсах, его часто спрашивают на собеседованиях. Сортировка — это процесс выстраивания массива или списка по возрастанию или убыванию. На примере чисел: [3, 1, 4, 2] → [1, 2, 3, 4].

Смысл пузырьковой сортировки заключается в следующем: мы начинаем с начала списка и сравниваем элементы попарно (нулевой и первый), если нулевой больше первого, то меняем их местами. Независимо от того, была ли замена или нет, мы шагаем вправо и сравниваем элементы вновь. Если на прошлом шаге была замена, то на этом шаге у нас окажется тот же элемент, и если он опять оказался больше, то «всплывет» снова вправо. Так за один проход наибольший элемент всплывет в самый-самый конец списка, подобно тому, как пузырек воздуха всплывает в бутылке воды. Когда все пузырьки всплывут – список будет отсортирован.

📎 Пример: a = [3, 1, 4, 2] – 4 элемента:

Первый проход:
  1. Сравним a[0] = 3 и a[1] = 1, 3 > 1. Меняем их местами. Теперь a = [1, 3, 4, 2].
  2. Сравним a[1] = 3 и a[2] = 4, 3 < 4. Менять не надо.
  3. Сравним a[2] = 4 и a[3] = 2, 4 > 2. Меняем. a = [1, 3, 2, 4].

Проход окончен. 4 «всплыла» в самый конец списка на свое место a[3]. Поэтому мы не трогаем больше конец списка, но список еще не отсортирован до конца, и следующий проход будет рассматривать только первые 3 элемента списка.

Второй проход:
  1. Сравним a[0] = 1 и a[1] = 3, 1 < 3. Менять не надо.
  2. Сравним a[1] = 3 и a[2] = 2, 3 > 2. Меняем их. a = [1, 2, 3, 4]. Проход окончен.
Третий проход:
  1. Сравним a[0] = 1 и a[1] = 3, 1 < 3. Менять не надо. Список отсортирован. Можно выходить.

👨‍💻 Переходим к реализации на Python:

def bubble_sort(a):
    n = len(a)
    
    # номер прохода i = 0..(n-2), т.е. (n-1 раз):
    for i in range(n - 1):
        # номер сравнения j = 0..(n - i - 2)
        for j in range(n - i - 1):
            # сравниваем только соседние элементы
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]

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

  • Начинаем всегда с начала (0-го элемента).
  • Число проходов меньше на 1, чем число элементов
  • С каждым проходом мы делаем все меньше и меньше сравнений, так как сортированный хвост списка растет на 1 после каждого прохода
  • Сравниваем только соседние элементы a[j] > a[j + 1], (а не i и j).
  • Если знак сравнения перевернуть, то сортировка будет по убыванию.

Временная сложность алгоритма квадратичная O(n^2) – имеются два вложенных цикла по элементам. Поэтому алгоритм медлителен для больших списков.  В реальной жизни чаще применяются другие алгоритмы сортировки, но пузырек до сих пор не забывают преподавать и спрашивать.

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

📕 Удаление ключа из словаря

Словарь (dict) – изменяемый тип в Python. Из словаря можно легко удалить ключ оператором del:

>>> d = {"foo":123, "bar":321}
>>> del d["foo"]
>>> d
{'bar': 321}

Что если ключа не окажется в словаре? Ответ: исключение – KeyError:

>>> del d['baz']
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
KeyError: 'baz'

Конечно, можно сделать так:

if 'baz' in d:
    del d['baz']

Или даже так:

try:
    del d['baz']
except KeyError:
    pass

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

d.pop('baz', None)

Обратите внимание, что второй аргумент None обязателен. Кроме того, метод pop вернет удаленный элемент, что может быть полезно в каких-то случаях.

🧙 Специально для канала @pyway. Подписывайтесь на мой канал в Телеграм @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.