Category Archives: Туториалы

Интересные статьи по разработке

Локальный Vibe-кодинг: LM Studio, VS Code и Continue

Если у вас было желание использовать нейросети для помощи в написании кода (так называемый Vibe-кодинг), и у вас достаточно мощный компьютер, например с видеокартой Nvidia RTX, то вы можете развернуть всю среду абсолютно бесплатно на своей машине. Это решает проблемы с платными подписками и позволяет спокойно работать с проектами под NDA, так как ваш код никуда не отправляется. В этой заметке я опишу, как собрать локальную связку из LM Studio, VS Code и расширения Continue.

Инструменты для локального Vibe-кодинга

Для комфортной работы нам понадобятся три основных компонента:
– LM Studio: удобное приложение для загрузки и запуска локальных LLM. Оно берет на себя всю сложность работы с GGUF-моделями и поднимает локальный сервер, совместимый с API OpenAI.
– VS Code: популярный и привычный редактор кода.
– Continue: расширение для VS Code, которое интегрирует нейросети прямо в рабочую среду. Позволяет общаться в чате, выделять код для рефакторинга и поддерживает автодополнение (autocomplete).

Требования к железу

Локальные языковые модели требовательны к памяти:
– Видеокарта (GPU): Nvidia с 8 ГБ VRAM и выше (для комфортной работы с моделями на 7-8 миллиардов параметров). Для более тяжелых моделей потребуется от 16 ГБ VRAM.
– Место на диске: около 500 ГБ для хранения разных скачанных моделей.

Настройка связки

Процесс настройки достаточно прост и не требует сложных манипуляций в терминале:
1. Скачайте и установите LM Studio. Во встроенном поиске найдите легковесную модель, например Qwen Coder или gemma3:12b.
2. В LM Studio перейдите во вкладку Local Server и нажмите Start Server. По умолчанию он запустится на `http://localhost:1234/v1`.
3. Откройте VS Code и установите расширение Continue из магазина плагинов.
4. Откройте конфигурационный файл Continue и добавьте новую модель, указав провайдера `openai` и адрес вашего локального сервера из LM Studio.

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

Почему это работает?

Как я уже писал ранее, LLM лучше справляются с плоской структурой и WET-кодом (Write Everything Twice). Локальные модели параметров могут уступают гигантам вроде GPT-4 в проектировании сложных архитектур, но для генерации шаблонного кода, рефакторинга простых функций и быстрого прототипирования их возможностей более чем достаточно.

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

Вывод

Локальные нейросети не способны полноценно заменить программиста или спроектировать сложную систему. Тем не менее, связка LM Studio + VS Code + Continue дает независимость от облачных сервисов и сохраняет приватность. Это вполне рабочий вспомогательный инструмент для рутинных задач, если вы готовы мириться с ограничениями небольших моделей и самостоятельно контролировать архитектуру проекта.

Ссылки

https://code.visualstudio.com/
https://lmstudio.ai/
https://continue.dev/

Источники

https://youtu.be/IqqCwhG46jY
https://www.youtube.com/watch?v=7AImkA96mE8

Запуск 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-разработке.

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

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

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

Пример 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-шлемы, а также другие устройства будущего, о которых мы сегодня ещё даже не догадываемся. Гибкость и адаптивность – вот ключи к созданию успешных интерфейсов в современном мире.

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

Включаем подсветку 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

Sleep Sort

Sleep Sort – сортировка сном, еще один представитель детерменированных странных алгоритмов сортировки.

Работает следующим образом:

  1. Проходит циклом по списку элементов
  2. Для каждого цикла запускается отдельный поток
  3. В потоке шедулится сон (sleep) потока на время – значение элемента и вывод значения после сна
  4. По окончанию цикла, ждем ожидания завершения самого долгого сна потока, выводим отсортированный список

Пример кода алгоритма сортировки сном на C:

#include <stdlib.h>
#include <pthread.h>
#include <unistd.h>

typedef struct {
    int number;
} ThreadPayload;

void *sortNumber(void *args) {
    ThreadPayload *payload = (ThreadPayload*) args;
    const int number = payload->number;
    free(payload);
    usleep(number * 1000);
    printf("%d ", number);
    return NULL;
}

int main(int argc, char *argv[]) {
    const int numbers[] = {2, 42, 1, 87, 7, 9, 5, 35};
    const int length = sizeof(numbers) / sizeof(int);

    int maximal = 0;
    pthread_t maximalThreadID;

    printf("Sorting: ");
    for (int i = 0; i < length; i++) { pthread_t threadID; int number = numbers[i]; printf("%d ", number); ThreadPayload *payload = malloc(sizeof(ThreadPayload)); payload->number = number;
        pthread_create(&threadID, NULL, sortNumber, (void *) payload);
        if (maximal < number) {
            maximal = number;
            maximalThreadID = threadID;
        }
    }
    printf("\n");
    printf("Sorted: ");
    pthread_join(maximalThreadID, NULL);
    printf("\n");
    return 0;
}

В этой реализации я использовал функцию usleep на микросекундах с умножением значения на 1000, т.е. на миллисекундах.
Временная сложность алгоритма – O(оч. долго)

Ссылки

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

Источники

https://codoholicconfessions.wordpress.com/2017/05/21/strangest-sorting-algorithms/
https://twitter.com/javascriptdaily/status/856267407106682880?lang=en
https://stackoverflow.com/questions/6474318/what-is-the-time-complexity-of-the-sleep-sort

Stalin Sort

Stalin Sort – сортировка навылет, один из алгоритмов сортировки с потерей данных.
Алгоритм очень производительный и эффективный, временная сложность O(n).

Работает следующим образом:

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

Пример вывода работы алгоритма:

Gulag: [1, 3, 2, 4, 6, 42, 4, 8, 5, 0, 35, 10]
Element 2 sent to Gulag
Element 4 sent to Gulag
Element 8 sent to Gulag
Element 5 sent to Gulag
Element 0 sent to Gulag
Element 35 sent to Gulag
Element 10 sent to Gulag
Numbers: [1, 3, 4, 6, 42]
Gulag: [2, 4, 8, 5, 0, 35, 10]

Код на Питоне 3:

gulag = []

print(f"Numbers: {numbers}")
print(f"Gulag: {numbers}")

i = 0
maximal = numbers[0]

while i < len(numbers):
    element = numbers[i]
    if maximal > element:
        print(f"Element {element} sent to Gulag")
        gulag.append(element)
        del numbers[i]
    else:
        maximal = element        
        i += 1

print(f"Numbers: {numbers}")
print(f"Gulag: {gulag}")

Из недостатков можно отметить потерю данных, но если двигаться к утопичному, идеальному, отсортированному списку за O(n), то как иначе?

Ссылки

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

Источники

https://github.com/gustavo-depaula/stalin-sort
https://www.youtube.com/shorts/juRL-Xn-E00
https://www.youtube.com/watch?v=L78i2YcyYfk

Selection Sort

Selection Sort – алгоритм сортировки выбором. Выбором чего? А вот минимального числа!!!
Временная сложность алгоритма – О(n2)

Алгоритм работает следующим образом:

  1. Проходим массив циклом слева-направо, запоминаем текущий стартовый индекс и число по индексу, назовем числом A
  2. Внутри цикла запускаем еще один для прохода слева-направо в поисках меньшего чем A
  3. Когда находим меньший, запоминаем индекс, теперь меньший становится числом А
  4. Когда внутренний цикл заканчивается, меняем местами число по стартовому индексу и число А
  5. После полного прохода верхнего цикла, получаем отсортированный массив

Пример выполнения алгоритма:

(29, 49, 66, 35, 7, 12, 80)
29 > 7
(7, 49, 66, 35, 29, 12, 80)
Round 1 ENDED
Round 2
(7, 49, 66, 35, 29, 12, 80)
49 > 35
35 > 29
29 > 12
(7, 12, 66, 35, 29, 49, 80)
Round 2 ENDED
Round 3
(7, 12, 66, 35, 29, 49, 80)
66 > 35
35 > 29
(7, 12, 29, 35, 66, 49, 80)
Round 3 ENDED
Round 4
(7, 12, 29, 35, 66, 49, 80)
(7, 12, 29, 35, 66, 49, 80)
Round 4 ENDED
Round 5
(7, 12, 29, 35, 66, 49, 80)
66 > 49
(7, 12, 29, 35, 49, 66, 80)
Round 5 ENDED
Round 6
(7, 12, 29, 35, 49, 66, 80)
(7, 12, 29, 35, 49, 66, 80)
Round 6 ENDED
Sorted: (7, 12, 29, 35, 49, 66, 80)

Не найдя Objective-C реализации на Rosetta Code, написал его сам:

#include <Foundation/Foundation.h>

@implementation SelectionSort
- (void)performSort:(NSMutableArray *)numbers
{
   NSLog(@"%@", numbers);   
   for (int startIndex = 0; startIndex < numbers.count-1; startIndex++) {
      int minimalNumberIndex = startIndex;
      for (int i = startIndex + 1; i < numbers.count; i++) {
         id lhs = [numbers objectAtIndex: minimalNumberIndex];
         id rhs = [numbers objectAtIndex: i];
         if ([lhs isGreaterThan: rhs]) {
            minimalNumberIndex = i;
         }
      }
      id temporary = [numbers objectAtIndex: minimalNumberIndex];
      [numbers setObject: [numbers objectAtIndex: startIndex] 
               atIndexedSubscript: minimalNumberIndex];
      [numbers setObject: temporary
               atIndexedSubscript: startIndex];
   }
   NSLog(@"%@", numbers);
}

@end

Собрать и запустить можно либо на MacOS/Xcode, либо на любой операционной системе поддерживающей GNUstep, например у меня собирается Clang на Arch Linux.
Скрипт сборки:

        main.m \
        -lobjc \
        `gnustep-config --objc-flags` \
        `gnustep-config --objc-libs` \
        -I /usr/include/GNUstepBase \
        -I /usr/lib/gcc/x86_64-pc-linux-gnu/12.1.0/include/ \
        -lgnustep-base \
        -o SelectionSort \

Links

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

Sources

https://rosettacode.org/wiki/Sorting_algorithms/Selection_sort
https://ru.wikipedia.org/wiki/Сортировка_выбором
https://en.wikipedia.org/wiki/Selection_sort
https://www.youtube.com/watch?v=LJ7GYbX7qpM

Counting Sort

Counting sort – алгоритм сортировки подсчетом. Всмысле? Да! Прям так!

В алгоритме участвуют минимум два массива, первый – список целых чисел которые надо отсортировать, второй – массив размером = (максимальное число – минимальное число) + 1, изначально содержащий одни нули. Далее перебираются цифры из первого массива, по элементу-числу получается индекс во втором массиве, который инкрементируют на единицу. После прохода по всему списку у нас получится полностью заполненный второй массив с количеством повторений чисел из первого. У алгоритма есть серьезная издержка – второй массив также содержит нули для чисел которых в первом списке нет, т.н. оверхед по памяти.

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

Пример неоптимизированной работы алгоритма сортировки подсчетом:

  1. Входой массив 1,9,1,4,6,4,4
  2. Тогда массив для подсчета будет 0,1,2,3,4,5,6,7,8,9 (минимальное число 0, максимальное 9)
  3. С итоговыми счетчиками 0,2,0,0,3,0,1,0,0,1
  4. Итого отсортированный массив 1,1,4,4,4,6,9

Код алгоритма на языке Python 3:


numbers = [42, 89, 69, 777, 22, 35, 42, 69, 42, 90, 777]

minimal = min(numbers)
maximal = max(numbers)
countListRange = maximal - minimal
countListRange += 1
countList = [0] * countListRange

print(numbers)
print(f"Minimal number: {minimal}")
print(f"Maximal number: {maximal}")
print(f"Count list size: {countListRange}")

for number in numbers:
    index = number - minimal
    countList[index] += 1

replacingIndex = 0
for index, count in enumerate(countList):
    for i in range(count):
        outputNumber = minimal + index
        numbers[replacingIndex] = outputNumber
        replacingIndex += 1

print(numbers)

Из-за использования двух массивов, временная сложность алгоритма O(n + k)

Ссылки

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

Источники

https://www.youtube.com/watch?v=6dk_csyWif0
https://www.youtube.com/watch?v=OKd534EWcdk
https://en.wikipedia.org/wiki/Counting_sort
https://rosettacode.org/wiki/Sorting_algorithms/Counting_sort
https://pro-prof.com/forums/topic/%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC-%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B8-%D0%BF%D0%BE%D0%B4%D1%81%D1%87%D0%B5%D1%82%D0%BE%D0%BC

Bogosort

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

Работает он так:
1. На вход подается массив из чисел
2. Массив из чисел перемешивается случайным образом (shuffle)
3. Проверяется отсортирован ли массив
4. Если не отсортирован, то массив перемешивается заново
5. Все это действо повторяется до тех пор, пока массив не отсортируется случайным образом.

Как можно увидеть – производительность этого алгоритма ужасна, умные люди считают что даже O(n * n!) т.е. есть шанс завязнуть кидая кубики во славу бога хаоса очень много лет, массив так и не отсортируется, а может отсортируется?

Реализация

Для реализации на TypeScript мне понадобилось реализовать следующие функции:
1. Перемешивание массива объектов
2. Сравнение массивов
3. Генерация случайного числа в диапазоне от нуля до числа (sic!)
4. Печать прогресса, т.к. кажется что сортировка выполняется бесконечно

Ниже код реализации на TypeScript:

const randomInteger = (maximal: number) => Math.floor(Math.random() * maximal);
const isEqual = (lhs: any[], rhs: any[]) => lhs.every((val, index) => val === rhs[index]);
const shuffle = (array: any[]) => {
    for (var i = 0; i < array.length; i++) { var destination = randomInteger(array.length-1); var temp = array[i]; array[i] = array[destination]; array[destination] = temp; } } let numbers: number[] = Array.from({length: 10}, ()=>randomInteger(10));
const originalNumbers = [...numbers];
const sortedNumbers = [...numbers].sort();

let numberOfRuns = 1;

do {
    if (numberOfRuns % 1000 == 0) {
        printoutProcess(originalNumbers, numbers, numberOfRuns);
    }
    shuffle(numbers);
    numberOfRuns++;
} while (isEqual(numbers, sortedNumbers) == false)

console.log(`Success!`);
console.log(`Run number: ${numberOfRuns}`)
console.log(`Original numbers: ${originalNumbers}`);
console.log(`Current numbers: ${originalNumbers}`);
console.log(`Sorted numbers: ${sortedNumbers}`);

Для отладки можно использовать VSCode и плагин TypeScript Debugger от kakumei.

Как долго

Вывод работы алгоритма:

src/bogosort.ts:1
Still trying to sort: 5,4,8,7,5,0,2,9,7,2, current shuffle 8,7,0,2,4,7,2,5,9,5, try number: 145000
src/bogosort.ts:2
Still trying to sort: 5,4,8,7,5,0,2,9,7,2, current shuffle 7,5,2,4,9,8,0,5,2,7, try number: 146000
src/bogosort.ts:2
Still trying to sort: 5,4,8,7,5,0,2,9,7,2, current shuffle 0,2,7,4,9,5,7,5,8,2, try number: 147000
src/bogosort.ts:2
Still trying to sort: 5,4,8,7,5,0,2,9,7,2, current shuffle 5,9,7,8,5,4,2,7,0,2, try number: 148000
src/bogosort.ts:2
Success!
src/bogosort.ts:24
Run number: 148798
src/bogosort.ts:25
Original numbers: 5,4,8,7,5,0,2,9,7,2
src/bogosort.ts:26
Current numbers: 5,4,8,7,5,0,2,9,7,2
src/bogosort.ts:27
Sorted numbers: 0,2,2,4,5,5,7,7,8,9

Для массива из 10 чисел Богосорт перемешивал исходный массив 148798 раз, многовато да?
Алгоритм можно использовать как учебный, для понимания возможностей языка с которым предстоит работать на рынке. Лично я был удивлен узнав что в ванильных JS и TS до сих пор нет своего алгоритма перемешивания массивов, генерации целого числа в диапазоне, доступа к хэшам объектов для быстрого сравнения.

Ссылки

https://gitlab.com/demensdeum/algorithms/-/tree/master/sortAlgorithms/bogosort
https://www.typescriptlang.org/
https://marketplace.visualstudio.com/items?itemName=kakumei.ts-debug

Источники

https://www.youtube.com/watch?v=r2N3scbd_jg
https://en.wikipedia.org/wiki/Bogosort

Паттерны GoF

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

Порождающие паттерны

Структурные паттерны

Паттерны поведения

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

Что входит

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

  • Терминальное выражение – например константа строки – “Hello World”
  • Нетерминальное выражение – например Print(“Hello World”), содержит Print и аргумент из Терминального выражения “Hello World”

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

Пример AST древа ниже:


Dcoetzee, CC0, via Wikimedia Commons

Как можно увидеть, терминальные выражения – constant и variable, нетерминальные – остальные.

Что не входит

В реализацию Интерпретатора не входит парсинг строкового ввода языка в AST-древо. Достаточно реализовать классы терминальных, нетерминальных выражений, методы Interpret с аргументом Контекст на входе, оформить AST древо из выражений, запустить у корневого выражения метод Interpret. Контекст можно использовать для того чтобы хранить состояние приложения во время выполнения.

Реализация

В паттерне участвуют:

  • Клиент – отдает AST-древо и запускает Interpret(context) для корневой вершины (Client)
  • Контекст – содержит состояние приложения, передается выражениям при интерпретации (Context)
  • Абстрактное выражение – абстрактный класс содержащий метод Interpret(context) (Expression)
  • Терминальное выражение – конечное выражение, потомок абстрактного выражения (TerminalExpression)
  • Нетерминальное выражение – не конечное выражение, содержит указатели на вершины вглубь AST-древа, подчиненные вершины обычно влияют на результат интерпретации нетерминального выражения (NonTerminalExpression)

Пример Клиента на C#

        static void Main(string[] args)
        {
            var context = new Context();
            var initialProgram = new PerformExpression(
                new IExpression[] {
                    new SetExpression("alpha", "1"),
                    new GetExpression("alpha"),
                    new PrintExpression(
                        new IExpression[] {
                            new ConstantExpression("Hello Interpreter Pattern")
                        }
                    )
                }
            );
            System.Console.WriteLine(initialProgram.interpret(context));
        }
}

Пример Абстрактного выражения на C#

{
    String interpret(Context context);
}

Пример Терминального выражения на C# (Строковая константа)

{
    private String constant;

    public ConstantExpression(String constant) {
        this.constant = constant;
    }

    override public String interpret(Context context) {
        return constant;
    }
}

Пример Нетерминального выражения на C# (Запуск и конкатенация результатов подчиненных вершин, с использованием разделителя «;»

{
    public PerformExpression(IExpression[] leafs) : base(leafs) {
        this.leafs = leafs;
    }
    
    override public String interpret(Context context) {
        var output = "";
        foreach (var leaf in leafs) {
            output += leaf.interpret(context) + ";";
        }
        return output;
    }
}

Функционально сможешь?

Как известно все Тьюринг-полные языки эквивалентны. Можно ли перенести Объектно-Ориентированный паттерн на язык Функционального программирования?

Можно, для эксперимента возьмем ФП язык для веба под названием Elm. В Elm нет классов, но есть Записи (Records) и Типы (Types) поэтому в реализации участвуют следующие записи и типы:

  • Выражение – перечисление всех возможных выражений языка (Expression)
  • Подчиненное выражение – выражение являющееся подчиненным по отношению к Нетерминальному выражению (ExpressionLeaf)
  • Контекст – запись хранящая состояние приложения (Context)
  • Функции реализующие методы Interpret(context) – все необходимые функции реализующие функционал Терминальных, Нетерминальных выражений
  • Вспомогательные записи состояния Интерпретатора – необходимы для корректной работы Интерпретатора, хранят состояние Интерпретатора, контекст

Пример функции реализующей интерпретацию для всего набора возможных выражений на Elm:

  case input.expression of
    Constant text ->
      { 
        output = text, 
        context = input.context 
      }
    Perform leafs ->
      let inputs = List.map (\leaf -> { expressionLeaf = leaf, context = input.context } ) leafs in
        let startLeaf = { expressionLeaf = (Node (Constant "")), context = { variables = Dict.empty } } in
          let outputExpressionInput = List.foldl mergeContextsAndRunLeafs startLeaf inputs in
            {
              output = (runExpressionLeaf outputExpressionInput).output,
              context = input.context
            }
    Print printExpression ->
      run 
      { 
        expression = printExpression, 
        context = input.context 
      }
    Set key value ->
      let variables = Dict.insert key value input.context.variables in
      {
        output = "OK",
        context = { variables = variables }
      }
    Get key ->
      {
        output = Maybe.withDefault ("No value for key: " ++ key) (Dict.get key input.context.variables),
        context = input.context
      }

А парсить?

Парсинг исходного кода в AST-древо не входит в паттерн Интерпретатор, существует несколько подходов для парсинга исходного кода, но об этом как-нибудь в другой раз.
В реализации Интерпретатора для Elm я написал простейший парсер в AST-древо, состоящий из двух функций – парсинг вершины, парсинг подчиненных вершин.

parseLeafs state =
    let tokensQueue = state.tokensQueue in
        let popped = pop state.tokensQueue in
            let tokensQueueTail = tail state.tokensQueue in
                if popped == "Nothing" then
                    state
                else if popped == "Perform(" then
                    {
                        tokensQueue = tokensQueue,
                        result = (state.result ++ [Node (parse tokensQueue)])
                    }
                else if popped == ")" then
                    parseLeafs {
                        tokensQueue = tokensQueueTail,
                        result = state.result
                    }
                else if popped == "Set" then
                    let key = pop tokensQueueTail in
                        let value = pop (tail tokensQueueTail) in
                            parseLeafs {
                                tokensQueue = tail (tail tokensQueueTail),
                                result = (state.result ++ [Node (Set key value)])
                            }
                else if popped == "Get" then
                    let key = pop tokensQueueTail in
                        parseLeafs {
                            tokensQueue = tail tokensQueueTail,
                            result = (state.result ++ [Node (Get key)])
                        }
                else 
                    parseLeafs {
                        tokensQueue = tokensQueueTail,
                        result = (state.result ++ [Node (Constant popped)])
                    }

parse tokensQueue =
    let popped = pop tokensQueue in
        let tokensQueueTail = tail tokensQueue in
            if popped == "Perform(" then
                Perform (
                    parseLeafs {
                        tokensQueue = tokensQueueTail, 
                        result = []
                    }
                ).result
            else if popped == "Set" then
                let key = pop tokensQueueTail in
                    let value = pop (tail tokensQueueTail) in
                        Set key value
            else if popped == "Print" then
                Print (parse tokensQueueTail)
            else
                Constant popped

Ссылки

https://gitlab.com/demensdeum/patterns/-/tree/master/interpreter/elm
https://gitlab.com/demensdeum/patterns/-/tree/master/interpreter/csharp

Источники

https://en.wikipedia.org/wiki/Interpreter_pattern
https://elm-lang.org/
https://docs.microsoft.com/en-us/dotnet/csharp/

RGB изображение в серое

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

red = average;
green = average;
blue = average;

Складываем 3 цветовых канала и делим на 3.

Однако существует еще один метод – метод средневзвешенный, он учитывает цветовосприятие человека:

red = luminance;
green = luminance;
blue = luminance;

Какой метод лучше использовать? Да какой вам больше подходит для конкретной задачи. Далее сравнение методов с помощью тестовой цветовой сетки:

Пример реализации на JavaScript + HTML 5

    image,
    canvas,
    weightedAverage
) {
    const context = canvas.getContext('2d');

    const imageWeight = image.width;
    const imageHeight = image.height;

    canvas.width = imageWeight;
    canvas.height = imageHeight;

    context.drawImage(image, 0, 0);

    let pixels = context
        .getImageData(
            0,
            0,
            imageWeight,
            imageHeight
        );

    for (let y = 0; y & lt; pixels.height; y++) {
        for (let x = 0; x & lt; pixels.width; x++) {
            const i = (y * 4) * pixels.width + x * 4;

            let red = pixels.data[i];
            let green = pixels.data[i + 1];
            let blue = pixels.data[i + 2]

            const average = (red + green + blue) / 3;
            const luminance = 0.2126 * red +
                0.7152 * green +
                0.0722 * blue;

            red = weightedAverage ? luminance : average;
            green = weightedAverage ? luminance : average;
            blue = weightedAverage ? luminance : average;

            pixels.data[i] = red;
            pixels.data[i + 1] = green;
            pixels.data[i + 2] = blue;
        }
    }
    context
        .putImageData(
            pixels,
            0,
            0,
            0,
            0,
            pixels.width,
            pixels.height
        );
}

Источники

https://www.baeldung.com/cs/convert-rgb-to-grayscale
https://twitter.com/mudasobwa/status/1528046455587495940
https://rosettacode.org/wiki/Grayscale_image

Ссылки

http://papugi.demensdeum.repl.co/

Благодарности

Спасибо Aleksei Matiushkin (https://twitter.com/mudasobwa) за наводку на Rosetta Code

Как запустить CSGO на Macbook M1

Если у вас вылезает ошибка SDL_GetDesktopDisplayMode_REAL на Macbook M1 при запуске CSGO, то делайте как написано дальше.
1. Добавьте параметры запуска в Steam для CSGO:
-w 1440 -h 900 -fullscreen
2. Запустите CSGO через Steam
3. Нажмите Игнорировать или Всегда игорировать на ошибке SDL_GetDesktopDisplayMode_REAL
4. Наслаждайтесь