Расширенный алгоритм Евклида.

1) Что такое расширенный алгоритм Евклида

Для двух целых чисел a и b и их НОД, то есть gcd(a, b), выполняется линейное уравнение с двумя переменными:

a·x + b·y = gcd(a, b) (1)

Расширенный алгоритм Евклида это способ найти одну пару целочисленных решений (x, y), которая удовлетворяет (1).

2) Алгоритм расширенного алгоритма Евклида

Перед тем как перейти к сути, вспомним обычный алгоритм Евклида.

Для двух целых a и b следующими шагами получаем:

gcd(a, b) = rₙ (2)

Сама цепочка делений с остатком:

a = b·q₀ + r₀
b = r₀·q₁ + r₁
r₀ = r₁·q₂ + r₂
...
rₙ₋₂ = rₙ₋₁·qₙ + rₙ
rₙ₋₁ = rₙ·qₙ₊₁

Теперь посмотрим на первую строку:

a = b·q₀ + r₀
r₀ = a − b·q₀

То есть r₀ можно выразить как линейную комбинацию a и b.

Подставим это во вторую строку:

b = r₀·q₁ + r₁
b = (a − b·q₀)·q₁ + r₁
b = a·q₁ − b·q₀·q₁ + r₁
r₁ = −a·q₁ + b·(q₀·q₁ + 1)

Получается, r₁ тоже выражается через a и b.

Если повторять эту операцию, то каждый rᵢ (0 ≤ i ≤ n) можно представить как сумму кратных a и b.
Значит, в конце:

rₙ = k·a + l·b

А из (2) получаем:

k·a + b·l = gcd(a, b) (3)

Это та же форма, что и (1). Сравнивая (1) и (3), получаем:

(x, y) = (k, l)

и эти k и l будут одной из пар целочисленных решений.

3) Реализация расширенного алгоритма Евклида

Опираясь на вышеописанное, реализуем расширенный алгоритм Евклида:

# extended_eucledean.py
def extended_eucledean(a, b):
  if b == 0:
    return (1, 0)
  else:
    xd, yd = extended_euclid(b, a % b)
    return (yd, xd - a // b * yd)

Очень просто, правда?

Ну всё. Пока. 🛌

👉 @PythonPortal

Теперь можно парсить почти любой документ одной моделью на 1.7B параметров.

Она называется dots-ocr. Одна система, которая умеет работать с текстом, таблицами, формулами, изображениями и PDF на 100+ языках.

Без отдельного OCR-пайплайна. Без моделей под конкретные задачи.

100% исходный код 👏

👉 @PythonPortal

Клонируй любой голос по 5-секундному аудиоклипу.

VoxCPM это open-source проект, который делает TTS принципиально иначе.

большинство TTS-систем сначала переводят речь в дискретные токены. это становится бутылочным горлышком и ограничивает, насколько “живым” может быть звук.

VoxCPM вообще пропускает токенизацию. он моделирует аудио в непрерывном пространстве через end-to-end diffusion autoregressive архитектуру.

в итоге получается речь, которая реально звучит по-человечески.

вот что в нем особенного:

> контекстно-зависимая генерация: читает текст и сам подбирает нужную просодию, эмоцию и темп. ручной тюнинг не нужен.

> zero-shot клонирование голоса: даешь короткий аудиоклип, и он ловит не только тембр, но и акцент, ритм и эмоциональный окрас.

модель обучали на 1.8 млн часов билингвальных данных (английский и китайский)

* поддерживает streaming synthesis
* работает и с full fine-tuning, и с LoRA
* простой Python API: pip install voxcpm

VoxCPM1.5 гоняет на 44.1kHz sampling rate и имеет 800M параметров. поэтому звук заметно более четкий и натуральный.

лицензия Apache-2.0

👉 @PythonPortal

Задеплой любую ML-модель как MCP-сервер.

LitServe: самый простой способ выкатывать агентов, RAG и вообще любые ML-модели. Теперь есть поддержка MCP.

Полностью open-source.

👉 @PythonPortal

Когда оперативка бесконечная

👉 @PythonPortal

Библиотека алгоритмов по робототехнике, которую должен знать каждый инженер📚

PythonRobotics это open-source коллекция Python-кода и учебник по алгоритмам робототехники, сделанные Atsushi Sakai.

На GitHub у проекта 27.2k звёзд и 7k форков, так что добавить в закладки вообще без вариантов

Там покрыто всё: от локализации (EKF, particle filters, histogram filters) до SLAM (FastSLAM, ICP matching), планирования пути (A*, RRT*, Dijkstra, D*, potential fields, state lattice), трекинга траектории (Stanley, LQR, MPC), навигации манипуляторов, воздушной навигации и даже планирования для двуногих роботов.

Что в нём особенного? Он сделан так, чтобы его было легко читать и понимать: минимум зависимостей и практичные, широко используемые алгоритмы.

Каждый алгоритм идёт с визуальными анимациями, математическими объяснениями и рабочим кодом.

Документация по сути это полноценный учебник по алгоритмам робототехники, бесплатно доступный онлайн.

Требования простые: Python 3.13+, NumPy, SciPy, Matplotlib и cvxpy.

И всё.

Это учебный ресурс с 2,201 коммитом, вкладом от 138 разработчиков и активной поддержкой. Одни только анимации (они лежат в отдельном репозитории) уже стоят того, чтобы их изучать.

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

Ссылка:

https://github.com/AtsushiSakai/PythonRobotics

P.S. Вот как выглядит хороший open-source: образовательный, практичный, отлично задокументированный и комьюнити-драйвовый. Добавь в закладки. 🔖

👉 @PythonPortal

Этот чувак буквально за 6 минут объясняет, как с нуля собрать алгоритмический хедж-фонд для трейдинга. Я видел, как команды годами до этого доходят.

Жесть 🙌

👉 @PythonPortal

инженеры смотрят, как все остальные вайб-кодят приложения

👉 @PythonPortal

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

На GitHub нашел FastScheduler, это опенсорсный легковесный таск-планировщик для Python. Поддерживает async, таймзоны, Cron-выражения и еще имеет визуальную панель.

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

Установка через pip в один шаг, а для персистентности доступны разные хранилища вроде SQLite и PostgreSQL. После рестарта сервиса состояние задач не теряется.

👉 @PythonPortal

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

👉 @PythonPortal

Топовый лайфхак с GitHub: добавь 0 к URL pull request, и ИИ поможет тебе ревьюнуть и понять изменения, которые хотят влить.

👉 @PythonPortal

Сравнение async и ThreadPoolExecutor в Python

Асинхронная обработка async

В async переключение выполнения на уровне CPU происходит в момент выполнения await.
Но чтобы можно было вызвать await, сам код должен поддерживать async.

Например, если вы хотите делать запись в PostgreSQL через async, то придется использовать asyncpg.
То есть для тех операций, которые поддерживают async, можно реализовать асинхронную обработку с помощью async.

Параллельная обработка ThredPoolExcutor

ThredPoolExcutor имеет смысл использовать в тех случаях, когда:

* код не поддерживает async
* или вы хотите распараллелить выполнение, минимально переписывая существующий код.

Тестовый код

Асинхронная обработка async:

import asyncio
import time

from icecream import ic


async def io_task(name):
    print(f"{name} start")
    await asyncio.sleep(3)  # ожидание неблокирующего I/O
    print(f"{name} end")


async def main():
    start = time.time()
    await asyncio.gather(io_task("A"), io_task("B"), io_task("C"))
    print(f"elapsed: {time.time() - start:.3f}")


ic()
asyncio.run(main())
ic()

# Результат выполнения
ic| main_async.py:19 in <module> at 22:06:11.408
A start
B start
C start
A end
B end
C end
elapsed: 3.001
ic| main_async.py:21 in <module> at 22:06:14.412

Параллельная обработка ThredPoolExcutor:

import time
from concurrent.futures import ThreadPoolExecutor

from icecream import ic


def io_task(name):
    print(f"{name} start")
    time.sleep(3)  # блокирующий I/O
    print(f"{name} end")


ic()
start = time.time()
with ThreadPoolExecutor(max_workers=3) as executor:
    executor.submit(io_task, "A")
    executor.submit(io_task, "B")
    executor.submit(io_task, "C")

print(f"elapsed: {time.time() - start:.3f}")

# Результат выполнения
ic| main_ThreadPoolExcutor.py:13 in <module> at 22:07:03.543
A start
B start
C start
C end
B end
A end
elapsed: 3.003

Вывод: В случаях, когда требуется блокирующая обработка вроде time.sleep[1], имеет смысл использовать ThredPoolExcutor.

Когда же нужна неблокирующая обработка, как в случае с asyncio.sleep, лучше использовать async.

👉 @PythonPortal