Raspberry PI 3 как Wi-Fi роутер

В сети очень много статей как сделать из Raspberry Pi (RPI) Wi-Fi роутер, в этой заметке я кратко опишу свой способ создания Wi-Fi роутера с sing-box на борту. Описанный метод работает на текущий момент времени, и многое может измениться в будущем. Поэтому используйте эту заметку для примерного обзорного понимания того с чем предстоит столкнуться.

SSH

Для тех кто не умеет работать с OpenWrt, я рекомендую установить dietPI.
Подключите RPI к вашему текущему роутеру по eth0, далее подключитесь туда по SSH. Узнать ip адрес RPI можно в dhcp панели роутера. Подключайтесь сразу к root, например так:

ssh root@[IP_ADDRESS]

Wi-Fi адаптер

Встроенный в RPI3 оказался откровенно слабым и не поддерживающим 5GHz. Поэтому я подключил адаптер RITMIX RWA-150 на чипсете Realtek RTL8811CU через USB 2. Драйвера добавлены в ядро Linux которое было в моей версии dietPi. Далее с помощью dietpi-config отключил встроенный Wi-Fi полностью. В результате этого остался один wlan0 адаптер по USB.

Точка доступа

По умолчанию dietPI для root ставит пароль dietpi. После подключения вас встретит установщик/конфигуратор dietPI. По окончанию нужно будет подключиться снова из-за перезагрузки устройства.

Для начала вам нужно настроить hostapd для того чтобы устройства видели вашу точку доступа. Если hostapd не установлен, то установите его через apk.

Далее нужно будет написать конфиг для hostapd. Пример моего конфига:

interface=wlan0
driver=nl80211
ssid=MyPiAP
hw_mode=a
channel=157
wmm_enabled=1

auth_algs=1
wpa=2
wpa_passphrase=your_password
wpa_key_mgmt=WPA-PSK
rsn_pairwise=CCMP
ieee80211n=1
ieee80211ac=0
ieee80211ax=0
country_code=RU

Смысл конфига hostapd можно посмотреть в мануале. Однако из того что важно стоит настроить под себя – канал (2.4GHz или 5GHz), код страны, иначе без этого ваши локализованные устройства могут работать с точкой доступа корректно, это я уже проходил и знаю, поэтому установите свою страну обзятально.

DHCP

Далее установите и настройте dnsmasq для реализации DHCP. Это нужно для того чтобы подключенные компьютеры определяли ip адрес и dns сервера.
Пример моего конфига:

interface=wlan0
dhcp-range=172.19.0.10,172.19.0.200,255.255.255.0,12h

dhcp-option=3,172.19.0.1

dhcp-option=6,1.1.1.1,8.8.8.8

no-resolv

server=1.1.1.1
server=8.8.8.8

Это минимальный конфиг, который позволит подключиться к точке доступа и получить ip адрес. Далее вам нужно будет настроить маршрутизацию и NAT. Это нужно для того чтобы подключенные компьютеры могли выходить в интернет.

Здесь уже заметка переходит в разряд типичной настройки маршрутизации на обычной debian совместимой системе, о чем есть очень много статей в сети. Далее все зависит от того какие цели вы преследуете, например подключение к внешнему серверу как новому интерфейсу в системе, или просто делаете wlan0 <-> eth0, на этом специфика по RPI заканчивается, дальше настраивайте на свой вкус.

Хочется упомянуть также необходимость настройки кастомных системных сервисов через systemctl, возможно появится потребность в подключении сервисов по цепочке, все это есть в мануалах по systemctl в сети. Если возникли проблемы на уровне сервисов, то ознакомьтесь с логами в journalctl.

Заключение

Из замеров скорости удалость выжать из RPI3 около 50Мбит/с по Wi-Fi (после подключения 5GHz адаптера) что означает потерю половины скорости по сравнению с подключением напрямую к роутеру. Допускаю что более производительные модели RPI позволят добиться лучших результатов, также специализированные устройства на OpenWrt и готовые решения могут оказаться лучше для ваших потребностей.

Источники

https://forums.raspberrypi.com/viewtopic.php?t=394710
https://superuser.com/questions/1408586/raspberry-pi-wifi-hotspot-slow-internet-speed
https://www.youtube.com/watch?v=jlHWnKVpygw

Локальная генерация изображений: ComfyUI и модель FLUX

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

ComfyUI использует узловую (node-based) архитектуру. Это позволяет:
– Тотально контролировать каждый этап генерации.
– Легко обмениваться готовыми “рабочими процессами” (workflows)

FLUX — модель крупная, поэтому требования к железу выше, чем у SD 1.5 или SDXL:
Видеокарта (GPU): Nvidia RTX с 12 ГБ VRAM и выше (для комфортной работы). Если у вас 8 ГБ или меньше, придется использовать квантованные версии (GGUF или NF4).
Оперативная память (RAM): минимум 16 ГБ (лучше 32 ГБ и выше).
Место на диске: около 20–50 ГБ для моделей и компонентов.

Самый простой способ запустить FLUX — использовать готовый шаблон. Просто найдите flux text to image в окне workflows и установите.

Напишите промпт на английском языке в узле `Text to Image (Flux.1 Dev)`, выберите разрешение (FLUX отлично справляется с 1024×1024 и даже выше) и нажмите RUN.

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

https://github.com/comfyanonymous/ComfyUI

Запуск macOS в Docker

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

Одними из классических способов запуска macOS на PC машинах исторически были:
* Hackintosh
* Виртуализация, например с помощью VMWare

Hackintosh предполагает наличие аналогичного или очень близкого к оригинальному маку железа. Виртуализация же предъявляет определенные требования к оборудованию, но в основном не такие строгие как в случае с Hackintosh. При этом в случае с виртуализацией есть проблемы с производительностью, так как macOS не оптимизирована для работы в виртуальной среде.

С недавних пор появилась возможность запускать macOS в Docker. Это стало возможным благодаря проекту Docker-OSX, который предоставляет готовые образы macOS для запуска в Docker. При этом стоит отметить, что Docker-OSX не является официальным проектом Apple и не поддерживается ею. Тем не менее, он позволяет запускать macOS в Docker и использовать ее для разработки и тестирования приложений.

Один из первых проектов по запуску macOS в Docker:
https://github.com/sickcodes/Docker-OSX

Однако запустить полноценно мне так и не удалось, после загрузки в мено Recovery OS, у меня просто отваливалась клавиатура и мышь, и я не мог продолжить установку. При этом в первом boot меню, клавиатура работает. Возможно дело в том что этот проект уже не так активно поддерживается, и есть некие специфические проблемы при запуске на Windows 11 + WSL2 + Ubuntu.

Один из самых активных проектов на данный момент:
https://github.com/dockur/macos

Позволяет запускать macOS в Docker, интерфейс работает через браузер путем проброса VNC(?). После запуска macOS доступна по адресу http://localhost:5900

Данный проект мне удалось запустить и установить macOS Big Sur (минуточку 2020 года) на Windows 11 + WSL2 + Ubuntu, но только изменив compose файл, а именно:

environment:
    VERSION: "11"
    RAM_SIZE: "8G"
    CPU_CORES: "4"

VERSION: “11” – это версия macOS, в данном случае Big Sur
RAM_SIZE: “8G” – это объем оперативной памяти, выделяемый для macOS
CPU_CORES: “4” – это количество ядер процессора, выделяемых для macOS

На текущий момент запуск macOS tahoe (16) также возможен, но есть ряд проблем которые пытаются доблестно решить разработчики проекта.

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

Сборка Swift в WSL2 (Linux)

Экосистема Swift активно развивается за пределами платформ Apple, и сегодня писать на нём под Windows вполне комфортно, используя Windows Subsystem for Linux (WSL2). Стоит учитывать, что для сборок под Linux/WSL доступен облегченный вариант Swift — без проприетарных Apple-фреймворков (таких как SwiftUI, UIKit, AppKit, CoreData, CoreML, ARKit, SpriteKit и других специфичных для iOS/macOS библиотек), однако для консольных утилит и бэкенда этого более чем достаточно. В этой заметке мы шаг за шагом разберём процесс подготовки окружения и сборки компилятора Swift из исходных кодов внутри WSL2 (на примере Ubuntu/Debian).

Обновляем список пакетов и саму систему:

sudo apt update && sudo apt upgrade -y

Устанавливаем необходимые зависимости для сборки:

sudo apt install -y \
  git cmake ninja-build clang python3 python3-pip \
  libicu-dev libxml2-dev libcurl4-openssl-dev \
  libedit-dev libsqlite3-dev swig libncurses5-dev \
  pkg-config tzdata rsync

Устанавливаем компилятор и компоновщик (LLVM и LLD):

sudo apt install -y llvm lld

Клонируем репозиторий Swift со всеми зависимостями:

git clone https://github.com/apple/swift.git
cd swift
utils/update-checkout --clone

Устанавливаем `swiftly` и готовый swift с swiftc

curl -O https://download.swift.org/swiftly/linux/swiftly-$(uname -m).tar.gz && \
tar zxf swiftly-$(uname -m).tar.gz && \
./swiftly init --quiet-shell-followup && \
. "${SWIFTLY_HOME_DIR:-$HOME/.local/share/swiftly}/env.sh" && \
hash -r

Запускаем сборку (это займёт продолжительное время):

utils/build-script \
  --release-debuginfo \
  --swift-darwin-supported-archs="x86_64" \
  --llvm-targets-to-build="X86" \
  --skip-build-benchmarks \
  --skip-test-cmark \
  --skip-test-swift \
  --skip-ios \
  --skip-tvos \
  --skip-watchos \
  --skip-build-libdispatch=false \
  --skip-build-cmark=false \
  --skip-build-foundation \
  --skip-build-lldb \
  --skip-build-xctest \
  --skip-test-swift

После завершения сборки добавляем путь к компилятору в PATH (укажите ваш путь до папки сборки):

export PATH=/root/Sources/3rdparty/build/Ninja-RelWithDebInfoAssert/swift-linux-x86_64/bin/swiftc:$PATH

Проверяем, что установленная версия Swift работает:

swift --version

Создаём тестовый файл и запускаем его:

echo "print(\"Hello, World!\")" > hello.swift
swift hello.swift

Также можно скомпилировать бинарный файл и запустить его:

swiftc hello.swift
./hello

Источники

Паттерн Интерпретатор на практике

В прошлой статье мы разобрали теорию паттерна Интерпретатор, узнали что такое AST-дерево и как абстрагировать терминальные и нетерминальные выражения. На этот раз давайте отойдем от теории и посмотрим, как этот паттерн применяется в серьезных коммерческих проектах, которыми мы все пользуемся ежедневно!

Спойлер: Вы, возможно, пользуетесь паттерном Интерпретатор прямо сейчас, просто читая этот текст в браузере!

Один из самых ярких и, пожалуй, самых важных примеров использования этого паттерна в индустрии — это JavaScript. Язык, который изначально создавался “на коленке”, сегодня работает на миллиардах устройств именно благодаря концепции интерпретации.

10 дней, которые перевернули интернет

История создания JavaScript полна легенд. В 1995 году Брендан Эйх (Brendan Eich), работая в Netscape Communications, получил задание: создать простой скриптовый язык, который мог бы выполняться прямо в браузере (Netscape Navigator), чтобы делать веб-странички интерактивными. Руководство хотело что-то с синтаксисом, похожим на сверхпопулярный тогда Java, но предназначенное не для профессиональных инженеров, а для веб-дизайнеров.

У Эйха было всего 10 дней на написание первого прототипа языка, который тогда назывался Mocha (затем LiveScript, и только потом JavaScript из маркетинговых соображений). Спешка была не случайной: на пятки наступала корпорация Microsoft, которая в это же время активно готовила свой собственный скриптовый язык VBScript для встраивания в браузер Internet Explorer. Netscape нужно было срочно выпустить свой ответ, чтобы не проиграть в надвигающейся браузерной войне.

Времени писать сложный компилятор в машинный код просто не было. Очевидным и самым быстрым решением для Эйха стала архитектура классического Интерпретатора.

Первый интерпретатор (SpiderMonkey) работал так:

  1. Он читал текстовый исходный код скрипта со страницы.
  2. Лексический анализатор разбивал текст на токены.
  3. Парсер строил Абстрактное Синтаксическое Дерево (AST). В терминах паттерна Интерпретатор это дерево состояло из терминальных выражений (строки, числа вроде 42) и нетерминальных (вызовы функций, операторы вроде If, While).
  4. Затем виртуальная машина шаг за шагом “обходила” это дерево, выполняя заложенные в нем инструкции у каждого узла (вызывая метод, аналогичный Interpret()).

Контекст (Context) и Объекты

Помните объект Context, который мы должны были передавать в метод Interpret(Context context) в классической реализации? Он нужен интерпретатору для хранения текущего состояния памяти.

В случае с JavaScript роль этого контекста на верхнем уровне играет Глобальный объект (например, window в браузере). Когда ваш AST-узел пытается, скажем, вывести текст на экран через document.write(“Hello”), интерпретатор обращается к своему контексту (объекту document) и вызывает нужный внутренний API браузера.

Именно благодаря интерпретатору JavaScript смог так легко взаимодействовать с DOM (Document Object Model) — всё это просто объекты в контексте, к которым обращаются узлы дерева.

Эволюция интерпретатора: JIT Компиляция

Исторически JS в браузерах долгое время оставался “чистым” интерпретатором. И у этого был большой минус — медленная скорость. Парсинг дерева и медленный обход каждого узла при каждом выполнении скрипта тормозил сложные веб-приложения.

С появлением движка V8 от Google (встроенного в Chrome) в 2008 году произошла революция. Инженеры поняли, что одного интерпретатора недостаточно для современного веба. Движок усложнился: он по-прежнему строит AST-дерево, но теперь использует JIT (Just-In-Time) компиляцию.

Современные JS-движки (V8, SpiderMonkey) работают как сложный конвейер:

  1. Быстрый и “тупой” базовый интерпретатор начинает выполнять ваш JS код моментально, даже не дожидаясь его компиляции (здесь по-прежнему работает классический паттерн).
  2. Параллельно, движок отслеживает “горячие” участки кода (циклы или функции, которые вызываются тысячи раз).
  3. Эти участки компилируются JIT-компилятором напрямую в оптимизированный машинный код, минуя медленный интерпретатор.

Именно это сочетание моментального старта интерпретатора и вычислительной мощи компиляции позволило JavaScript захватить мир, став языком серверов (Node.js) и мобильных приложений (React Native).

Интерпретатор в игровой индустрии

Несмотря на доминирование C++ в тяжелых вычислениях, паттерн Интерпретатор является индустриальным стандартом в геймдеве для создания игровой логики. Зачем? Чтобы геймдизайнеры могли делать игры без риска «уронить» движок или необходимости его постоянно перекомпилировать.

Отличным историческим примером является UnrealScript — язык, на котором была написана логика игр серий Unreal Tournament и Gears of War в Unreal Engine 1, 2 и 3. Текст компилировался в компактный байт-код абстрактной машины, который затем шаг за шагом 해석(интерпретировался) виртуальной машиной движка.

Визуальные граф-скрипты (Blueprints)

Сегодня на смену тексту пришло визуальное программирование — система Blueprints в Unreal Engine 4 и 5.

Если вы когда-либо открывали Blueprint в Unreal Engine, вы видели множество блоков-узлов (Nodes), соединенных «проводами». Архитектурно, весь граф Blueprints — это огромное Абстрактное Синтаксическое Дерево (AST), нарисованное на экране:

  1. Терминальные выражения (Terminal Expressions): Узлы-константы. Например, узел, который просто хранит число 42 или строку. Они возвращают конкретное значение при интерпретации.
  2. Нетерминальные выражения (Non-Terminal Expressions): Вычислительные узлы (сложение Add) или узлы контроля потока (Branch). У них есть входы-аргументы, которые интерпретатор сначала рекурсивно вычисляет, прежде чем выдать результат на выходной пин.

А роль контекста здесь играет память экземпляра конкретного игрового объекта (Actor). Interpreter Machine безопасно “гуляет” по этому графу, запрашивая данные и выполняя переходы.

Где еще используется Интерпретатор?

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

  • Интерпретируемые языки программирования (Python, Ruby, PHP). Весь их рантайм базируется на классическом паттерне. Например, эталонная реализация CPython сначала парсит ваш .py скрипт в AST, компилирует его в байт-код, а затем огромная виртуальная машина (цикл вычисления) интерпретирует этот байт-код шаг за шагом.
  • Java Virtual Machine (JVM). Изначально Java код компилируется не в машинные инструкции, а в байт-код. Когда вы запускаете приложение, JVM работает как интерпретатор (правда, с агрессивной JIT-компиляцией, как и в V8).
  • Базы данных и SQL. Когда вы отправляете SQL-запрос (SELECT * FROM users) в PostgreSQL или MySQL, движок базы данных выступает в роли интерпретатора. Он проводит лексический анализ, строит AST-дерево запроса, генерирует план выполнения и затем буквально «интерпретирует» этот план, перебирая строки таблиц.
  • Регулярные выражения (RegEx). Любой движок регулярных выражений внутри парсит строковый паттерн (например, ^\d{3}-\d{2}$) в граф состояний (NFA/DFA Автомат), по которому затем проходит внутренний интерпретатор, сопоставляя каждый вводимый символ с вершинами этого графа.
  • Unity Shader Graph / Unreal Material Editor — интерпретируют визуальные узлы в модульный шейдерный код (GLSL/HLSL).
  • Blender Geometry Nodes — интерпретируют математические и геометрические операции для процедурной генерации 3D-моделей в реальном времени.

Итог

Паттерн Интерпретатор давно вышел за рамки «написать свой калькулятор». Это мощнейший индустриальный стандарт. От JavaScript-движков, которые ежедневно исполняют гигабайты кода за кулисами браузеров, до игровых конструкторов, позволяющих строить сложную логику без знания C++ — интерпретаторы остаются одной из важнейших архитектурных концепций в современной IT-разработке.

ollama-call

Если вы используете Ollama и не хотите каждый раз писать собственную обвязку вокруг API,
проект ollama_call заметно упрощает работу.

Это небольшая Python-библиотека, которая позволяет отправить запрос к локальной LLM одной функцией
и сразу получить ответ, в том числе в JSON-формате.

Установка

pip install ollama-call

Зачем он нужен

  • минимальный код для работы с моделью;
  • структурированный JSON-ответ для дальнейшей обработки;
  • удобен для быстрых прототипов и MVP;
  • поддерживает потоковый вывод при необходимости.

Пример использования

from ollama_call import ollama_call

response = ollama_call(
    user_prompt="Hello, how are you?",
    format="json",
    model="gemma3:12b"
)

print(response)

Когда особенно полезен

  • вы пишете скрипты или сервисы поверх Ollama;
  • нужен предсказуемый формат ответа;
  • нет желания подключать тяжёлые фреймворки.

Итог

ollama_call — лёгкая и понятная обёртка для работы с Ollama из Python.
Хороший выбор, если важны простота и быстрый результат.

GitHub
https://github.com/demensdeum/ollama_call

SFAP: модульный фреймворк для современного сбора и обработки данных

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

SFAP (Seek · Filter · Adapt · Publish) — это open-source проект на Python,
который предлагает целостный и расширяемый подход к обработке данных на всех этапах их жизненного цикла:
от поиска источников до публикации готового результата.

Что такое SFAP

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

Проект основан на архитектурном паттерне Chain of Responsibility, что обеспечивает:

  • гибкость конфигурации пайплайна;
  • простое тестирование отдельных этапов;
  • масштабируемость под высокие нагрузки;
  • чистое разделение ответственности между компонентами.

Основные этапы пайплайна

Seek — поиск данных

На этом этапе происходит обнаружение источников данных: веб-страниц, API, файловых хранилищ
или других потоков информации. SFAP позволяет легко подключать новые источники без изменения
остальной системы.

Filter — фильтрация

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

Adapt — адаптация и обработка

Этап адаптации отвечает за преобразование данных: нормализацию, структурирование,
семантическую обработку и интеграцию с ИИ-моделями (в том числе генеративными).

Publish — публикация

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

Ключевые особенности проекта

  • Асинхронная архитектура на базе asyncio
  • Модульность и расширяемость
  • Поддержка сложных пайплайнов обработки
  • Готовность к интеграции с AI/LLM-решениями
  • Подходит для высоконагруженных систем

Практические сценарии использования

  • Агрегация и анализ новостных источников
  • Подготовка датасетов для машинного обучения
  • Автоматизированный контент-пайплайн
  • Очистка и нормализация больших потоков данных
  • Интеграция данных из разнородных источников

Начало работы с SFAP

Для старта достаточно:

  1. Клонировать репозиторий проекта;
  2. Установить зависимости Python;
  3. Определить собственные шаги пайплайна;
  4. Запустить асинхронный процесс обработки данных.

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

Заключение

SFAP — это не просто парсер или сборщик данных, а полноценный фреймворк для построения
современных data-pipeline-систем. Он подойдёт разработчикам и командам, которым важны
масштабируемость, архитектурная чистота и готовность к работе с интеллектуальной обработкой данных.
Исходный код проекта доступен на GitHub:
https://github.com/demensdeum/SFAP

Почему никак не получается исправить баг?

Вы часами сидите над кодом, перебираете гипотезы, правите условия, но баг все равно воспроизводится. Знакомо? Это состояние фрустрации часто называют «охотой на призраков». Кажется, что программа живет своей жизнью, игнорируя ваши исправления.

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

Ловушка «ложных симптомов»

Когда мы видим ошибку, наше внимание приковано к месту, где она «выстрелила». Но в сложных системах место проявления бага (crash или некорректное значение) — это лишь финал длинной цепочки событий. Пытаясь починить финал, вы боретесь с симптомами, а не с болезнью.

Именно здесь на помощь приходит концепция блок-схемы.

Как это работает в реальности

Конечно, прямо составлять (рисовать) блок-схему на бумаге каждый раз не обязательно, но важно иметь её в голове или под рукой как архитектурный ориентир. Блок-схема позволяет визуализировать работу приложения как дерево исходов.

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

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


Алгоритм победы над багом

Чтобы перестать биться в закрытую дверь, нужно изменить подход к диагностике:

  • Найдите состояние в дереве исходов: Прежде чем писать код, нужно точно определить путь, по которому прошло приложение. В какой точке логика свернула не туда? Какое именно состояние (State) привело к проблеме?
  • Воспроизведение — это 80% успеха: Обычно это делается силами тестировщиков и автотестов. Если баг «плавающий», к процессу подключается разработка для совместного поиска условий.
  • Используйте максимум информации: Для локализации важны логи, версия ОС, параметры устройства, тип подключения (Wi-Fi/5G) и даже конкретный оператор связи.

«Фотография» момента ошибки

В идеале для исправления нужно получить полное состояние приложения в момент воспроизведения бага. Также критически важны логи взаимодействия: они показывают не только финальную точку, но и весь путь пользователя (какие действия предшествовали сбою). Это помогает понять, как воссоздать подобное состояние снова.

Совет на будущее: Если вы столкнулись со сложным кейсом, добавьте в этот участок кода расширенную отладочную информацию (debug logging) на случай, если ситуация повторится.


Проблема «неуловимых» состояний в эпоху AI

В современных системах, использующих LLM (Large Language Models), классический детерминизм («один вход — один выход») часто нарушается. Вы можете передать абсолютно те же входные данные, но получить другой результат.

Это происходит из-за недетерминированности современных продакшн-систем:

  • Параллелизм на GPU: Операции с плавающей запятой в GPU не всегда ассоциативны. Из-за параллельного выполнения потоков порядок сложения чисел может незначительно меняться, что влияет на результат.
  • Температура GPU и троттлинг: Скорость выполнения и распределение нагрузки могут зависеть от физического состояния «железа». В огромных моделях эти микроскопические различия накапливаются и могут привести к выбору другого токена на выходе.
  • Динамический батчинг: В облаке ваш запрос объединяется с другими. Разный размер пакета (batch size) меняет математику вычислений в ядрах.

В таких условиях воспроизвести «то самое состояние» становится практически невозможно. Здесь спасает только статистический подход к тестированию.


Когда логика бессильна: Проблемы с памятью

Если вы работаете с «unsafe» языками (C или C++), баг может возникать из-за разрушения памяти (Memory Corruption).

Это самые тяжелые случаи: ошибка в одном модуле может «затереть» данные в другом. Это приводит к совершенно необъяснимым и единичным сбоям, которые невозможно отследить по обычной логике приложения.

Как защититься на уровне архитектуры?

Чтобы избежать таких «мистических» багов, стоит использовать современные подходы:

  • Паттерны многопоточного программирования: Четкая синхронизация исключает состояние гонки (race conditions).
  • Языки с безопасной многопоточностью: Инструменты, гарантирующие безопасность памяти еще на этапе компиляции:
    • Rust: Система владения (Ownership) исключает ошибки памяти.
    • Swift 6 Concurrency: Строгие проверки изоляции данных.
    • Erlang: Полная изоляция процессов через модель акторов.

Резюме

Исправление бага — это не про написание нового кода, а про понимание того, как работает старый. Помните: вы можете тратить время на правку ветки, в которую управление даже не заходит. Фиксируйте состояние системы, учитывайте фактор AI-недетерминированности и выбирайте безопасные инструменты.

Блок-схемы на практике без формалина

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

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

Пример 1: Упрощённая схема запуска игры
Чтобы понять принцип работы, давайте представим простую схему запуска игры.

Эта схема показывает идеальный сценарий, когда всё происходит без сбоев. Но в реальной жизни всё гораздо сложнее.

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

Эта схема уже более реалистична, но что произойдёт, если что-то пойдёт не так?

Как было: Игра, которая “ломалась” при потере интернета

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

В такой ситуации блок-схема их кода выглядела бы так:

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

Как стало: Исправление по жалобам пользователей

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

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

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

Неопределенное поведение

Зависания и ошибки — это лишь один из примеров непредсказуемого поведения программы. В программировании существует понятие неопределённого поведения (Undefined Behavior) — это ситуация, когда стандарт языка не описывает, как должна вести себя программа в определённом случае.

Это может привести к чему угодно: от случайного “мусора” в выводе до сбоя программы или даже серьёзной уязвимости безопасности. Неопределённое поведение часто возникает при работе с памятью, например, со строками в языке C.

Пример из языка C:

Представьте, что разработчик скопировал строку в буфер, но забыл добавить в конец нулевой символ (`\0`), который отмечает конец строки.

Вот как выглядит код:

#include 

int main() {
char buffer[5];
char* my_string = "hello";

memcpy(buffer, my_string, 5);

printf("%s\n", buffer);
return 0;
}

Ожидаемый результат: “hello”
Реальный результат Непредсказуем.

Почему так происходит? Функция `printf` с спецификатором `%s` ожидает, что строка завершается нулевым символом. Если его нет, она продолжит читать память за пределами выделенного буфера.

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

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

Pixel Perfect: Миф или реальность в эпоху декларативности?

В мире разработки интерфейсов существует расхожее понятие – “pixel perfect вёрстка”. Оно подразумевает максимально точное воспроизведение дизайн-макета до мельчайшего пикселя. Долгое время это было золотым стандартом, особенно в эру классического веб-дизайна. Однако с приходом декларативной вёрстки и стремительным ростом разнообразия устройств, принцип “pixel perfect” становится всё более эфемерным. Попробуем разобраться, почему.

Императивный WYSIWYG vs. Декларативный Код: В чём разница?

Традиционно многие интерфейсы, особенно десктопные, создавались с помощью императивных подходов или WYSIWYG (What You See Is What You Get) редакторов. В таких инструментах дизайнер или разработчик напрямую манипулирует элементами, располагая их на холсте с точностью до пикселя. Это похоже на работу с графическим редактором – вы видите, как ваш элемент выглядит, и можете точно его позиционировать. В этом случае достижение “pixel perfect” было вполне реальной целью.

Однако современная разработка всё чаще опирается на декларативную вёрстку. Это означает, что вы не говорите компьютеру “помести эту кнопку сюда”, а описываете, что вы хотите получить. Например, вместо того чтобы указывать конкретные координаты элемента, вы описываете его свойства: “эта кнопка должна быть красной, иметь отступы 16px со всех сторон и находиться в центре контейнера”. Фреймворки вроде React, Vue, SwiftUI или Jetpack Compose как раз и используют этот принцип.

Почему “Pixel Perfect” не работает с декларативной вёрсткой для множества устройств

Представьте себе, что вы создаёте приложение, которое должно одинаково хорошо выглядеть на iPhone 15 Pro Max, Samsung Galaxy Fold, iPad Pro и телевизоре с разрешением 4K. Каждое из этих устройств имеет разное разрешение экрана, плотность пикселей, соотношение сторон и физические размеры.

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

* Адаптивность и Отзывчивость: Основная цель декларативной вёрстки — создать адаптивные и отзывчивые интерфейсы. Это значит, что ваш интерфейс должен автоматически подстраиваться под размер и ориентацию экрана, не ломаясь и сохраняя читаемость. Если бы мы стремились к “pixel perfect” на каждом устройстве, нам пришлось бы создавать бесчисленное количество вариантов одного и того же интерфейса, что полностью нивелирует преимущества декларативного подхода.
* Плотность Пикселей (DPI/PPI): Устройства имеют разную плотность пикселей. Один и тот же элемент, имеющий размер 100 “виртуальных” пикселей, на устройстве с высокой плотностью будет выглядеть гораздо меньше, чем на устройстве с низкой плотностью, если не учитывать масштабирование. Декларативные фреймворки абстрагируются от физических пикселей, работая с логическими единицами.
* Динамический Контент: Контент в современных приложениях часто бывает динамическим – его объём и структура могут меняться. Если бы мы жёстко привязывались к пикселям, любое изменение текста или изображения привело бы к “разваливанию” макета.
* Различные Платформы: Помимо разнообразия устройств, существуют и разные операционные системы (iOS, Android, Web, Desktop). Каждая платформа имеет свои гайдлайны по дизайну, стандартные элементы управления и шрифты. Попытка сделать абсолютно идентичный, “pixel perfect” интерфейс на всех платформах привела бы к неестественному виду и плохому пользовательскому опыту.

Старые Подходы Не Ушли, А Эволюционировали

Важно понимать, что подход к вёрстке интерфейсов не является бинарным выбором между “императивным” и “декларативным”. Исторически для каждой платформы существовали свои инструменты и подходы к созданию интерфейсов.

* Нативные Интерфейсные Файлы: Для iOS это были XIB/Storyboards, для Android – XML-файлы разметки. Эти файлы представляют собой pixel-perfect WYSIWYG верстку, которая затем отображается в рантайме также как и в редакторе. Этот подход никуда не исчез, он продолжает развиваться, интегрируясь с современными декларативными фреймворками. Например, SwiftUI в Apple и Jetpack Compose в Android ступили на путь чисто декларативного кода, но при этом сохранили возможность использовать классическую верстку.
* Гибридные Решения: Часто в реальных проектах используется комбинация подходов. Например, базовая структура приложения может быть реализована декларативно, а для специфических, требующих точного позиционирования элементов, могут применяться более низкоуровневые, императивные методы или же подключаться нативные компоненты, разработанные с учётом специфики платформы.

От Монолита к Адаптивности: Как Эволюция Устройств Сформировала Декларативную Вёрстку

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

* Смартфонах всех форм-факторов и размеров экрана.
* Планшетах с их уникальными режимами ориентации и разделенного экрана.
* Ноутбуках и десктопах с различными разрешениями мониторов.
* Телевизорах и медиацентрах, управляемых дистанционно. Примечательно, что даже для телевизоров, пульты которых могут быть простыми, как Apple TV Remote с минимумом кнопок, или наоборот, перегруженными множеством функций, современные требования к интерфейсам таковы, что код не должен требовать специфической адаптации под эти особенности ввода. Интерфейс должен работать “как бы сам собой”, без дополнительного описания того, “как” именно взаимодействовать с конкретным пультом.
* Умных часах и носимых устройствах с минималистичными экранами.
* Шлемах виртуальной реальности (VR), требующих совершенно нового подхода к пространственному интерфейсу.
* Устройствах дополненной реальности (AR), накладывающих информацию на реальный мир.
* Автомобильных информационно-развлекательных системах.
* И даже бытовой технике: от холодильников с сенсорными экранами и стиральных машин с интерактивными дисплеями до умных духовок и систем “умного дома”.

Каждое из этих устройств имеет свои уникальные особенности: физические размеры, соотношение сторон, плотность пикселей, методы ввода (сенсорный экран, мышь, контроллеры, жесты, голосовые команды) и, что немаловажно, тонкости пользовательского окружения. Например, VR-шлем требует глубокого погружения, а смартфон — быстрой и интуитивной работы на ходу, тогда как интерфейс холодильника должен быть максимально простым и крупным для быстрой навигации.

Классический Подход: Бремя Поддержки Отдельных Интерфейсов

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

* Разработка под iOS часто требовала использования Storyboards или XIB-файлов в Xcode, написания кода на Objective-C или Swift.
* Для Android создавались XML-файлы разметки и код на Java или Kotlin.
* Веб-интерфейсы верстались на HTML/CSS/JavaScript.
* Для C++ приложений на различных десктопных платформах использовались свои специфические фреймворки и инструментарии:
* В Windows это были MFC (Microsoft Foundation Classes), Win32 API с ручной отрисовкой элементов или с использованием ресурсных файлов для диалоговых окон и элементов управления.
* В macOS применялись Cocoa (Objective-C/Swift) или старые Carbon API для прямого управления графическим интерфейсом.
* В Linux/Unix-подобных системах часто использовались библиотеки вроде GTK+ или Qt, которые предоставляли свой набор виджетов и механизмы для создания интерфейсов, нередко через XML-подобные файлы разметки (например, .ui файлы в Qt Designer) или прямое программное создание элементов.

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

Декларативная Вёрстка: Единый Язык для Разнообразия

Именно в ответ на это стремительное усложнение и появилась декларативная вёрстка как доминирующая парадигма. Фреймворки вроде React, Vue, SwiftUI, Jetpack Compose и других представляют собой не просто новый способ написания кода, а фундаментальный сдвиг в мышлении.

Основная идея декларативного подхода: вместо того чтобы говорить системе “как” отрисовывать каждый элемент (императивно), мы описываем “что” мы хотим увидеть (декларативно). Мы задаём свойства и состояние интерфейса, а фреймворк сам решает, как наилучшим образом отобразить его на конкретном устройстве.

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

1. Абстракция от Деталей Платформы: Декларативные UI фреймворки специально разработаны, чтобы забыть о низкоуровневых деталях отрисовки и специфике каждой платформы. Разработчик описывает компоненты и их взаимосвязи на более высоком уровне абстракции, используя единый, переносимый код.
2. Автоматическая Адаптация и Отзывчивость: Фреймворки берут на себя ответственность за автоматическое масштабирование, изменение макета и адаптацию элементов под различные размеры экранов, плотности пикселей и методы ввода. Это достигается за счёт использования гибких систем компоновки, таких как Flexbox или Grid, и концепций, подобных “логическим пикселям” или “dp” (density-independent pixels).
3. Согласованность Пользовательского Опыта: Несмотря на внешние различия, декларативный подход позволяет поддерживать единую логику поведения и взаимодействия по всему семейству устройств. Это упрощает процесс тестирования и обеспечивает более предсказуемый пользовательский опыт.
4. Ускорение Разработки и Снижение Затрат: С одним и тем же кодом, способным работать на множестве платформ, значительно снижаются время и стоимость разработки и поддержки. Команды могут сосредоточиться на функциональности и дизайне, а не на многократном переписывании одного и того же интерфейса.
5. Готовность к Будущему: Способность абстрагироваться от специфики текущих устройств делает декларативный код более устойчивым к появлению новых типов устройств и форм-факторов. Фреймворки могут быть обновлены для поддержки новых технологий, а ваш уже написанный код получит эту поддержку относительно бесшовно.

Заключение

Декларативная вёрстка — это не просто модное веяние, а необходимый эволюционный шаг, вызванный бурным развитием пользовательских устройств, включая и сферу интернета вещей (IoT) и умной бытовой техники. Она позволяет разработчикам и дизайнерам создавать сложные, адаптивные и единообразные интерфейсы, не утопая в бесконечных специфических реализациях для каждой платформы. Переход от императивного контроля над каждым пикселем к декларативному описанию желаемого состояния — это признание того, что в мире будущего интерфейсы должны быть гибкими, переносимыми и интуитивно понятными вне зависимости от того, на каком экране они отображаются.

Программистам, дизайнерам и пользователям необходимо научиться жить в этом новом мире. Лишние детали “pixel perfect” дизайна, привязанные к конкретному устройству или разрешению, приводят к ненужным временным затратам на разработку и поддержку. Более того, такие жёсткие макеты могут просто не отработать на устройствах с нестандартными интерфейсами, таких как телевизоры с ограниченным вводом, VR- и AR-шлемы, а также другие устройства будущего, о которых мы сегодня ещё даже не догадываемся. Гибкость и адаптивность – вот ключи к созданию успешных интерфейсов в современном мире.

Почему у программистов ничего не получается даже с нейросетями

Сегодня нейросети используются повсеместно. Программисты применяют их для генерации кода, объяснения чужих решений, автоматизации рутинных задач и даже создания целых приложений с нуля. Казалось бы, это должно привести к повышению эффективности, снижению ошибок и ускорению разработки. Но реальность оказывается намного прозаичнее: у многих по-прежнему ничего не получается. Нейросети не решают ключевые проблемы — они лишь подсвечивают глубину незнания.

Полная зависимость от LLM вместо понимания

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

Отсутствие контекста и устаревшие практики

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

Избыточность, неэффективность и отсутствие профилирования

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

Нейросеть не проводит профилирование, не учитывает ограничения CPU и GPU, не заботится об утечках памяти. Она не анализирует, насколько эффективно выполняется код на практике. Оптимизация — это по-прежнему ручная работа, требующая анализа и экспертизы. Без неё приложения становятся медленными, нестабильными и ресурсоёмкими, даже если выглядят «правильно» с точки зрения структуры.

Уязвимости и угроза безопасности

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

Закон Парето и суть недоработки

С нейросетями ярко работает закон Парето: 80% результата достигается за счёт 20% усилий. Модель может сгенерировать большое количество кода, создать основу проекта, раскидать структуру, оформить типы, подключить модули. Однако всё это может оказаться устаревшим, несовместимым с текущими версиями библиотек или фреймворков, и потребовать значительной ручной доработки. Автоматизация здесь работает скорее как черновик, который нуждается в проверке, переработке и адаптации под конкретные реалии проекта.

Осторожный оптимизм

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

Нейросети — мощный инструмент. Но чтобы он работал на вас, а не против вас, нужна база, критическое мышление и готовность в любой момент взять управление в свои руки.

Vibe-кодерские трюки: почему LLM пока не работают с SOLID, DRY и CLEAN

С развитием больших языковых моделей (LLM), таких как ChatGPT, всё больше разработчиков используют их для генерации кода, проектирования архитектуры и ускорения интеграции. Однако при практическом применении становится заметно: классические принципы архитектуры — SOLID, DRY, CLEAN — плохо уживаются с особенностями кодогенерации LLM.

Это не значит, что принципы устарели — напротив, они прекрасно работают при ручной разработке. Но с LLM подход приходится адаптировать.

Почему LLM не справляются с архитектурными принципами

Инкапсуляция

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

Абстракции и интерфейсы

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

DRY (Don’t Repeat Yourself)

LLM не стремятся минимизировать повторяющийся код — напротив, им проще дублировать блоки, чем выносить общую логику. Хотя они могут предложить рефакторинг по запросу, по умолчанию модели склонны генерировать «самодостаточные» фрагменты, даже если это приводит к избыточности.

CLEAN Architecture

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

Что работает лучше при работе с LLM

WET вместо DRY
Подход WET (Write Everything Twice) оказывается практичнее в работе с LLM. Дублирование кода не требует от модели удержания контекста, а значит — результат предсказуемее и легче исправляется вручную. Это также снижает вероятность появления неочевидных связей и багов.

Кроме того, дублирование помогает компенсировать короткую память модели: если определённый фрагмент логики встречается в нескольких местах, LLM с большей вероятностью будет его учитывать при дальнейшей генерации. Это упрощает сопровождение и увеличивает устойчивость к “забыванию”.

Простые структуры вместо инкапсуляции

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

Упрощённая архитектура

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

Интеграция SDK — вручную надёжнее

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

Почему принципы всё же работают — но при ручной разработке

Важно понимать, что сложности с SOLID, DRY и CLEAN касаются именно кодогенерации через LLM. Когда разработчик пишет код вручную, эти принципы продолжают демонстрировать свою ценность: снижают связанность, упрощают сопровождение, повышают читаемость и гибкость проекта.

Это связано с тем, что человеческое мышление склонно к обобщению. Мы ищем закономерности, выносим повторяющуюся логику в отдельные сущности, создаём паттерны. Вероятно, такое поведение имеет эволюционные корни: сокращение объёма информации экономит когнитивные ресурсы.

LLM же действуют иначе: они не испытывают нагрузки от объёма данных и не стремятся к экономии. Напротив, им проще работать с дублирующей, разрозненной информацией, чем строить и поддерживать сложные абстракции. Именно поэтому им легче справляться с кодом без инкапсуляции, с повторяющимися структурами и минимальной архитектурной строгостью.

Вывод

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

Принципы SOLID, DRY и CLEAN по-прежнему актуальны — но наилучший эффект они дают в руках человека. При работе с LLM разумно использовать упрощённый, практичный стиль, позволяющий получать надёжный и понятный код, который легко доработать вручную. А где LLM забывает — дублирование кода помогает ему вспомнить.

Портирование Surreal Engine C++ на WebAssembly

В этой заметке я опишу то как я портировал игровой движок Surreal Engine на WebAssembly.

Surreal Engine – игровой движок который реализует большую часть функционала движка Unreal Engine 1, известные игры на этом движке – Unreal Tournament 99, Unreal, Deus Ex, Undying. Он относится к классическим движкам, которые работали преимущественно в однопоточной среде выполнения.

Изначально у меня была идея взяться за проект который я не смогу выполнить в какой-либо разумный срок, таким образом показав своим подписчикам на Twitch, что есть проекты которые не могу сделать даже я. В первый же стрим я внезапно понял что задача портирования Surreal Engine C++ на WebAssembly с помощью Emscripten выполнима.

Surreal Engine Emscripten Demo

Спустя месяц я могу продемонстрировать свой форк и сборку движка на WebAssembly:
https://demensdeum.com/demos/SurrealEngine/

Управление как и в оригинале, осуществляется на стрелках клавиатуры. Далее планирую адаптацию под мобильное управление (тачи), добавление корректного освещения и прочие графические фишки рендера Unreal Tournament 99.

С чего начать?

Первое о чем хочется сказать, это то что любой проект можно портировать с C++ на WebAssembly с помощью Emscripten, вопрос лишь в том насколько полным получится функционал. Выбирайте проект порты библиотек которого уже доступны для Emscripten, в случае Surreal Engine очень сильно повезло, т.к. движок использует библиотеки SDL 2, OpenAL – они обе портированы под Emscripten. Однако в качестве графического API используется Vulkan, который на данный момент не доступен для HTML5, ведутся работы по реализации WebGPU, но он также находится в стадии черновика, также неизвестно насколько простым будет дальнейший порт из Vulkan на WebGPU, после полной стандартизации оного. Поэтому пришлось написать свой собственный базовый OpenGL-ES / WebGL рендер для Surreal Engine.

Сборка проекта

Система сборки в Surreal Engine – CMake, что тоже упрощает портирование, т.к. Emscripten предоставляет свои нативные сборщики – emcmake, emmake.
За основу порта Surreal Engine брался код моей последней игры на WebGL/OpenGL ES и C++ под названием Death-Mask, из-за этого разработка шла гораздо проще, все необходимые флаги сборки были с собой, примеры кода.

Один из важнейших моментов в CMakeLists.txt это флаги сборки для Emscripten, ниже пример из файла проекта:


-s MAX_WEBGL_VERSION=2 \

-s EXCEPTION_DEBUG \

-fexceptions \

--preload-file UnrealTournament/ \

--preload-file SurrealEngine.pk3 \

--bind \

--use-preload-plugins \

-Wall \

-Wextra \

-Werror=return-type \

-s USE_SDL=2 \

-s ASSERTIONS=1 \

-w \

-g4 \

-s DISABLE_EXCEPTION_CATCHING=0 \

-O3 \

--no-heap-copy \

-s ALLOW_MEMORY_GROWTH=1 \

-s EXIT_RUNTIME=1")

Сам сборочный скрипт:


emmake make -j 16

cp SurrealEngine.data /srv/http/SurrealEngine/SurrealEngine.data

cp SurrealEngine.js /srv/http/SurrealEngine/SurrealEngine.js

cp SurrealEngine.wasm /srv/http/SurrealEngine/SurrealEngine.wasm

cp ../buildScripts/Emscripten/index.html /srv/http/SurrealEngine/index.html

cp ../buildScripts/Emscripten/background.png /srv/http/SurrealEngine/background.png

Далее подготовим index.html, который включает в себя прелоадер файловой системы проекта. Для выкладывания в веб я использовал Unreal Tournament Demo версии 338. Как можно увидеть из файла CMake, распакованная папка игры была добавлена с сборочную директорию и прилинкована как preload-file для Emscripten.

Основные изменения кода

Затем предстояло поменять игровой цикл игры, запускать бесконечный цикл нельзя, это приводит к зависанию браузера, вместо этого нужно использовать emscripten_set_main_loop, об этой особенности я писал в своей заметке 2017 года “Портирование SDL C++ игры на HTML5 (Emscripten)
Код условия выхода из цикла while меняем на if, далее выводим основной класс игрового движка, который содержит игровой луп, в глобальный скоп, и пишем глобальную функцию которая будет вызывать шаг игрового цикла из глобального объекта:


#include <emscripten.h>

Engine *EMSCRIPTEN_GLOBAL_GAME_ENGINE = nullptr;

void emscripten_game_loop_step() {

	EMSCRIPTEN_GLOBAL_GAME_ENGINE->Run();

}

#endif

После этого нужно убедиться что в приложении отсутствуют фоновые потоки, если они есть, то приготовьтесь к переписываю их на однопоточное выполнение, либо использование библиотеки phtread в Emscripten.
Фоновый поток в Surreal Engine используется для проигрывания музыки, из главного потока движка приходят данные о текущем треке, о необходимости проигрывания музыки, либо ее отсутствии, затем фоновый поток по мьютексу получает новое состояние и начинает проигрывать новую музыку, либо приостанавливает. Фоновый поток также используется для буферизации музыки во время проигрывания.
Мои попытки собрать Surreal Engine под Emscripten с pthread не увенчались успехом, по той причине что порты SDL2 и OpenAL были собраны без поддержки pthread, а их пересборкой ради музыки я заниматься не хотел. Поэтому перенес функционал фонового потока музыки в однопоточное выполнение с помощью цикла. Удалив вызовы pthread из C++ кода, я перенес буферизацию, проигрывание музыки в основной поток, чтобы не было задержек я увеличил буфер на несколько секунд.

Далее я опишу уже конкретные реализации графики и звука.

Vulkan не поддерживается!

Да Vulkan не поддерживается в HTML5, хотя все рекламные брошюры выдают кроссплатформенность и широкую поддержку на платформах как основное преимущество Vulkan. По этой причине пришлось написать свой базовый рендер графики для упрощенного типа OpenGL – ES, он используется на мобильных устройствах, иногда не содержит модных фишек современного OpenGL, зато он очень хорошо переносится на WebGL, именно это реализует Emscripten. Написание базового рендера тайлов, bsp рендеринга, для простейшего отображения GUI, и отрисовки моделей + карт, удалось за две недели. Это, пожалуй, была самая сложная часть проекта. Впереди еще очень много работы по имплементации полного функционала рендеринга Surreal Engine, поэтому любая помощь читателей приветствуется в виде кода и pull request’ов.

OpenAL поддерживается!

Большим везением стало то, что Surreal Engine использует OpenAL для вывода звука. Написав простой hello world на OpenAL, и собрав его на WebAssembly c помощью Emscripten, мне стало ясно насколько все просто, и я отправился портировать звук.
После нескольких часов дебага, стало очевидно что в OpenAL реализации Emscripten есть несколько багов, например при инициализации считывания количества моно каналов, метод возвращал бесконечную цифру, а после попытки инициализации вектора бесконечного размера, падает уже C++ с исключением vector::length_error.
Это удалось обойти сделав хардкод количества моно каналов на 2048:


		alcGetIntegerv(alDevice, ALC_STEREO_SOURCES, 1, &stereoSources);



#if __EMSCRIPTEN__

		monoSources = 2048; // for some reason Emscripten's OpenAL gives infinite monoSources count, bug?

#endif



А сеть есть?

Surreal Engine сейчас не поддерживает сетевую игру, игра с ботами поддерживается, но нужен кто-то кто напишет ИИ для этих ботов. Теоретически реализовать сетевую игру на WebAssembly/Emscripten можно с помощью Websockets.

Заключение

В заключение хочется сказать что портирование Surreal Engine получилось достаточно гладким из-за использования библиотек для которых есть порты Emscripten, также мой прошлый опыт реализации игры на C++ для WebAssembly на Emscripten. Ниже ссылки на источники знаний, репозиториев по теме.
M-M-M-MONSTER KILL!

Также если вы хотите помочь проекту, желательно кодом рендера WebGL/OpenGL ES, то пишите мне в Telegram:
https://t.me/demenscave

Ссылки

https://demensdeum.com/demos/SurrealEngine/
https://github.com/demensdeum/SurrealEngine-Emscripten

https://github.com/dpjudas/SurrealEngine

Флеш жив – Interceptor 2021

Недавно оказалось что Adobe Flash достаточно стабильно работает под Wine. На 4-х часовом стриме сделал игру Interceptor 2021, это сиквел игры Interceptor 2020 которая была написана для ZX Spectrum.

Для тех кто в танке – технология Флеш обеспечивала интерактивность в вебе с 2000 по примерно 2015 год. К ее закрытию привело открытое письмо Стива Джобса в котором он написал что Флешу пора на свалку истории, т.к. на айфоне он тормозит. За это время JS стал тормозить еще больше чем флеш, а сам Флеш обернули в JS и теперь его можно запускать на чём угодно благодаря плееру Ruffle.

Поиграть можно тут:
https://demensdeum.com/demos/Interceptor2021

Видео:
https://www.youtube.com/watch?v=-3b5PkBvHQk

Исходный код:
https://github.com/demensdeum/Interceptor-2021

CRUD репозиторий

В этой заметке я опишу основные принципы известного классического паттерна CRUD, реализацию на языке Swift. Swift является открытым, кроссплатформенным языком, доступным для ОС Windows, Linux, macOS, iOS, Android.

Существует множество решений абстрагирования хранилища данных и логики приложения. Одним из таких решений является подход CRUD, это акроним от C – Create, R -Read, U – Update, D – Delete.
Обычно реализация этого принципа обеспечивается с помощью реализации интерфейса к базе данных, в котором работа с элементами происходит с использованием уникального идентификатора, например id. Создается интерфейс по каждой букве CRUD – Create(object, id), Read(id), Update(object, id), Delete(object, id).
Если объект содержит id внутри себя, то аргумент id можно упустить в части методов (Create, Update, Delete), так как туда передается объект целиком вместе со своим полем – id. А вот для – Read требуется id, так как мы хотим получить объект из базы данных по идентификатору.

Все имена вымышлены

Представим что гипотетическое приложение AssistantAI создавалось с использованием бесплатной SDK базы данных EtherRelm, интеграция была простой, API очень удобным, в итоге приложение было выпущено в маркеты.
Внезапно компания-разработчик SDK EtherRelm решает сделать её платной, устанавливая цену в 100$ в год за одного пользователя приложения.
Что? Да! Что же теперь делать разработчикам из AssistantAI, ведь у них уже 1млн активных пользователей! Платить 100 млн долларов?
Вместо этого принимается решение оценить перенос приложения на нативную для платформы базу данных RootData, по оценке программистов такой перенос займет около полугода, это без учета реализации новых фич в приложении. После недолгих раздумий, принимается решение убрать приложение из маркетов, переписать его на другом бесплатном кроссплатформенном фреймворке со встроенной базой данных BueMS, это решит проблему с платностью БД + упростит разработку на другие платформы.
Через год приложение переписано на BueMS, но тут внезапно разработчик фреймворка решает сделать его платным. Получается что команда попала в одну и ту же ловушку дважды, получится ли у них выбраться во второй раз, это уже совершенно другая история.

Абстракция на помощь

Этих проблем удалось бы избежать, если бы разработчики использовали абстракцию интерфейсов внутри приложения. К трем китам ООП – полиморфизму, инкапсуляции, наследованию, не так давно добавили еще одного – абстракцию.
Абстракция данных позволяет описывать идеи, модели в общих чертах, с минимум деталей, при этом достаточно точной для реализации конкретных имплементаций, которые используют для решения бизнес-задач.
Как мы можем абстрагировать работу с базой данных, чтобы логика приложения не зависела от нее? Используем подход CRUD!

Упрощенно UML схема CRUD выглядит так:

Пример с вымышленной базой данных EtherRelm:

Пример с настоящей базой данных SQLite:

Как вы уже заметили, при переключении базы данных, меняется только она, интерфейс CRUD с которым взаимодействует приложение остается неизменным. CRUD является вариантом реализации паттерна GoF – Адаптер, т.к. с помощью него мы адаптируем интерфейсы приложения к любой базе данных, совмещаем несовместимые интерфейсы.
Слова это пустое, покажи мне код
Для реализации абстракций в языках программирования используют интерфейсы/протоколы/абстрактные классы. Все это явления одного порядка, однако на собеседованиях вас могут попросить назвать разницу между ними, я лично считаю что в этом особого смысла нет т.к. единственная цель использования это реализация абстракции данных, в остальном это проверка памяти интервьюируемого.
CRUD часто реализуют в рамках паттерна Репозиторий, репозиторий однако может реализовывать интерфейс CRUD, а может и не реализовывать, всё зависит от изобретательности разработчика.

Рассмотрим достаточно типичный Swift код репозитория структур Book, работающий напрямую с базой данных UserDefaults:


struct Book: Codable {
	let title: String
	let author: String
}

class BookRepository {
	func save(book: Book) {
    		let record = try! JSONEncoder().encode(book)
    		UserDefaults.standard.set(record, forKey: book.title)
	}
    
	func get(bookWithTitle title: String) -> Book? {
    		guard let data = UserDefaults.standard.data(forKey: title) else { return nil }
    		let book = try! JSONDecoder().decode(Book.self, from: data)
    		return book
	}
    
	func delete(book: Book) {
    		UserDefaults.standard.removeObject(forKey: book.title)
	}
}

let book = Book(title: "Fear and Loathing in COBOL", author: "Sir Edsger ZX Spectrum")
let repository = BookRepository()
repository.save(book: book)
print(repository.get(bookWithTitle: book.title)!)
repository.delete(book: book)
guard repository.get(bookWithTitle: book.title) == nil else {
	print("Error: can't delete Book from repository!")
	exit(1)
}

Код выше кажется простым, однако посчитаем количество нарушений принципа DRY (Do not Repeat Yourself) и связанность кода:
Связанность с базой данных UserDefaults
Связанность с энкодерами и декодерами JSON – JSONEncoder, JSONDecoder
Связанность со структурой Book, а нам нужен абстрактный репозиторий чтобы не создавать по классу репозитория для каждой структуры, которую мы будем хранить в базе данных (нарушение DRY)

Такой код CRUD репозитория я встречаю достаточно часто, пользоваться им можно, однако высокая связанность, дублирование кода, приводят к тому что со временем его поддержка очень сильно усложнится. Особенно это будет ощущаться при попытке перейти на другую базу данных, либо при изменении внутренней логики работы с бд во всех созданных в приложении репозиториях.
Вместо того чтобы дублировать код, держать высокую связанность – напишем протокол для CRUD репозитория, таким образом абстрагируя интерфейс базы данных и бизнес-логики приложения, соблюдая DRY, осуществляя низкую связанность:

    typealias Item = Codable
    typealias ItemIdentifier = String
    
    func create<T: CRUDRepository.Item>(id: CRUDRepository.ItemIdentifier, item: T) async throws
    func read<T: CRUDRepository.Item>(id: CRUDRepository.ItemIdentifier) async throws -> T
    func update<T: CRUDRepository.Item>(id: CRUDRepository.ItemIdentifier, item: T) async throws
    func delete(id: CRUDRepository.ItemIdentifier) async throws
}

Протокол CRUDRepository описывает интерфейсы и ассоциированные типы данных для дальнейшей реализации конкретного CRUD репозитория.

Далее напишем конкретную реализацию для базы данных UserDefaults:

    private typealias RecordIdentifier = String
    
    let tableName: String
    let dataTransformer: DataTransformer
    
    init(
   	 tableName: String = "",
   	 dataTransformer: DataTransformer = JSONDataTransformer()
    ) {
   	 self.tableName = tableName
   	 self.dataTransformer = dataTransformer
    }
    
    private func key(id: CRUDRepository.ItemIdentifier) -> RecordIdentifier {
   	 "database_\(tableName)_item_\(id)"
    }
   	 
    private func isExists(id: CRUDRepository.ItemIdentifier) async throws -> Bool {
   	 UserDefaults.standard.data(forKey: key(id: id)) != nil
    }
    
    func create<T: CRUDRepository.Item>(id: CRUDRepository.ItemIdentifier, item: T) async throws {
   	 let data = try await dataTransformer.encode(item)
   	 UserDefaults.standard.set(data, forKey: key(id: id))
   	 UserDefaults.standard.synchronize()
    }
    
    func read<T: CRUDRepository.Item>(id: CRUDRepository.ItemIdentifier) async throws -> T {
   	 guard let data = UserDefaults.standard.data(forKey: key(id: id)) else {
   		 throw CRUDRepositoryError.recordNotFound(id: id)
   	 }
   	 let item: T = try await dataTransformer.decode(data: data)
   	 return item
    }
    
    func update<T: CRUDRepository.Item>(id: CRUDRepository.ItemIdentifier, item: T) async throws {
   	 guard try await isExists(id: id) else {
   		 throw CRUDRepositoryError.recordNotFound(id: id)
   	 }
   	 let data = try await dataTransformer.encode(item)
   	 UserDefaults.standard.set(data, forKey: key(id: id))
   	 UserDefaults.standard.synchronize()
    }
    
    func delete(id: CRUDRepository.ItemIdentifier) async throws {
   	 guard try await isExists(id: id) else {
   		 throw CRUDRepositoryError.recordNotFound(id: id)
   	 }
   	 UserDefaults.standard.removeObject(forKey: key(id: id))
   	 UserDefaults.standard.synchronize()
    }
}

Код выглядит длинным, однако содержит полную конкретную реализацию CRUD репозитория, содержащим слабую связанность, подробности далее.
typealias’ы добавлены для самодокументирования кода.
Слабая связанность и сильная связность
Отвязка от конкретной структуры (struct) реализуется с помощью генерика T, который в свою очередь должен имплементировать протоколы Codable. Codable позволяет производить преобразование структур с помощью классов которые реализуют протоколы TopLevelEncoder и TopLevelDecoder, например JSONEncoder и JSONDecoder, при использовании базовых типов (Int, String, Float и т.д.) нет необходимости писать дополнительный код для преобразования структур.

Отвязка от конкретного энкодера и декодера происходит с помощью абстрагирования в протоколе DataTransformer:

	func encode<T: Encodable>(_ object: T) async throws -> Data
	func decode<T: Decodable>(data: Data) async throws -> T
}

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

Далее приводится код конкретного DataTransformer, а именно для JSON:

	func encode<T>(_ object: T) async throws -> Data where T : Encodable {
    		let data = try JSONEncoder().encode(object)
    		return data
	}
    
	func decode<T>(data: Data) async throws -> T where T : Decodable {
    		let item: T = try JSONDecoder().decode(T.self, from: data)
    		return item
	}
}

А так можно было?

Что же изменилось? Теперь достаточно проинициализировать конкретный репозиторий для работы с любой структурой которая имплементирует протокол Codable, таким образом исчезает потребность в дублировании кода, реализуется слабая связанность приложения.

Пример клиентский CRUD с конкретным репозиторием, в качестве базы данных выступает UserDefaults, формат данных JSON, структура Client, также пример записи и считывания массива:


print("One item access example")

do {
	let clientRecordIdentifier = "client"
	let clientOne = Client(name: "Chill Client")
	let repository = UserDefaultsRepository(
    	tableName: "Clients Database",
    	dataTransformer: JSONDataTransformer()
	)
	try await repository.create(id: clientRecordIdentifier, item: clientOne)
	var clientRecord: Client = try await repository.read(id: clientRecordIdentifier)
	print("Client Name: \(clientRecord.name)")
	clientRecord.name = "Busy Client"
	try await repository.update(id: clientRecordIdentifier, item: clientRecord)
	let updatedClient: Client = try await repository.read(id: clientRecordIdentifier)
	print("Updated Client Name: \(updatedClient.name)")
	try await repository.delete(id: clientRecordIdentifier)
	let removedClientRecord: Client = try await repository.read(id: clientRecordIdentifier)
	print(removedClientRecord)
}
catch {
	print(error.localizedDescription)
}

print("Array access example")

let clientArrayRecordIdentifier = "clientArray"
let clientOne = Client(name: "Chill Client")
let repository = UserDefaultsRepository(
	tableName: "Clients Database",
	dataTransformer: JSONDataTransformer()
)
let array = [clientOne]
try await repository.create(id: clientArrayRecordIdentifier, item: array)
let savedArray: [Client] = try await repository.read(id: clientArrayRecordIdentifier)
print(savedArray.first!)

При первой проверке CRUD реализована обработка исключения, при которой чтение удаленного айтема будет уже недоступно.

Переключаем базы данных

Теперь я покажу как перенести текущий код на другую базу данных. Для примера возьму код репозитория SQLite который сгенерил ChatGPT:


class SQLiteRepository: CRUDRepository {
    private typealias RecordIdentifier = String
    
    let tableName: String
    let dataTransformer: DataTransformer
    private var db: OpaquePointer?

    init(
   	 tableName: String,
   	 dataTransformer: DataTransformer = JSONDataTransformer()
    ) {
   	 self.tableName = tableName
   	 self.dataTransformer = dataTransformer
   	 self.db = openDatabase()
   	 createTableIfNeeded()
    }
    
    private func openDatabase() -> OpaquePointer? {
   	 var db: OpaquePointer? = nil
   	 let fileURL = try! FileManager.default
   		 .url(for: .documentDirectory, in: .userDomainMask, appropriateFor: nil, create: false)
   		 .appendingPathComponent("\(tableName).sqlite")
   	 if sqlite3_open(fileURL.path, &db) != SQLITE_OK {
   		 print("error opening database")
   		 return nil
   	 }
   	 return db
    }
    
    private func createTableIfNeeded() {
   	 let createTableString = """
   	 CREATE TABLE IF NOT EXISTS \(tableName) (
   	 id TEXT PRIMARY KEY NOT NULL,
   	 data BLOB NOT NULL
   	 );
   	 """
   	 var createTableStatement: OpaquePointer? = nil
   	 if sqlite3_prepare_v2(db, createTableString, -1, &createTableStatement, nil) == SQLITE_OK {
   		 if sqlite3_step(createTableStatement) == SQLITE_DONE {
       		 print("\(tableName) table created.")
   		 } else {
       		 print("\(tableName) table could not be created.")
   		 }
   	 } else {
   		 print("CREATE TABLE statement could not be prepared.")
   	 }
   	 sqlite3_finalize(createTableStatement)
    }
    
    private func isExists(id: CRUDRepository.ItemIdentifier) async throws -> Bool {
   	 let queryStatementString = "SELECT data FROM \(tableName) WHERE id = ?;"
   	 var queryStatement: OpaquePointer? = nil
   	 if sqlite3_prepare_v2(db, queryStatementString, -1, &queryStatement, nil) == SQLITE_OK {
   		 sqlite3_bind_text(queryStatement, 1, id, -1, nil)
   		 if sqlite3_step(queryStatement) == SQLITE_ROW {
       		 sqlite3_finalize(queryStatement)
       		 return true
   		 } else {
       		 sqlite3_finalize(queryStatement)
       		 return false
   		 }
   	 } else {
   		 print("SELECT statement could not be prepared.")
   		 throw CRUDRepositoryError.databaseError
   	 }
    }
    
    func create<T: CRUDRepository.Item>(id: CRUDRepository.ItemIdentifier, item: T) async throws {
   	 let insertStatementString = "INSERT INTO \(tableName) (id, data) VALUES (?, ?);"
   	 var insertStatement: OpaquePointer? = nil
   	 if sqlite3_prepare_v2(db, insertStatementString, -1, &insertStatement, nil) == SQLITE_OK {
   		 let data = try await dataTransformer.encode(item)
   		 sqlite3_bind_text(insertStatement, 1, id, -1, nil)
   		 sqlite3_bind_blob(insertStatement, 2, (data as NSData).bytes, Int32(data.count), nil)
   		 if sqlite3_step(insertStatement) == SQLITE_DONE {
       		 print("Successfully inserted row.")
   		 } else {
       		 print("Could not insert row.")
       		 throw CRUDRepositoryError.databaseError
   		 }
   	 } else {
   		 print("INSERT statement could not be prepared.")
   		 throw CRUDRepositoryError.databaseError
   	 }
   	 sqlite3_finalize(insertStatement)
    }
    
    func read<T: CRUDRepository.Item>(id: CRUDRepository.ItemIdentifier) async throws -> T {
   	 let queryStatementString = "SELECT data FROM \(tableName) WHERE id = ?;"
   	 var queryStatement: OpaquePointer? = nil
   	 var item: T?
   	 if sqlite3_prepare_v2(db, queryStatementString, -1, &queryStatement, nil) == SQLITE_OK {
   		 sqlite3_bind_text(queryStatement, 1, id, -1, nil)
   		 if sqlite3_step(queryStatement) == SQLITE_ROW {
       		 let queryResultCol1 = sqlite3_column_blob(queryStatement, 0)
       		 let queryResultCol1Length = sqlite3_column_bytes(queryStatement, 0)
       		 let data = Data(bytes: queryResultCol1, count: Int(queryResultCol1Length))
       		 item = try await dataTransformer.decode(data: data)
   		 } else {
       		 throw CRUDRepositoryError.recordNotFound(id: id)
   		 }
   	 } else {
   		 print("SELECT statement could not be prepared")
   		 throw CRUDRepositoryError.databaseError
   	 }
   	 sqlite3_finalize(queryStatement)
   	 return item!
    }
    
    func update<T: CRUDRepository.Item>(id: CRUDRepository.ItemIdentifier, item: T) async throws {
   	 guard try await isExists(id: id) else {
   		 throw CRUDRepositoryError.recordNotFound(id: id)
   	 }
   	 let updateStatementString = "UPDATE \(tableName) SET data = ? WHERE id = ?;"
   	 var updateStatement: OpaquePointer? = nil
   	 if sqlite3_prepare_v2(db, updateStatementString, -1, &updateStatement, nil) == SQLITE_OK {
   		 let data = try await dataTransformer.encode(item)
   		 sqlite3_bind_blob(updateStatement, 1, (data as NSData).bytes, Int32(data.count), nil)
   		 sqlite3_bind_text(updateStatement, 2, id, -1, nil)
   		 if sqlite3_step(updateStatement) == SQLITE_DONE {
       		 print("Successfully updated row.")
   		 } else {
       		 print("Could not update row.")
       		 throw CRUDRepositoryError.databaseError
   		 }
   	 } else {
   		 print("UPDATE statement could not be prepared.")
   		 throw CRUDRepositoryError.databaseError
   	 }
   	 sqlite3_finalize(updateStatement)
    }
    
    func delete(id: CRUDRepository.ItemIdentifier) async throws {
   	 guard try await isExists(id: id) else {
   		 throw CRUDRepositoryError.recordNotFound(id: id)
   	 }
   	 let deleteStatementString = "DELETE FROM \(tableName) WHERE id = ?;"
   	 var deleteStatement: OpaquePointer? = nil
   	 if sqlite3_prepare_v2(db, deleteStatementString, -1, &deleteStatement, nil) == SQLITE_OK {
   		 sqlite3_bind_text(deleteStatement, 1, id, -1, nil)
   		 if sqlite3_step(deleteStatement) == SQLITE_DONE {
       		 print("Successfully deleted row.")
   		 } else {
       		 print("Could not delete row.")
       		 throw CRUDRepositoryError.databaseError
   		 }
   	 } else {
   		 print("DELETE statement could not be prepared.")
   		 throw CRUDRepositoryError.databaseError
   	 }
   	 sqlite3_finalize(deleteStatement)
    }
}

Или код CRUD репозитория для файловой системы который тоже сгенерила ChatGPT:


class FileSystemRepository: CRUDRepository {
	private typealias RecordIdentifier = String
    
	let directoryName: String
	let dataTransformer: DataTransformer
	private let fileManager = FileManager.default
	private var directoryURL: URL
    
	init(
    	directoryName: String = "Database",
    	dataTransformer: DataTransformer = JSONDataTransformer()
	) {
    	self.directoryName = directoryName
    	self.dataTransformer = dataTransformer
   	 
    	let paths = fileManager.urls(for: .documentDirectory, in: .userDomainMask)
    	directoryURL = paths.first!.appendingPathComponent(directoryName)
   	 
    	if !fileManager.fileExists(atPath: directoryURL.path) {
        	try? fileManager.createDirectory(at: directoryURL, withIntermediateDirectories: true, attributes: nil)
    	}
	}
    
	private func fileURL(id: CRUDRepository.ItemIdentifier) -> URL {
    	return directoryURL.appendingPathComponent("item_\(id).json")
	}
    
	private func isExists(id: CRUDRepository.ItemIdentifier) async throws -> Bool {
    	return fileManager.fileExists(atPath: fileURL(id: id).path)
	}
    
	func create<T: CRUDRepository.Item>(id: CRUDRepository.ItemIdentifier, item: T) async throws {
    	let data = try await dataTransformer.encode(item)
    	let url = fileURL(id: id)
    	try data.write(to: url)
	}
    
	func read<T: CRUDRepository.Item>(id: CRUDRepository.ItemIdentifier) async throws -> T {
    	let url = fileURL(id: id)
    	guard let data = fileManager.contents(atPath: url.path) else {
        	throw CRUDRepositoryError.recordNotFound(id: id)
    	}
    	let item: T = try await dataTransformer.decode(data: data)
    	return item
	}
    
	func update<T: CRUDRepository.Item>(id: CRUDRepository.ItemIdentifier, item: T) async throws {
    	guard try await isExists(id: id) else {
        	throw CRUDRepositoryError.recordNotFound(id: id)
    	}
    	let data = try await dataTransformer.encode(item)
    	let url = fileURL(id: id)
    	try data.write(to: url)
	}
    
	func delete(id: CRUDRepository.ItemIdentifier) async throws {
    	guard try await isExists(id: id) else {
        	throw CRUDRepositoryError.recordNotFound(id: id)
    	}
    	let url = fileURL(id: id)
    	try fileManager.removeItem(at: url)
	}
}

Заменяем репозиторий в клиентском коде:


print("One item access example")

do {
	let clientRecordIdentifier = "client"
	let clientOne = Client(name: "Chill Client")
	let repository = FileSystemRepository(
    	directoryName: "Clients Database",
    	dataTransformer: JSONDataTransformer()
	)
	try await repository.create(id: clientRecordIdentifier, item: clientOne)
	var clientRecord: Client = try await repository.read(id: clientRecordIdentifier)
	print("Client Name: \(clientRecord.name)")
	clientRecord.name = "Busy Client"
	try await repository.update(id: clientRecordIdentifier, item: clientRecord)
	let updatedClient: Client = try await repository.read(id: clientRecordIdentifier)
	print("Updated Client Name: \(updatedClient.name)")
	try await repository.delete(id: clientRecordIdentifier)
	let removedClientRecord: Client = try await repository.read(id: clientRecordIdentifier)
	print(removedClientRecord)
}
catch {
	print(error.localizedDescription)
}

print("Array access example")

let clientArrayRecordIdentifier = "clientArray"
let clientOne = Client(name: "Chill Client")
let repository = FileSystemRepository(
	directoryName: "Clients Database",
	dataTransformer: JSONDataTransformer()
)
let array = [clientOne]
try await repository.create(id: clientArrayRecordIdentifier, item: array)
let savedArray: [Client] = try await repository.read(id: clientArrayRecordIdentifier)
print(savedArray.first!)

Инициализация UserDefaultsRepository заменена на FileSystemRepository, с соотетствующими аргументами.
После запуска второго варианта клиентского кода, вы обнаружите в папке документов директорию “Clients Database”, которая будет содержать в себе файл сериализованного в JSON массива с одной структурой Client.

Переключаем формат хранения данных

Теперь попросим ChatGPT сгенерить энкодер и декодер для XML:

	let formatExtension = "xml"
    
	func encode<T: Encodable>(_ item: T) async throws -> Data {
    	let encoder = PropertyListEncoder()
    	encoder.outputFormat = .xml
    	return try encoder.encode(item)
	}
    
	func decode<T: Decodable>(data: Data) async throws -> T {
    	let decoder = PropertyListDecoder()
    	return try decoder.decode(T.self, from: data)
	}
}

Благодаря встроенным типам в Swift, задача для нейросети становится элементарной.

Заменяем JSON на XML в клиентском коде:


print("One item access example")

do {
	let clientRecordIdentifier = "client"
	let clientOne = Client(name: "Chill Client")
	let repository = FileSystemRepository(
    	directoryName: "Clients Database",
    	dataTransformer: XMLDataTransformer()
	)
	try await repository.create(id: clientRecordIdentifier, item: clientOne)
	var clientRecord: Client = try await repository.read(id: clientRecordIdentifier)
	print("Client Name: \(clientRecord.name)")
	clientRecord.name = "Busy Client"
	try await repository.update(id: clientRecordIdentifier, item: clientRecord)
	let updatedClient: Client = try await repository.read(id: clientRecordIdentifier)
	print("Updated Client Name: \(updatedClient.name)")
	try await repository.delete(id: clientRecordIdentifier)
	let removedClientRecord: Client = try await repository.read(id: clientRecordIdentifier)
	print(removedClientRecord)
}
catch {
	print(error.localizedDescription)
}

print("Array access example")

let clientArrayRecordIdentifier = "clientArray"
let clientOne = Client(name: "Chill Client")
let repository = FileSystemRepository(
	directoryName: "Clients Database",
	dataTransformer: XMLDataTransformer()
)
let array = [clientOne]
try await repository.create(id: clientArrayRecordIdentifier, item: array)
let savedArray: [Client] = try await repository.read(id: clientArrayRecordIdentifier)
print(savedArray.first!)

Клиентский код изменился только на одно выражение JSONDataTransformer -> XMLDataTransformer

Итог

CRUD репозитории один из паттернов проектирования, которые можно использовать для реализации слабой связанности компонентов архитектуры приложения. Еще одно из решений – использование ORM (Объектно-реляционный маппинг), если вкратце то в ОРМ используется подход при котором структуры полностью мапятся на базу данных, и затем изменения с моделями должны отображаться (маппиться(!)) на бд.
Но это уже совсем другая история.

Полная реализация репозиториев CRUD для Swift доступна по ссылке:
https://gitlab.com/demensdeum/crud-example

Кстати Swift давно поддерживается вне macOS, код из статьи был польностью написан и протестирован на Arch Linux.

Источники

https://developer.apple.com/documentation/combine/topleveldecoder
https://developer.apple.com/documentation/combine/toplevelencoder
https://en.wikipedia.org/wiki/Create,_read,_update_and_delete

dd input/output error

Что делать если при копировании нормального диска с помощью dd в Linux вы получили ошибку input/output error?

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

Обязательно проверьте такой диск с помощью S.M.A.R.T., скорее всего он покажет вам ошибки диска. Так было в моем случае, количество сбойных блоков было настолько огромным, что пришлось распрощаться со старым жестким диском и заменить его на новый SSD.

Проблема была в том, что на этом диске была полностью рабочая система с лицензионным софтом, который необходим в работе. Я предпринял попытку использовать partimage, для быстрого копирования данных, но вдруг обнаружил что утилита копирует лишь треть диска, далее завершается толи с segfault, толи с каким-то другим своим веселым Сишным/Сиплюсплюсным приколом.

Далее я попробовал скопировать данные с помощью dd, и обнаружилось что dd доходит примерно тудаже где и partimage, и потом наступает ошибка input/output error. При этом всякие веселые флажки навроде conv=noerr,skip или еще чего-то такого совершенно не помогали.

Зато данные на другой диск удалось скопировать без проблем с помощью утилиты GNU под названием ddrescue.

После этого мои волосы стали шелковистыми, вернулась жена, дети и собака перестала кусать диван.

Большим плюсом ddrescue является наличие встроенного прогрессбара, поэтому не приходится костылять какие-то ухищрения навроде pv и всяких не особо красивых флажков dd. Также ddrescure показывает количество попыток прочитать данные; еще на вики написано что утилита обладает каким-то сверх алгоритмом для считывания поврежденных данных, оставим это на проверку людям которые любят ковыряться в исходниках, мы же не из этих да?

https://ru.wikipedia.org/wiki/Ddrescue
https://www.gnu.org/software/ddrescue/ddrescue_ru.html

ChatGPT

Всем привет! В этой статье я хочу рассказать о ChatGPT – мощном языковом моделировании от OpenAI, которое может помочь в решении различных задач, связанных с обработкой текста. Я покажу, как этот инструмент работает, и как его можно использовать в практических ситуациях. Приступим!

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

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

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

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

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

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


На самом деле всё что выше написала ChatGPT полностью сама. Что? Да? Я сам в шоке!

Саму сетку можно опробовать здесь:
https://chat.openai.com/chat

Включаем подсветку USB клавиатуры на macOS

Недавно купил очень недорогую USB-клавиатуру Getorix GK-45X, с RGB подсветкой. Подключив ее к Макбуку Pro на процессоре M1 стало понятно что RGB подсветка не работает. Даже нажимая волшебную комбинацию Fn + Scroll Lock включить подсветку не удалось, менялся только уровень подсветки экрана макбука.
Решений этой проблемы несколько, а именно OpenRGB (не работает), HID LED Test (не работает). Cработала только утилита kvmswitch:
https://github.com/stoutput/OSX-KVM

Надо ее скачать из гитхаба и разрешить для запуска из терминала в Security панели System Settings.
Как я понял из описания, после запуска утилита отправляет нажатие Fn + Scroll Lock, таким образом включая/выключая подсветку на клавиатуре.

Tree sort

Tree sort – сортировка двоичным деревом поиска. Временная сложность – O(n²). В таком дереве у каждой ноды слева числа меньше ноды, справа больше ноды, при приходе от корня и распечатке значений слева направо, получаем отсортированный список чисел. Удивительно да?

Рассмотрим схему двоичного дерева поиска:

Derrick Coetzee (public domain)

Попробуйте вручную прочитать числа начиная с предпоследней левой ноды нижнего левого угла, для каждой ноды слева – нода – справа.

Получится так:

  1. Предпоследняя нода слева внизу – 3.
  2. У нее есть левая ветвь – 1.
  3. Берем это число (1)
  4. Дальше берем саму вершину 3 (1, 3)
  5. Справа ветвь 6, но она содержит ветви. Поэтому ее прочитываем таким же образом.
  6. CЛева ветвь ноды 6 число 4 (1, 3, 4)
  7. Сама нода 6 (1, 3, 4, 6)
  8. Справа 7 (1, 3, 4, 6, 7)
  9. Идем наверх к корневой ноде – 8 (1,3, 4 ,6, 7, 8)
  10. Печатаем все что справа по аналогии
  11. Получаем итоговый список – 1, 3, 4, 6, 7, 8, 10, 13, 14

Чтобы реализовать алгоритм в коде потребуются две функции:

  1. Сборка бинарного дерева поиска
  2. Распечатка бинарного дерева поиска в правильно порядке

Собирают бинарное древо поиска также как и прочитывают, к каждой ноде прицепляется число слева или справа, в зависимости от того – меньше оно или больше.

Пример на Lua:


function Node:new(value, lhs, rhs)
    output = {}
    setmetatable(output, self)
    self.__index = self  
    output.value = value
    output.lhs = lhs
    output.rhs = rhs
    output.counter = 1
    return output  
end

function Node:Increment()
    self.counter = self.counter + 1
end

function Node:Insert(value)
    if self.lhs ~= nil and self.lhs.value > value then
        self.lhs:Insert(value)
        return
    end

    if self.rhs ~= nil and self.rhs.value < value then
        self.rhs:Insert(value)
        return
    end

    if self.value == value then
        self:Increment()
        return
    elseif self.value > value then
        if self.lhs == nil then
            self.lhs = Node:new(value, nil, nil)
        else
            self.lhs:Insert(value)
        end
        return
    else
        if self.rhs == nil then
            self.rhs = Node:new(value, nil, nil)
        else
            self.rhs:Insert(value)
        end
        return
    end
end

function Node:InOrder(output)
    if self.lhs ~= nil then
       output = self.lhs:InOrder(output)
    end
    output = self:printSelf(output)
    if self.rhs ~= nil then
        output = self.rhs:InOrder(output)
    end
    return output
end

function Node:printSelf(output)
    for i=0,self.counter-1 do
        output = output .. tostring(self.value) .. " "
    end
    return output
end

function PrintArray(numbers)
    output = ""
    for i=0,#numbers do
        output = output .. tostring(numbers[i]) .. " "
    end    
    print(output)
end

function Treesort(numbers)
    rootNode = Node:new(numbers[0], nil, nil)
    for i=1,#numbers do
        rootNode:Insert(numbers[i])
    end
    print(rootNode:InOrder(""))
end


numbersCount = 10
maxNumber = 9

numbers = {}

for i=0,numbersCount-1 do
    numbers[i] = math.random(0, maxNumber)
end

PrintArray(numbers)
Treesort(numbers)

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

Ссылки

https://gitlab.com/demensdeum/algorithms/-/tree/master/sortAlgorithms/treesort

Источники

TreeSort Algorithm Explained and Implemented with Examples in Java | Sorting Algorithms | Geekific – YouTube

Tree sort – YouTube

Convert Sorted Array to Binary Search Tree (LeetCode 108. Algorithm Explained) – YouTube

Sorting algorithms/Tree sort on a linked list – Rosetta Code

Tree Sort – GeeksforGeeks

Tree sort – Wikipedia

How to handle duplicates in Binary Search Tree? – GeeksforGeeks

Tree Sort | GeeksforGeeks – YouTube

Bucket Sort

Bucket Sort – сортировка ведрами. Алгоритм похож на сортировку подсчетом, с той разницей что числа собираются в «ведра»-диапазоны, затем ведра сортируются с помощью любого другого, достаточно производительного, алгоритма сортировки, и финальным аккордом делается разворачивание «ведер» поочередно, в результате чего получается отсортированный список.

Временная сложность алгоритма O(nk). Алгоритм работает за линейное время для данных которые подчиняются равномерному закону распределения. Если говорить проще, то элементы должны быть в каком-то определенном диапазоне, без «вспесков», например числа от 0.0 до 1.0. Если среди таких чисел есть 4 или 999, то такой ряд по дворовым законам «ровным» уже не считается.

Пример реализации на Julia:

    buckets = Vector{Vector{Int}}()
    
    for i in 0:bucketsCount - 1
        bucket = Vector{Int}()
        push!(buckets, bucket)
    end

    maxNumber = maximum(numbers)

    for i in 0:length(numbers) - 1
        bucketIndex = 1 + Int(floor(bucketsCount * numbers[1 + i] / (maxNumber + 1)))
        push!(buckets[bucketIndex], numbers[1 + i])
    end

    for i in 0:length(buckets) - 1
        bucketIndex = 1 + i
        buckets[bucketIndex] = sort(buckets[bucketIndex])
    end

    flat = [(buckets...)...]
    print(flat, "\n")

end

numbersCount = 10
maxNumber = 10
numbers = rand(1:maxNumber, numbersCount)
print(numbers,"\n")
bucketsCount = 10
bucketSort(numbers, bucketsCount)

На производительность алгоритма также влияет число ведер, для большего количества чисел лучше взять большее число ведер (Algorithms in a nutshell by George T. Heineman)

Ссылки

https://gitlab.com/demensdeum/algorithms/-/tree/master/sortAlgorithms/bucketSort

Источники

https://www.youtube.com/watch?v=VuXbEb5ywrU
https://www.youtube.com/watch?v=ELrhrrCjDOA
https://medium.com/karuna-sehgal/an-introduction-to-bucket-sort-62aa5325d124
https://www.geeksforgeeks.org/bucket-sort-2/
https://ru.wikipedia.org/wiki/%D0%91%D0%BB%D0%BE%D1%87%D0%BD%D0%B0%D1%8F_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0
https://www.youtube.com/watch?v=LPrF9yEKTks
https://en.wikipedia.org/wiki/Bucket_sort
https://julialang.org/
https://www.oreilly.com/library/view/algorithms-in-a/9780596516246/ch04s08.html

Radixsort

Radix Sort – поразрядная сортировка. Алгоритм схож с сортировкой подсчетом тем, что отсутствует сравнение элементов, вместо этого элементы *посимвольно* группируются в *ведра* (buckets), ведро выбирается по индексу текущего числа-символа. Временная сложность – O(nd).

Работает примерно так:

  • На вход получим числа 6, 12, 44, 9
  • Создадим 10 ведер списков (0-9), в которые будем поразрядно складывать/сортировать числа.

Далее:

  1. Запускаем цикл со счетчиком i до максимального количества символов в числе
  2. По индексу i справа налево получаем один символ для каждого числа, если символа нет, то считаем что это ноль
  3. Символ преобразовываем в число
  4. Выбираем ведро по индексу – числу, кладем туда число полностью
  5. После окончания перебора чисел, преобразовываем все ведра назад в список чисел
  6. Получаем числа отсортированные по разряду
  7. Повторяем пока не кончатся все разряды

Пример Radix Sort на Scala:


import scala.util.Random.nextInt



object RadixSort {

    def main(args: Array[String]) = {

        var maxNumber = 200

        var numbersCount = 30

        var maxLength = maxNumber.toString.length() - 1



        var referenceNumbers = LazyList.continually(nextInt(maxNumber + 1)).take(numbersCount).toList

        var numbers = referenceNumbers

        

        var buckets = List.fill(10)(ListBuffer[Int]())



        for( i <- 0 to maxLength) { numbers.foreach( number => {

                    var numberString = number.toString

                    if (numberString.length() > i) {

                        var index = numberString.length() - i - 1

                        var character = numberString.charAt(index).toString

                        var characterInteger = character.toInt  

                        buckets.apply(characterInteger) += number

                    }

                    else {

                        buckets.apply(0) += number

                    }

                }

            )

            numbers = buckets.flatten

            buckets.foreach(x => x.clear())

        }

        println(referenceNumbers)

        println(numbers)

        println(s"Validation result: ${numbers == referenceNumbers.sorted}")

    }

}

Алгоритм также имеет версию для параллельного выполнения, например на GPU; также существует вариант битовой сортировки, что наверное, очень интересно и поистине захватывает дух!

Ссылки

https://gitlab.com/demensdeum/algorithms/-/blob/master/sortAlgorithms/radixSort/radixSort.scala

Источники

https://ru.wikipedia.org/wiki/%D0%9F%D0%BE%D1%80%D0%B0%D0%B7%D1%80%D1%8F%D0%B4%D0%BD%D0%B0%D1%8F_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0
https://www.geeksforgeeks.org/radix-sort/

https://www.youtube.com/watch?v=toAlAJKojos

https://github.com/gyatskov/radix-sort

Heapsort

Heapsort – пирамидальная сортировка. Временная сложность алгоритма – O(n log n), шустрый да? Я бы назвал эту сортировку – сортировкой падающих камушков. Объяснять её, как мне кажется, проще всего визуально.

На вход подается список цифр, например:
5, 0, 7, 2, 3, 9, 4

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

Сделаем двоичное дерево:
⠀⠀5
⠀0⠀7
2 3 9 4

Если долго смотреть на пирамидку, то можно увидеть что это просто числа из массива, идущие друг за другом, количество элементов в каждом этаже умножается на два.

Далее начинается самое интересное, отсортируем пирамидку снизу вверх, методом падающих камушков (heapify). Сортировку можно было бы начинать с последнего этажа (2 3 9 4 ), но смысла нет т.к. нет этажа ниже, куда можно было бы упасть.

Поэтому начинаем ронять элементы с предпоследнего этажа (0 7)
⠀⠀5
⠀0⠀7
2 3 9 4

Первый элемент для падения выбирается справа, нашем случае это 7, далее смотрим что под ним, а под ним 9 и 4, девятка больше четверки, так еще и девятка больше семерки! Роняем 7 на 9, а 9 поднимаем на место 7.
⠀⠀5
⠀0⠀9
2 3 7 4

Далее понимаем что семерке падать ниже некуда, переходим к числу 0 которое находится на предпоследнем этаже слева:
⠀⠀5
0⠀9
2 3 7 4

Смотрим что под ним – 2 и 3, два меньше трех, три больше нуля, поэтому меняем ноль и три местами:
⠀⠀5
⠀3⠀9
2 0 7 4

Когда добрались до конца этажа – переходите на этаж выше и роняйте там всё, если сможете.
В итоге получится структура данных – куча (heap), а именно max heap, т.к. наверху самый большой элемент:
⠀⠀9
⠀3⠀7
2 0 5 4

Если вернуть в представление массива, то получится список:
[9, 3, 7, 2, 0, 5, 4]

Из этого можно сделать вывод, что поменяв местами первый и последний элемент, мы получим первое число в окончательной отсортированной позиции, а именно 9 должна стоять в конце отсортированного списка, меняем местами:
[4, 3, 7, 2, 0, 5, 9]

Посмотрим на бинарное дерево:
⠀⠀4
⠀3⠀7
2 0 5 9

Получилась ситуация при которой нижняя часть древа отсортирована, нужно лишь уронить 4 до корректной позиции, повторяем алгоритм, но не учитываем уже отсортированные числа, а именно 9:
⠀⠀4
⠀3⠀7
2 0 5 9

⠀⠀7
⠀3⠀4
2 0 5 9

⠀⠀7
⠀3⠀5
2 0 4 9

Получилось что мы, уронив 4, подняли следующее после 9 самое больше число – 7. Меняем местами последнее неотсортированное число (4) и самое больше число (7)
⠀⠀4
⠀3⠀5
2 0 7 9

Получилось что теперь мы имеем два числа в корректной окончательной позиции:
4, 3, 5, 2, 0, 7, 9

Далее повторяем алгоритм сортировки, игнорируя уже отсортированные, в итоге получим кучу вида:
⠀⠀0
⠀2⠀3
4 5 7 9

Или в виде списка:
0, 2, 3, 4, 5, 7, 9

Реализация

Алгоритм обычно разделяют на три функции:

  1. Создание кучи
  2. Алгоритм просеивания (heapify)
  3. Замена последнего неотсортированного элемента и первого

Куча создается с помощью прохода по предпоследнему ряду бинарного дерева с помощью функции heapify, справа налево до конца массива. Далее в цикле делается первая замена чисел, после чего первый элемент падает/остается на месте, в результате чего самый большой элемент попадает на первое место, цикл повторяется с уменьшением участников на единицу, т.к. после каждого прохода в конце списка остаются отсортированные числа.

Пример Heapsort на Ruby:






module Colors



    BLUE = "\033[94m"



    RED = "\033[31m"



    STOP = "\033[0m"



end







def heapsort(rawNumbers)



    numbers = rawNumbers.dup







    def swap(numbers, from, to)



        temp = numbers[from]



        numbers[from] = numbers[to]



        numbers[to] = temp



    end







    def heapify(numbers)



        count = numbers.length()



        lastParentNode = (count - 2) / 2







        for start in lastParentNode.downto(0)



            siftDown(numbers, start, count - 1)



            start -= 1 



        end







        if DEMO



            puts "--- heapify ends ---"



        end



    end







    def siftDown(numbers, start, rightBound)      



        cursor = start



        printBinaryHeap(numbers, cursor, rightBound)







        def calculateLhsChildIndex(cursor)



            return cursor * 2 + 1



        end







        def calculateRhsChildIndex(cursor)



            return cursor * 2 + 2



        end            







        while calculateLhsChildIndex(cursor) <= rightBound



            lhsChildIndex = calculateLhsChildIndex(cursor)



            rhsChildIndex = calculateRhsChildIndex(cursor)







            lhsNumber = numbers[lhsChildIndex]



            biggerChildIndex = lhsChildIndex







            if rhsChildIndex <= rightBound



                rhsNumber = numbers[rhsChildIndex]



                if lhsNumber < rhsNumber



                    biggerChildIndex = rhsChildIndex



                end



            end







            if numbers[cursor] < numbers[biggerChildIndex]



                swap(numbers, cursor, biggerChildIndex)



                cursor = biggerChildIndex



            else



                break



            end



            printBinaryHeap(numbers, cursor, rightBound)



        end



        printBinaryHeap(numbers, cursor, rightBound)



    end







    def printBinaryHeap(numbers, nodeIndex = -1, rightBound = -1)



        if DEMO == false



            return



        end



        perLineWidth = (numbers.length() * 4).to_i



        linesCount = Math.log2(numbers.length()).ceil()



        xPrinterCount = 1



        cursor = 0



        spacing = 3



        for y in (0..linesCount)



            line = perLineWidth.times.map { " " }



            spacing = spacing == 3 ? 4 : 3



            printIndex = (perLineWidth / 2) - (spacing * xPrinterCount) / 2



            for x in (0..xPrinterCount - 1)



                if cursor >= numbers.length



                    break



                end



                if nodeIndex != -1 && cursor == nodeIndex



                    line[printIndex] = "%s%s%s" % [Colors::RED, numbers[cursor].to_s, Colors::STOP]



                elsif rightBound != -1 && cursor > rightBound



                    line[printIndex] = "%s%s%s" % [Colors::BLUE, numbers[cursor].to_s, Colors::STOP]



                else



                    line[printIndex] = numbers[cursor].to_s



                end



                cursor += 1



                printIndex += spacing



            end



            print line.join()



            xPrinterCount *= 2           



            print "\n"            



        end



    end







    heapify(numbers)



    rightBound = numbers.length() - 1







    while rightBound > 0



        swap(numbers, 0, rightBound)   



        rightBound -= 1



        siftDown(numbers, 0, rightBound)     



    end







    return numbers



end







numbersCount = 14



maximalNumber = 10



numbers = numbersCount.times.map { Random.rand(maximalNumber) }



print numbers



print "\n---\n"







start = Time.now



sortedNumbers = heapsort(numbers)



finish = Time.now



heapSortTime = start - finish







start = Time.now



referenceSortedNumbers = numbers.sort()



finish = Time.now



referenceSortTime = start - finish







print "Reference sort: "



print referenceSortedNumbers



print "\n"



print "Reference sort time: %f\n" % referenceSortTime



print "Heap sort:      "



print sortedNumbers



print "\n"



if DEMO == false



    print "Heap sort time:      %f\n" % heapSortTime



else



    print "Disable DEMO for performance measure\n"



end







if sortedNumbers != referenceSortedNumbers



    puts "Validation failed"



    exit 1



else



    puts "Validation success"



    exit 0



end



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

Ссылки

https://gitlab.com/demensdeum/algorithms/-/blob/master/sortAlgorithms/heapsort/heapsort.rb

Источники

http://rosettacode.org/wiki/Sorting_algorithms/Heapsort
https://www.youtube.com/watch?v=LbB357_RwlY

https://habr.com/ru/company/otus/blog/460087/

https://ru.wikipedia.org/wiki/Пирамидальная_сортировка

https://neerc.ifmo.ru/wiki/index.php?title=Сортировка_кучей

https://wiki5.ru/wiki/Heapsort

https://wiki.c2.com/?HeapSort

https://ru.wikipedia.org/wiki/Дерево (структура данных)

https://ru.wikipedia.org/wiki/Куча (структура данных)

https://www.youtube.com/watch?v=2DmK_H7IdTo

https://www.youtube.com/watch?v=kU4KBD4NFtw

https://www.youtube.com/watch?v=DU1uG5310x0

https://www.youtube.com/watch?v=BzQGPA_v-vc

https://www.geeksforgeeks.org/array-representation-of-binary-heap/

https://habr.com/ru/post/112222/

https://www.cs.usfca.edu/~galles/visualization/BST.html

https://www.youtube.com/watch?v=EQzqHWtsKq4

https://medium.com/@dimko1/%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B-%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B8-heapsort-796ba965018b

https://ru.wikibrief.org/wiki/Heapsort

https://www.youtube.com/watch?v=GUUpmrTnNbw

Вымирание пчёл

Недавно оказалось что для пользователей современных GPU Nvidia под Arch Linux совершенно не нужно пользоваться пакетом bumblebee, у меня например он не определял внешний монитор при подключении. Рекомендую удалить пакет bumblebee и все связанные с ним пакеты, и установить prime по инструкции в Arch Wiki.
Далее для запуска всех игр в Steam и 3D приложений добавляем prime-run, для Стима это делается так prime-run %command% в дополнительных параметрах запуска.
Для проверки корректности можно использовать glxgears, prime-run glxgears.
https://bbs.archlinux.org/viewtopic.php?pid=2048195#p2048195

Quicksort

Quicksort – алгоритм сортировки по методу «разделяй и влавствуй». Рекурсивно, по частям разбираем массив чисел, выставляя числа в меньшем и большем порядке от выбранного опорного элемента, сам опорный элемент вставляем в отсечку между ними. После нескольких рекурсивных итераций получится отсортированный список. Временная сложность O(n2).

Схема:

  1. Начинаем с того что получаем снаружи список элементов, границы сортировки. На первом шаге границы сортировки будут от начала до конца.
  2. Проверяем что границы начала и конца не пересекаются, если это произошло, значит пора заканчивать
  3. Выбираем какой-то элемент из списка, называем его опорным
  4. Сдвигаем вправо в конец на последний индекс, чтобы не мешался
  5. Создаем счетчик *меньших чисел* пока равный нулю
  6. Проходим циклом по списку слева направо, до последнего индекса, где находится опорный элемент, не включительно
  7. Каждый элемент сравниваем с опорным
  8. Если он меньше опорного, то меняем его местами по индексу счетчика меньших чисел. Инкрементируем счетчик меньших чисел.
  9. Когда цикл дойдет до опорного элемента, останавливаемся, меняем местами опорный элемент с элементом по счетчику меньших чисел.
  10. Запускаем отдельно алгоритм для левой меньшей части списка, и отдельно для правой большей части списка.
  11. В итоге все рекурсивные итерации начнут останавливаться из-за проверки в пункте 2
  12. Получим отсортированный список

Quicksort был придуман ученым Чарльзом Энтони Ричардом Хоаром в МГУ, выучив русский язык, он занимался изучением компьютерного перевода, а также теории вероятностей в школе Колмогорова. В 1960 г. из-за политического кризиса, он покинул Советский Союз.

Пример реализации на Rust:


use rand::Rng;

fn swap(numbers: &mut [i64], from: usize, to: usize) {
    let temp = numbers[from];
    numbers[from] = numbers[to];
    numbers[to] = temp;
}

fn quicksort(numbers: &mut [i64], left: usize, right: usize) {
    if left >= right {
        return
    }
    let length = right - left;
    if length <= 1 {
        return
    }
    let pivot_index = left + (length / 2);
    let pivot = numbers[pivot_index];

    let last_index = right - 1;
    swap(numbers, pivot_index, last_index);

    let mut less_insert_index = left;

    for i in left..last_index {
        if numbers[i] < pivot {
            swap(numbers, i, less_insert_index);
            less_insert_index += 1;
        }
    }
    swap(numbers, last_index, less_insert_index);
    quicksort(numbers, left, less_insert_index);
    quicksort(numbers, less_insert_index + 1, right);
}

fn main() {
    let mut numbers = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0];
    let mut reference_numbers = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0];

    let mut rng = rand::thread_rng();
    for i in 0..numbers.len() {
        numbers[i] = rng.gen_range(-10..10);
        reference_numbers[i] = numbers[i];
    }

    reference_numbers.sort();

  println!("Numbers           {:?}", numbers);
  let length = numbers.len();
  quicksort(&mut numbers, 0, length);
  println!("Numbers           {:?}", numbers);
  println!("Reference numbers {:?}", reference_numbers);

  if numbers != reference_numbers {
    println!("Validation failed");
    std::process::exit(1);
  }
  else {
    println!("Validation success!");
    std::process::exit(0);
  }
}

Если ничего непонятно, то предлагаю посмотреть видео Роба Эдвардса из университета Сан-Диего https://www.youtube.com/watch?v=ZHVk2blR45Q в нем наиболее просто, по шагам, показывается суть и реализация алгоритма.

Ссылки

https://gitlab.com/demensdeum/algorithms/-/tree/master/sortAlgorithms/quickSort

Источники

https://www.youtube.com/watch?v=4s-aG6yGGLU
https://www.youtube.com/watch?v=ywWBy6J5gz8
https://www.youtube.com/watch?v=Hoixgm4-P4M
https://ru.wikipedia.org/wiki/Быстрая_сортировка
https://www.youtube.com/watch?v=Hoixgm4-P4M
https://www.youtube.com/watch?v=XE4VP_8Y0BU
https://www.youtube.com/watch?v=MZaf_9IZCrc
https://www.youtube.com/watch?v=ZHVk2blR45Q
http://rosettacode.org/wiki/Sorting_algorithms/Quicksort
https://www.youtube.com/watch?v=4s-aG6yGGLU
https://www.youtube.com/watch?v=dQw4w9WgXcQ
https://www.youtube.com/watch?v=maibrCbZWKw
https://www.geeksforgeeks.org/quick-sort/
https://www.youtube.com/watch?v=uXBnyYuwPe8

Binary Insertion Sort

Binary Insertion Sort – вариант сортировки вставками, в котором позицию для вставки определяют с помощью двоичного поиска. Временная сложность алгоритма O(n2)

Алгоритм работает так:

  1. Запускается цикл от нуля до конца списка
  2. В цикле выбирается число для сортировки, число сохраняется в отдельную переменную
  3. Бинарным поиском ищется индекс для вставки этого числа по сравнению с числами слева
  4. После нахождения индекса, числа слева сдвигаются на одну позицию вправо, начиная с индекса вставки. В процессе будет стерто число которое нужно отсортировать.
  5. Сохраненное ранее число вставляется по индексу вставки
  6. По окончанию цикла весь список будет отсортирован

Во время выполнения бинарного поиска, возможна ситуация когда число не будет найдено, со-но не возвращен индекс. Из-за особенности работы бинарного поиска, будет найдено число наиболее близкое к искомому, тогда для возврата индекса нужно будет сравнить его с искомым, если искомое меньше, то искомое должно быть по индексу слева, а если больше или равно то справа.

Код на Go:


import (
	"fmt"
	"math/rand"
	"time"
)

const numbersCount = 20
const maximalNumber = 100

func binarySearch(numbers []int, item int, low int, high int) int {
	for high > low {
		center := (low + high) / 2
		if numbers[center] < item { low = center + 1 } else if numbers[center] > item {
			high = center - 1
		} else {
			return center
		}
	}

	if numbers[low] < item {
		return low + 1
	} else {
		return low
	}
}

func main() {
	rand.Seed(time.Now().Unix())
	var numbers [numbersCount]int
	for i := 0; i < numbersCount; i++ {
		numbers[i] = rand.Intn(maximalNumber)
	}
	fmt.Println(numbers)

	for i := 1; i < len(numbers); i++ { searchAreaLastIndex := i - 1 insertNumber := numbers[i] insertIndex := binarySearch(numbers[:], insertNumber, 0, searchAreaLastIndex) for x := searchAreaLastIndex; x >= insertIndex; x-- {
			numbers[x+1] = numbers[x]
		}
		numbers[insertIndex] = insertNumber
	}
	fmt.Println(numbers)
}

Ссылки

https://gitlab.com/demensdeum/algorithms/-/blob/master/sortAlgorithms/binaryInsertionSort/binaryInsertionSort.go

Источники

https://www.geeksforgeeks.org/binary-insertion-sort/
https://www.youtube.com/watch?v=-OVB5pOZJug

Shell Sort

Shell Sort – вариант сортировки вставками с предварительным причесыванием массива чисел.

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

1. Запускается цикл от нуля до конца цикла, таким образом массив разделяется на две части
2. Для левой части запускается второй цикл, сравнение элементов справа налево, меньший элемент справа опускается пока не найдется меньший элемент слева
3. По окончанию обоих циклов, получим отсортированный список

Однажды во времени, информатик Дональд Шелл озадачился как улучшить алгоритм сортировки вставками. Он придумал предварительно проходить также двумя циклами по массиву, но на определенном расстоянии, постепенно уменьшая «расческу» пока она не превратиться в обычный алгоритм сортировки вставками. Всё действительно настолько просто, никаких подводных камней, к двум циклам сверху добавляем еще один, в котором уменьшаем постепенно размер «расчески». Единственное что нужно будет делать – проверять расстояние при сравнении, чтобы оно не вышло за пределы массива.

По настоящему интересная тема – выбор последовательности изменения длины сравнения на каждой итерации первого цикла. Интересна по той причине, что от этого зависит производительность алгоритма.

Таблицу известных вариантов и временную сложность можно посмотреть здесь: https://en.wikipedia.org/wiki/Shellsort#Gap_sequences

Вычислением идеальной дистанции занимались разные люди, настолько, видимо, была им эта тема интересна. Неужели они не могли просто запустить Ruby, вызвать самый быстрый алгоритм sort()?

В общем эти странные люди писали диссертации на тему вычисления дистанции/зазора «расчески» для алгоритма Шелла. Я же просто воспользовался результатами их труда и проверил 5 типов последовательностей, Хиббарда, Кнута-Пратта, Чиуры, Седжвика.

import time
import random
from functools import reduce
import math

DEMO_MODE = False

if input("Demo Mode Y/N? ").upper() == "Y":
    DEMO_MODE = True

class Colors:
    BLUE = '\033[94m'
    RED = '\033[31m'
    END = '\033[0m'

def swap(list, lhs, rhs):
    list[lhs], list[rhs] = list[rhs], list[lhs]
    return list

def colorPrintoutStep(numbers: List[int], lhs: int, rhs: int):
    for index, number in enumerate(numbers):
        if index == lhs:
            print(f"{Colors.BLUE}", end = "")
        elif index == rhs:
            print(f"{Colors.RED}", end = "")
        print(f"{number},", end = "")
        if index == lhs or index == rhs:
            print(f"{Colors.END}", end = "")
        if index == lhs or index == rhs:
            print(f"{Colors.END}", end = "")
    print("\n")
    input(">")

def ShellSortLoop(numbers: List[int], distanceSequence: List[int]):
    distanceSequenceIterator = reversed(distanceSequence)
    while distance:= next(distanceSequenceIterator, None):
        for sortArea in range(0, len(numbers)):
            for rhs in reversed(range(distance, sortArea + 1)):
                lhs = rhs - distance
                if DEMO_MODE:
                    print(f"Distance: {distance}")
                    colorPrintoutStep(numbers, lhs, rhs)
                if numbers[lhs] > numbers[rhs]:
                    swap(numbers, lhs, rhs)
                else:
                    break

def ShellSort(numbers: List[int]):
    global ShellSequence
    ShellSortLoop(numbers, ShellSequence)

def HibbardSort(numbers: List[int]):
    global HibbardSequence
    ShellSortLoop(numbers, HibbardSequence)

def ShellPlusKnuttPrattSort(numbers: List[int]):
    global KnuttPrattSequence
    ShellSortLoop(numbers, KnuttPrattSequence)

def ShellPlusCiuraSort(numbers: List[int]):
    global CiuraSequence
    ShellSortLoop(numbers, CiuraSequence)

def ShellPlusSedgewickSort(numbers: List[int]):
    global SedgewickSequence
    ShellSortLoop(numbers, SedgewickSequence)

def insertionSort(numbers: List[int]):
    global insertionSortDistanceSequence
    ShellSortLoop(numbers, insertionSortDistanceSequence)

def defaultSort(numbers: List[int]):
    numbers.sort()

def measureExecution(inputNumbers: List[int], algorithmName: str, algorithm):
    if DEMO_MODE:
        print(f"{algorithmName} started")
    numbers = inputNumbers.copy()
    startTime = time.perf_counter()
    algorithm(numbers)
    endTime = time.perf_counter()
    print(f"{algorithmName} performance: {endTime - startTime}")

def sortedNumbersAsString(inputNumbers: List[int], algorithm) -> str:
    numbers = inputNumbers.copy()
    algorithm(numbers)
    return str(numbers)

if DEMO_MODE:
    maximalNumber = 10
    numbersCount = 10
else:
    maximalNumber = 10
    numbersCount = random.randint(10000, 20000)

randomNumbers = [random.randrange(1, maximalNumber) for i in range(numbersCount)]

ShellSequenceGenerator = lambda n: reduce(lambda x, _: x + [int(x[-1]/2)], range(int(math.log(numbersCount, 2))), [int(numbersCount / 2)])
ShellSequence = ShellSequenceGenerator(randomNumbers)
ShellSequence.reverse()
ShellSequence.pop()

HibbardSequence = [
    0, 1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095,
    8191, 16383, 32767, 65535, 131071, 262143, 524287, 1048575,
    2097151, 4194303, 8388607, 16777215, 33554431, 67108863, 134217727,
    268435455, 536870911, 1073741823, 2147483647, 4294967295, 8589934591
]

KnuttPrattSequence = [
    1, 4, 13, 40, 121, 364, 1093, 3280, 9841, 29524, 88573, 265720, 
    797161, 2391484, 7174453, 21523360, 64570081, 193710244, 581130733, 
    1743392200, 5230176601, 15690529804, 47071589413
]

CiuraSequence = [
            1, 4, 10, 23, 57, 132, 301, 701, 1750, 4376, 
            10941, 27353, 68383, 170958, 427396, 1068491, 
            2671228, 6678071, 16695178, 41737946, 104344866, 
            260862166, 652155416, 1630388541
]

SedgewickSequence = [
            1, 5, 19, 41, 109, 209, 505, 929, 2161, 3905,
            8929, 16001, 36289, 64769, 146305, 260609, 587521, 
            1045505, 2354689, 4188161, 9427969, 16764929, 37730305, 
            67084289, 150958081, 268386305, 603906049, 1073643521, 
            2415771649, 4294770689, 9663381505, 17179475969
]

insertionSortDistanceSequence = [1]

algorithms = {
    "Default Python Sort": defaultSort,
    "Shell Sort": ShellSort,
    "Shell + Hibbard" : HibbardSort,
    "Shell + Prat, Knutt": ShellPlusKnuttPrattSort,
    "Shell + Ciura Sort": ShellPlusCiuraSort,
    "Shell + Sedgewick Sort": ShellPlusSedgewickSort,
    "Insertion Sort": insertionSort
}

for name, algorithm in algorithms.items():
    measureExecution(randomNumbers, name, algorithm)

reference = sortedNumbersAsString(randomNumbers, defaultSort)

for name, algorithm in algorithms.items():
    if sortedNumbersAsString(randomNumbers, algorithm) != reference:
        print("Sorting validation failed")
        exit(1)

print("Sorting validation success")
exit(0)

В моей реализации, для случайного набора числем самыми быстрыми оказываются зазоры Седжвика и Хиббарда.

mypy

Также хочется упомянуть анализатор статической типизации для Python 3 – mypy. Помогает справиться с проблемами присущими языкам с динамической типизацией, а именно устраняет возможность просунуть что-то куда не надо.

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

Ссылки

https://gitlab.com/demensdeum/algorithms/-/tree/master/sortAlgorithms/shellSort
http://mypy-lang.org/

Источники

https://dl.acm.org/doi/10.1145/368370.368387
https://en.wikipedia.org/wiki/Shellsort
http://rosettacode.org/wiki/Sorting_algorithms/Shell_sort
https://ru.wikipedia.org/wiki/Сортировка_Шелла
https://neerc.ifmo.ru/wiki/index.php?title=Сортировка_Шелла
https://twitter.com/gvanrossum/status/700741601966985216

Double Selection Sort

Double Selection Sort – подвид сортировки выбором, вроде как должен ускоряться в два раза. Ванильный алгоритм проходит двойным циклом по списку чисел, находит минимальное число и меняет местами с текущей цифрой на которую указывает цикл на уровне выше. Двойная сортировка выбором же ищет минимальное и максимальное число, далее происходит замена двух цифр, на которые указывает цикл на уровне выше – два числа слева и справа. Заканчивается вся эта вакханалия когда курсоры чисел для замены встречаются в середине списка, по итогу слева и справа от визуального центра получаются отсортированные числа.
Временная сложность алгоритма аналогична Selection Sort – O(n2), но якобы есть ускорение на 30%.

Пограничное состояние

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

  maximalNumberIndex = minimalNumberIndex;
}

Реализация на Cito

Cito – язык либ, язык транслятор. На нем можно писать для C, C++, C#, Java, JavaScript, Python, Swift, TypeScript, OpenCL C, при этом совершенно ничего не зная про эти языки. Исходный код на языке Cito транслируется в исходный код на поддерживаемых языках, далее можно использовать как библиотеку, либо напрямую, исправив сгенеренный код руками. Эдакий Write once – translate to anything.
Double Selection Sort на cito:

{
    public static int[] sort(int[]# numbers, int length)
    {
        int[]# sortedNumbers = new int[length];
        for (int i = 0; i < length; i++) {
            sortedNumbers[i] = numbers[i];
        }
        for (int leftCursor = 0; leftCursor < length / 2; leftCursor++) {
            int minimalNumberIndex = leftCursor;
            int minimalNumber = sortedNumbers[leftCursor];

            int rightCursor = length - (leftCursor + 1);
            int maximalNumberIndex = rightCursor;
            int maximalNumber = sortedNumbers[maximalNumberIndex];

            for (int cursor = leftCursor; cursor <= rightCursor; cursor++) { int cursorNumber = sortedNumbers[cursor]; if (minimalNumber > cursorNumber) {
                    minimalNumber = cursorNumber;
                    minimalNumberIndex = cursor;
                }
                if (maximalNumber < cursorNumber) {
                    maximalNumber = cursorNumber;
                    maximalNumberIndex = cursor;
                }
            }

            if (leftCursor == maximalNumberIndex) {
                maximalNumberIndex = minimalNumberIndex;
            }

            int fromNumber = sortedNumbers[leftCursor];
            int toNumber = sortedNumbers[minimalNumberIndex];
            sortedNumbers[minimalNumberIndex] = fromNumber;
            sortedNumbers[leftCursor] = toNumber;

            fromNumber = sortedNumbers[rightCursor];
            toNumber = sortedNumbers[maximalNumberIndex];
            sortedNumbers[maximalNumberIndex] = fromNumber;
            sortedNumbers[rightCursor] = toNumber;
        }
        return sortedNumbers;
    }
} 

Ссылки

https://gitlab.com/demensdeum/algorithms/-/tree/master/sortAlgorithms/doubleSelectionSort
https://github.com/pfusik/cito

Источники

https://www.researchgate.net/publication/330084245_Improved_Double_Selection_Sort_using_Algorithm
http://algolab.valemak.com/selection-double
https://www.geeksforgeeks.org/sorting-algorithm-slightly-improves-selection-sort/

Cocktail Shaker Sort

Cocktail Shaker Sort – сортировка в шейкере, вариант двунаправленной сортировки пузырьком.
Алгоритм работает следующим образом:

  1. Выбирается начальное направление перебора в цикле (обычно слева-направо)
  2. Далее в цикле попарно проверяются цифры
  3. Если следующий элемент больше, то они меняются местами
  4. По окончанию, процесс перебора запускается заново с инвертированием направления
  5. Перебор повторяется до тех пор, пока не закончатся перестановки

Временная сложность алгоритма аналогична пузырьковой – O(n2).

Пример реализации на языке PHP:

<?php

function cocktailShakeSort($numbers)
{
    echo implode(",", $numbers),"\n";
    $direction = false;
    $sorted = false;
    do {
        $direction = !$direction;        
        $firstIndex = $direction == true ? 0 : count($numbers) - 1;
        $lastIndex = $direction == true ? count($numbers) - 1 : 0;
        
        $sorted = true;
        for (
            $i = $firstIndex;
            $direction == true ? $i < $lastIndex : $i > $lastIndex;
            $direction == true ? $i++ : $i--
        ) {
            $lhsIndex = $direction ? $i : $i - 1;
            $rhsIndex = $direction ? $i + 1 : $i;

            $lhs = $numbers[$lhsIndex];
            $rhs = $numbers[$rhsIndex];

            if ($lhs > $rhs) {
                $numbers[$lhsIndex] = $rhs;
                $numbers[$rhsIndex] = $lhs;
                $sorted = false;
            }
        }
    } while ($sorted == false);

    echo implode(",", $numbers);
}

$numbers = [2, 1, 4, 3, 69, 35, 55, 7, 7, 2, 6, 203, 9];
cocktailShakeSort($numbers);

?>

Ссылки

https://gitlab.com/demensdeum/algorithms/-/blob/master/sortAlgorithms/cocktailShakerSort/cocktailShakerSort.php

Источники

https://www.youtube.com/watch?v=njClLBoEbfI
https://www.geeksforgeeks.org/cocktail-sort/
https://rosettacode.org/wiki/Sorting_algorithms/Cocktail_sort

Починяем Primus

В этой заметке опишу запуск Steam игр на дистрибутиве Линукса Arch Linux в конфигурации ноутбука Intel + Nvidia

Counter-Strike: Global Offensive

Единственная конфигурация которая у меня заработала – Primus-vk + Vulkan.

Установим нужные пакеты:
pacman -S vulkan-intel lib32-vulkan-intel nvidia-utils lib32-nvidia-utils vulkan-icd-loader lib32-vulkan-icd-loader primus_vk

Далее добавляем параметры запуска для Counter-Strike: Global Offensive:
pvkrun %command% -vulkan -console -fullscreen

Должно работать!

Sid Meier’s Civilization VI

Работает в связке – Primus + OpenGL + LD_PRELOAD.

Установим пакет Primus:
pacman -S primus

Далее добавляем параметры запуска для Sid Meier’s Civilization VI:
LD_PRELOAD='/usr/lib/libfreetype.so.6:/usr/lib/libbrotlicommon.so.1:/usr/lib/libbrotlidec.so.1' primusrun %command%

С помощью LD_PRELOAD подпихиваются библиотеки сжатия и шрифтов Freetype.

Dota 2

Работает в связке – Primus + OpenGL + удаление локов на запуске.

Установим пакет Primus:
pacman -S primus

Далее добавляем параметры запуска для Dota 2:
primusrun %command% -gl -console

Если игра не стартует с ошибкой fcntl(5) for /tmp/source_engine_2808995433.lock failed, то попробуйте удалить файл/tmp/source_engine_2808995433.lock
rm /tmp/source_engine_2808995433.lock
Обычно файл лока остается от прошлой игровой сессии, если игра не была закрыта естественным образом.

Как проверить?

Проще всего проверить запуск приложений на дискретной видеокарте Nvidia через утилиту nvidia-smi:

Для игр на движке Source проверить можно через игровую консоль с помощью команды mat_info:

Источники

https://wiki.archlinux.org/title/Steam/Game-specific_troubleshooting
https://help.steampowered.com/en/faqs/view/145A-FE54-F37B-278A
https://bbs.archlinux.org/viewtopic.php?id=277708