Почему важен DRY

Существует множество статей на тему DRY, я рекомендую прочитать первоисточник “Программист-прагматик” за авторством Andy Hunt и Dave Thomas. Однако я всё равно вижу как у множества разработчиков вызывает вопросы данный принцип в разработке программного обеспечения.

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

class Client {
    public let name: String
    private var messages: [String] = []
    
    init(name: String) {
        self.name = name
    }
    
    func receive(_ message: String) {
        messages.append(message)
    }
}

class ClientController {
    func greet(client: Client?) {
        guard let client else {
            debugPrint("No client!")
            return
        }
        client.receive("Hello \(client.name)!")
    }

    func goodbye(client: Client?) {
        guard let client else {
            debugPrint("No client!!")
            return
        }
        client.receive("Bye \(client.name)!")
    }
}

Как можно увидеть в методе greet и goodbye передается опциональный инстанс класса Client, который затем нужно проверять на nil, после чего начинать работу с ним. Чтобы соблюсти метод DRY, нужно убрать повторяющуюся проверку на nil для инстанса класса. Реализовать это можно множеством путей, один из вариантов это передавать инстанс в конструктор класса, после чего необходимость в проверках отпадет.

Соблюдаем DRY с помощью специализации ClientController на единственном инстансе Client:

class Client {
    public let name: String
    private var messages: [String] = []
    
    init(name: String) {
        self.name = name
    }
    
    func receive(_ message: String) {
        messages.append(message)
    }
}

class ClientController {
    private let client: Client

    init(client: Client) {
        self.client = client
    }

    func greet() {
        client.receive("Hello \(client.name)!")
    }

    func goodbye() {
        client.receive("Bye \(client.name)!")
    }
}

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

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

У Стива Джобса было выражение “Строка кода, которую не пришлось писать, — это строка кода, которую вам никогда не придется дебажить.”

Источники

https://pragprog.com/titles/tpp20/the-pragmatic-programmer-20th-anniversary-edition/
https://youtu.be/-msIEOGvTYM

Я помогу вам в разработке iOS для Swift или Objective-С

Рад сообщить, что теперь я предлагаю свои услуги как iOS-разработчик на Fiverr. Если вам нужна помощь в разработке качественных iOS-приложений или улучшении существующих проектов, ознакомьтесь с моим профилем:
https://www.fiverr.com/s/Q7x4kb6

Буду рад возможности поработать над вашим проектом.
Email: demensdeum@gmail.com
Telegram: https://t.me/demensdeum

Динамическая линковка Qt приложений на macOS

Сегодня я выпустил версию RaidenVideoRipper для устройств Apple с macOS и процессоров M1/M2/M3/M4 (Apple Silicon). RaidenVideoRipper это приложение для быстрого монтажа видео, которое позволяет вырезать часть видеофайла в новый файл. Также можно делать gif, экспортировать звуковую дорожку в mp3.

Далее я коротко опишу какие команды я использовал для того чтобы это осуществить. Теорию того что здесь происходит, документацию утилит, можно прочитать по следующим ссылкам:
https://www.unix.com/man-page/osx/1/otool/
https://www.unix.com/man-page/osx/1/install_name_tool/
https://llvm.org/docs/CommandGuide/llvm-nm.html
https://linux.die.net/man/1/file
https://www.unix.com/man-page/osx/8/SPCTL/
https://linux.die.net/man/1/chmod
https://linux.die.net/man/1/ls
https://man7.org/linux/man-pages/man7/xattr.7.html
https://doc.qt.io/qt-6/macos-deployment.html

Для начала установите Qt на свою macOS, также установите окружение для Qt Desktop Development. После этого соберите свой проект например в Qt Creator, далее я опишу что нужно для того чтобы зависимости с внешними динамическими библиотеками корректно отрабатывали при дистрибутизации приложения конечным пользователям.

Создайте в папке YOUR_APP.app/Contents вашего приложения директорию Frameworks, сложите в нее внешние зависимости. Для примера так выглядит Frameworks для приложения RaidenVideoRipper:

Frameworks
├── DullahanFFmpeg.framework
│   ├── dullahan_ffmpeg.a
│   ├── libavcodec.60.dylib
│   ├── libavdevice.60.dylib
│   ├── libavfilter.9.dylib
│   ├── libavformat.60.dylib
│   ├── libavutil.58.dylib
│   ├── libpostproc.57.dylib
│   ├── libswresample.4.dylib
│   └── libswscale.7.dylib
├── QtCore.framework
│   ├── Headers -> Versions/Current/Headers
│   ├── QtCore -> Versions/Current/QtCore
│   ├── Resources -> Versions/Current/Resources
│   └── Versions
├── QtGui.framework
│   ├── Headers -> Versions/Current/Headers
│   ├── QtGui -> Versions/Current/QtGui
│   ├── Resources -> Versions/Current/Resources
│   └── Versions
├── QtMultimedia.framework
│   ├── Headers -> Versions/Current/Headers
│   ├── QtMultimedia -> Versions/Current/QtMultimedia
│   ├── Resources -> Versions/Current/Resources
│   └── Versions
├── QtMultimediaWidgets.framework
│   ├── Headers -> Versions/Current/Headers
│   ├── QtMultimediaWidgets -> Versions/Current/QtMultimediaWidgets
│   ├── Resources -> Versions/Current/Resources
│   └── Versions
├── QtNetwork.framework
│   ├── Headers -> Versions/Current/Headers
│   ├── QtNetwork -> Versions/Current/QtNetwork
│   ├── Resources -> Versions/Current/Resources
│   └── Versions
└── QtWidgets.framework
    ├── Headers -> Versions/Current/Headers
    ├── QtWidgets -> Versions/Current/QtWidgets
    ├── Resources -> Versions/Current/Resources
    └── Versions

Для упрощения я распечатал только второй уровень вложенности.

Далее печатаем текущие динамические зависимости вашего приложения:

otool -L RaidenVideoRipper 

Вывод для бинарика RaidenVideoRipper, который лежит в RaidenVideoRipper.app/Contents/MacOS:

RaidenVideoRipper:
	@rpath/DullahanFFmpeg.framework/dullahan_ffmpeg.a (compatibility version 0.0.0, current version 0.0.0)
	@rpath/QtMultimediaWidgets.framework/Versions/A/QtMultimediaWidgets (compatibility version 6.0.0, current version 6.8.1)
	@rpath/QtWidgets.framework/Versions/A/QtWidgets (compatibility version 6.0.0, current version 6.8.1)
	@rpath/QtMultimedia.framework/Versions/A/QtMultimedia (compatibility version 6.0.0, current version 6.8.1)
	@rpath/QtGui.framework/Versions/A/QtGui (compatibility version 6.0.0, current version 6.8.1)
	/System/Library/Frameworks/AppKit.framework/Versions/C/AppKit (compatibility version 45.0.0, current version 2575.20.19)
	/System/Library/Frameworks/ImageIO.framework/Versions/A/ImageIO (compatibility version 1.0.0, current version 1.0.0)
	/System/Library/Frameworks/Metal.framework/Versions/A/Metal (compatibility version 1.0.0, current version 367.4.0)
	@rpath/QtNetwork.framework/Versions/A/QtNetwork (compatibility version 6.0.0, current version 6.8.1)
	@rpath/QtCore.framework/Versions/A/QtCore (compatibility version 6.0.0, current version 6.8.1)
	/System/Library/Frameworks/IOKit.framework/Versions/A/IOKit (compatibility version 1.0.0, current version 275.0.0)
	/System/Library/Frameworks/DiskArbitration.framework/Versions/A/DiskArbitration (compatibility version 1.0.0, current version 1.0.0)
	/System/Library/Frameworks/UniformTypeIdentifiers.framework/Versions/A/UniformTypeIdentifiers (compatibility version 1.0.0, current version 709.0.0)
	/System/Library/Frameworks/AGL.framework/Versions/A/AGL (compatibility version 1.0.0, current version 1.0.0)
	/System/Library/Frameworks/OpenGL.framework/Versions/A/OpenGL (compatibility version 1.0.0, current version 1.0.0)
	/usr/lib/libc++.1.dylib (compatibility version 1.0.0, current version 1800.101.0)
	/usr/lib/libSystem.B.dylib (compatibility version 1.0.0, current version 1351.0.0)

Как можно увидеть у RaidenVideoRipper в зависимостях Qt и dullahan_ffmpeg. Dullahan FFmpeg это форк FFmpeg который инкапсулирует его функционал в динамическую библиотеку, с возможностью получения текущего прогресса выполнения и отмены, с помощью Си процедур.
Далее заменяйте у приложения и всех необходимых библиотек пути с помощью install_name_tool.

Команда для этого такая:

install_name_tool -change old_path new_path target

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

install_name_tool -change /usr/local/lib/libavfilter.9.dylib @rpath/DullahanFFmpeg.framework/libavfilter.9.dylib dullahan_ffmpeg.a

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

Также бывает ошибка с путаницей зависимостей, когда у замененной вами библиотеки отсутствует символ в таблице, проверить наличие или отсутствие символа можно так:

nm -gU path

После выполнения вы увидите всю символьную таблицу библиотеки или приложения.
Также возможно что вы скопируете зависимости не той архитектуры, проверить это можно с помощью file:

file path

Утилита file покажет вам к какой архитектуре принадлежит библиотека или приложение.

Также Qt требует наличия папки Plugins в папке Contents вашей директории YOUR_APP.app, скопируйте плагины из Qt в Contents. Далее проверьте работоспособность приложения, после этого можете приступать к оптимизации папки Plugins, удаляя элементы из этой папки и тестируя приложение.

Безопасность macOS

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

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

Эта инструкция работает также и для RaidenVideoRipper:

  • Отключение Gatekeeper: spctl –master-disable
  • Разрешить запуск из любых источников в Privacy & Security: Allow applications переключить на Anywhere
  • Удалить флаг карантина после скачивания с zip или dmg приложения: xattr -d com.apple.quarantine app.dmg
  • Проверите что флаг карантина (com.apple.quarantine) отсутствует: ls -l@ app.dmg
  • Дополните подтвердите запуск приложения если необходимо в Privacy & Security

Ошибка с флагом карантина обычно воспроизводится тем что на экране пользователя появляется ошибка “Приложение повреждено”. В этом случае надо убрать флаг карантина из метаданных.

Ссылка на сборку RaidenVideoRipper для Apple Silicon:
https://github.com/demensdeum/RaidenVideoRipper/releases/download/1.0.1.0/RaidenVideoRipper-1.0.1.0.dmg

Стабилизация видео с помощью ffmpeg

Если вы хотите стабилизировать видео и убрать дрожание камеры, инструмент `ffmpeg` предлагает мощное решение. Благодаря встроенным фильтрам `vidstabdetect` и `vidstabtransform`, можно добиться профессионального результата без использования сложных видеоредакторов.

Подготовка к работе

Прежде чем начать, убедитесь, что ваш `ffmpeg` поддерживает библиотеку `vidstab`. В Linux это можно проверить командой:

bash  
ffmpeg -filters | grep vidstab  

Если библиотека не установлена, её можно добавить:

sudo apt install ffmpeg libvidstab-dev  

Установка для macOS через brew:

brew install libvidstab
brew install ffmpeg

Теперь перейдём к процессу.

Шаг 1: Анализ движения

Сначала нужно провести анализ движения видео и создать файл с параметрами стабилизации.

ffmpeg -i input.mp4 -vf vidstabdetect=shakiness=10:accuracy=15 transfile=transforms.trf -f null -  

Параметры:

shakiness: Уровень дрожания видео (по умолчанию 5, можно увеличить до 10 для более сложных случаев).
accuracy: Точность анализа (по умолчанию 15).
transfile: Имя файла для сохранения параметров движения.

Шаг 2: Применение стабилизации

Теперь можно применить стабилизацию, используя файл трансформаций:

ffmpeg -i input.mp4 -vf vidstabtransform=input=transforms.trf:zoom=5 output.mp4

Параметры:

input: Указывает на файл с параметрами трансформации (созданный на первом шаге).
zoom: Коэффициент масштабирования для устранения черных краев (например, 5 — автоматическое увеличение до устранения артефактов).

Автоматический анализ кода с помощью Bistr

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

Что такое Bistr?

Bistr — это утилита для анализа исходного кода, которая позволяет интегрировать локальную LLM (large language model) модель, такую как Ollama, для анализа и обработки кода. С помощью Bistr вы можете анализировать файлы на различных языках программирования, например, Python, C, Java, JavaScript, HTML и других.

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

Как работает Bistr?

  • Загрузка состояния: Когда вы начинаете анализ, утилита проверяет, было ли ранее сохранено состояние анализа. Это помогает продолжить с того места, где вы остановились, без необходимости повторного анализа тех же файлов.
  • Анализ кода: Каждый файл анализируется с использованием модели Ollama. Утилита отправляет запрос к модели для анализа конкретного фрагмента кода. Модель возвращает информацию о релевантности кода в ответ на запрос, а также предоставляет текстовое объяснение, почему данный фрагмент имеет отношение к задаче.
  • Сохранение состояния: После анализа каждого файла состояние обновляется, чтобы в следующий раз продолжить с актуальной информацией.
  • Вывод результатов: Все результаты анализа можно экспортировать в HTML-файл, который содержит таблицу с рейтингом файлов по релевантности, что помогает понять, какие части кода наиболее важны для дальнейшего анализа.

Установка и запуск

Для использования Bistr необходимо установить и запустить Ollama — платформу, которая предоставляет LLM модели на вашей локальной машине. Инструкция по установке Ollama для macOS, Windows и Linux описана ниже.

Загрузите последнюю версию Bistr из git:
https://github.com/demensdeum/Bistr/

После установки Ollama и Bistr можно запускать анализ кода. Для этого нужно подготовить исходный код и указать путь к директории, содержащей файлы для анализа. Утилита позволяет продолжить анализ с того места, где вы остановились, а также предоставляет возможность экспортировать результаты в HTML-формате для удобства дальнейшего анализа.

Пример команды для запуска анализа:


python bistr.py /path/to/code --model llama3.1:latest --output-html result.html --research "What is the purpose of this function?"

В этой команде:

–model указывает модель, которая будет использоваться для анализа.
–output-html задает путь для сохранения результатов анализа в HTML-файле.
–research позволяет задать вопрос, на который вы хотите получить ответ, анализируя код.

Преимущества использования Bistr

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

Локальные нейросети с помощью ollama

Если у вас было желание запустить подобие ChatGPT и у вас достаточно мощный компьютер, например с видеокартой Nvidia RTX, то тогда вы можете запустить проект ollama, который позволит использовать одну из готовых LLM моделей, на локальный машине, абсолютно бесплатно. ollama обеспечивает возможность общения с LLM моделями, на манер ChatGPT, также в последней версии объявлена возможность прочтения изображений, форматирование выходных данных в формат json.

Сам проект я запускал также и на макбуке с процессором Apple M2, и мне известно что поддерживаются последние модели видеокарт от AMD.

Для установки на macOS зайдите на сайт ollama:
https://ollama.com/download/mac

Нажмите “Download for macOS”, у вас загрузится архив вида ollama-darwin.zip, внутри архива будет Ollama.app который нужно скопировать в “Applications”. После этого запускайте Ollama.app, скорее всего при первом запуске произойдет процесс установки. После этого в трее вы увиделе иконку ollama, трэй это справа сверху рядом с часами.

После этого запускайте обычный терминал macOS, и набирайте команду загрузки, установки и запуска любой модели ollama. Список доступных моделей, описания, их характеристик можно увидеть на сайте ollama:
https://ollama.com/search

Выбирайте модель с наименьшим количеством параметров, если она не влезает в вашу видеокарту на запуске.

Для примера командв запуск модели llama3.1:latest:


ollama run llama3.1:latest

Установка для Windows и Linux в целом похожа, в одном случае будет установщик ollama и дальнейшая работа с ней через Powershell.
Для Linux установка производится скриптом, однако я рекомендую использовать версию конкретно вашего пакетного менеджера. В Linux ollama запустить также можно через обычный терминал bash.

Источники
https://www.youtube.com/watch?v=Wjrdr0NU4Sk
https://ollama.com

Unreal Engine на Macbook M2

Если вы смогли запустить Unreal Engine 5 Editor на Macbook с процессором Apple, то вы могли заметить что эта штука достаточо сильно тормозит.

Чтобы увеличить производительность редактора и движка, проставьте Engine Scalability Settings -> Medium. После этого движок начнет рисовать все не так красиво, зато вы сможете нормально поработать с движком на своем макбуке.

Исправление мобильного меню в WordPress


document.addEventListener('DOMContentLoaded', function() {
    new navMenu('primary');
    new navMenu('woo');
});

Если у вас тоже несколько лет не открывалось меню блога на iOS/Android в вашем блоге на WordPress, при использовании темы Seedlet, то просто добавьте:
В функцию замыкание файла wp-content/themes/seedlet/assets/js/primary-navigation.js, рядом с дефолтной подпиской window addEventListener ‘load’.

Radio-Maximum-Electron

Радио Максимум Electron — это мощное и удобное приложение, предназначенное для прослушивания потока радиостанции “Радио Максимум” на вашем компьютере под управлением операционных систем Windows, Linux и macOS. Этот плеер сочетает в себе простоту использования с высокой функциональностью, обеспечивая вам доступ к потоку в реальном времени с минимальными усилиями.

Просто скачайте приложение с GitHub:

https://github.com/demensdeum/Radio-Maximum-Electron/releases

Автор не имеет отношение к Радио Максимум, ему просто очень нравится это радио.
Основной функционал реализован проектом Nativifier

https://github.com/nativefier/nativefier

Лицензия на скрипты сборки MIT, у рантайма своя лицензия!

Подводное Приключение Полярного Мишки

Простенькая игра с бесконечно генерируемыми лабиринтами на ThreeJS.

Создавалась в рамках 3-х дневного геймджема “Начни игру” на тему “Семейная игра”.

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

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

https://demensdeum.com/demos/arctica/

Nixy Player

Nixy Player – Небольшой, расширяемый, кросс-платформенный JavaScript-runtime.

Кросс-платформенный: доступен на Windows, macOS и Linux, а также на любой другой платформе с поддержкой C++ и динамических библиотек.
Легковесный: минимальное потребление ресурсов с эффективной производительностью.
Расширяемый: создан для легкого расширения с помощью плагинов и дополнительных библиотек.

Пожалуйста, посетите страницу “Релизы”, чтобы быть в курсе последних выпусков и обновлений:
https://github.com/demensdeum/NixyPlayer/releases/

Raiden Video Ripper

Raiden Video Ripper – это проект с открытым исходным кодом, предназначенный для редактирования видео и конвертации форматов. Он создан с использованием Qt 6 (Qt Creator) и позволяет обрезать и конвертировать видео в форматы MP4, GIF и WebM. Вы также можете извлекать аудио из видео и конвертировать его в формат MP3.
Интерфейс RaidenVideoRipper

Кадр из COSTA RICA IN 4K 60fps HDR (ULTRA HD)
https://www.youtube.com/watch?v=LXb3EKWsInQ

Пожалуйста, посетите страницу “Релизы”, чтобы быть в курсе последних выпусков и обновлений:
https://github.com/demensdeum/RaidenVideoRipper/releases

Donki Hills

За месяц сделал забавный гэг, игру-пародию с помощью движка Unreal Engine 5. Разработка велась на Twitch стриме.

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

https://demensdeum.itch.io/donki-hills

Защитники роботов

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

– Тут явно проблема в поведении
– Ну зарелизим и когда пользователи начнут жаловаться вот тогда и исправим
– ??? Ну ок…

Вроде бы рабочая схема да? Достаточно оптимальный алгоритм для команд с малым бюджетом, сжатыми сроками, недостаточного исследования/отсутствия UI/UX специалиста. Пользователи же будут жаловаться если что, ничего страшного.
Поиск в гугле показывает что источник этой методы происходит из статьи – “Complaint-Driven Development” от Coding Horror

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

На следующий день я зашел за продуктами в супермаркет снова, пробил продукты через терминал. На выходе меня встретил мужчина южной внешности с густой бородой, протянув смартфон он сказал – “Это вы на камере?”, я посмотрел в его телефон и увидел себя в майке Melodic-Death-Metal группы Arch Enemy с черепами и всем таким, причин сомневаться не было.
“Да это я, а в чем дело?”, мужчина, очень сильно прищурившись, сказал “Ты вчера колбасу не пробил”… ухты

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

– На видео видно как сканер отработал
– Ничего не отработал, оплати колбасу!

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

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

В этот день я понял насколько на самом деле пользователям сложно пожаловаться на аппаратные, программные продукты, и что скорее всего мантра “люди будут жаловаться – исправим” работает очень плохо. Основная причина это люди которые защищают сломанных роботов, сломанные программные решения, для простоты предлагаю ввести новые термины – Защитник Сломанного Робота и Защитник Сломанных Систем.

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

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

– Вот здесь кое-что не работает, по документации вроде бы правильно всё
– А, так ты не читал тот мануал из 2005 года, где внизу маленькими буквами написано что надо дописать PROGRAM_START:6969
– ??? ээээ

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

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

Источники
https://blog.codinghorror.com/complaint-driven-development/
https://habr.com/ru/articles/554404/
https://en.wikipedia.org/wiki/British_Post_Office_scandal

Сборка bgfx Emscripten приложения

В этой заметке я опишу способ сборки bgfx приложений для веба (WebAssembly) через Emscripten.

Платформа для установки это Linux x86-64, например Arch Linux.

Для начала установим Emscripten версии 3.1.51, иначе у вас ничего не получится, всё из-за изменения типа динамических библиотек в последней версии Emscripten. Подробнее можно прочитать здесь:
https://github.com/bkaradzic/bgfx/discussions/3266

Делается это так:


git clone https://github.com/emscripten-core/emsdk.git



cd emsdk



./emsdk install 3.1.51



./emsdk activate 3.1.51



source ./emsdk_env.sh



Соберем bgfx для WebAssembly – Emscripten:


mkdir bgfx-build-test



cd bgfx-build-test



git clone https://github.com/bkaradzic/bx.git



git clone https://github.com/bkaradzic/bimg.git



git clone https://github.com/bkaradzic/bgfx.git



cd bgfx



emmake make wasm-debug



В результате в папке .build у вас будут файлы bitcode с расширением .bc, которые нужно будет линковать с вашим bgfx приложением.
Должны быть bgfx.bc, bx.bc, bimg.bc; в разных сборках разное название для этих файлов, в зависимости от типа сборки (release/debug)

Добавляем в CMakeLists.txt файл линковку с .bc файлами, для примера абсолютные пути к файлам из проекта bgfx-experiments:


target_link_libraries(${PROJECT_NAME} SDL2 GL /home/demensdeum_stream/Sources/bgfx-build/bgfx/.build/wasm/bin/bgfxDebug.bc /home/demensdeum_stream/Sources/bgfx-build/bgfx/.build/wasm/bin/bxDebug.bc /home/demensdeum_stream/Sources/bgfx-build/bgfx/.build/wasm/bin/bimgDebug.bc)



Теперь поменяйте native window handle в platform data на инициализации bgfx:


bgfx::PlatformData platformData{};



platformData.context = NULL;



platformData.backBuffer = NULL;



platformData.backBufferDS = NULL;



platformData.nwh = (void*)"#canvas";



Также надо заменить тип рендера на OpenGL:


bgfx::Init init;



init.type = bgfx::RendererType::OpenGL;







init.resolution.width = screenWidth;



init.resolution.height = screenHeight;



init.resolution.reset = BGFX_RESET_VSYNC;



init.platformData = platformData;







if (!bgfx::init(init))



{



    throw std::runtime_error("Failed to initialize bgfx");



}



Перекомпилируйте шейдеры GLSL под 120:


shaderc -f "VertexShader.vs" -o "VertexShader.glsl" --type "v" -p "120"



shaderc -f "FragmentShader.fs" -o "FragmentShader.glsl" --type "f" -p "120"



Ес-но .glsl файлы надо добавить к CMakeLists.txt как –preload-file:


set(CMAKE_CXX_FLAGS ... <Остальная часть>



--preload-file VertexShader.glsl \



--preload-file FragmentShader.glsl \



Осталось заменить основной цикл рендера в вашем приложении с while на вызов функции через emscripten_set_main_loop.

Об этом можно прочитать здесь:
https://demensdeum.com/blog/ru/2017/03/29/porting-sdl-c-game-to-html5-emscripten/

Далее собирайте свой Emscripten проект по обычному, всё должно работать.
Из интересного – в сборке Emscripten 3.1.51 похоже отсутствует OpenAL (или только у меня).

Исходный код проекта который корректно собирается с bgfx и Emscripten:
https://github.com/demensdeum/bgfx-experiments/tree/main/2-emscripten-build

Источники

https://github.com/bkaradzic/bgfx/discussions/3266
https://bkaradzic.github.io/bgfx/build.html
https://emscripten.org/docs/getting_started/downloads.html
https://demensdeum.com/blog/ru/2017/03/29/porting-sdl-c-game-to-html5-emscripten/
https://llvm.org/docs/BitCodeFormat.html

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

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

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

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

Surreal Engine Emscripten Demo

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

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

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

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

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

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

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


-s MAX_WEBGL_VERSION=2 \

-s EXCEPTION_DEBUG \

-fexceptions \

--preload-file UnrealTournament/ \

--preload-file SurrealEngine.pk3 \

--bind \

--use-preload-plugins \

-Wall \

-Wextra \

-Werror=return-type \

-s USE_SDL=2 \

-s ASSERTIONS=1 \

-w \

-g4 \

-s DISABLE_EXCEPTION_CATCHING=0 \

-O3 \

--no-heap-copy \

-s ALLOW_MEMORY_GROWTH=1 \

-s EXIT_RUNTIME=1")

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


emmake make -j 16

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

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

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

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

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

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

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

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


#include <emscripten.h>

Engine *EMSCRIPTEN_GLOBAL_GAME_ENGINE = nullptr;

void emscripten_game_loop_step() {

	EMSCRIPTEN_GLOBAL_GAME_ENGINE->Run();

}

#endif

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

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

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

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

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

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


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



#if __EMSCRIPTEN__

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

#endif



А сеть есть?

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

Заключение

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

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

Ссылки

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

https://github.com/dpjudas/SurrealEngine

Флеш жив – Interceptor 2021

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

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

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

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

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

Масоны-ДР Демо Игры

Масоны-ДР (Masonry-AR) это игра в дополненной реальности, где нужно перемещаться по городу в реальном мире и собирать масонские знания из книг, добывая валюту и захватывая территорию за свой масонский орден. Игра не имеет отношения к каким либо реальным организациям, все совпадения случайны.

Демо игры:
https://demensdeum.com/demos/masonry-ar/client

Вики:
https://demensdeum.com/masonry-ar-wiki-ru/

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

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

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

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

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

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

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

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

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

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

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

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

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


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


print("One item access example")

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

print("Array access example")

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

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

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

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


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

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

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


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

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


print("One item access example")

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

print("Array access example")

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

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

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

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

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

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

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


print("One item access example")

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

print("Array access example")

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

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

Итог

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

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

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

Источники

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

dd input/output error

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

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

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

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

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

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

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

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

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

ChatGPT

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

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

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

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

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

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

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


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

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

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

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

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

Mitsume ga Tōru (NES) – Третий глаз на Денди

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

Mitsume ga Tooru (яп. 三つ目がとおる Mitsume ga tōru?, букв. “трёхглазый”) — видеоигра в жанре платформера, разработанная компанией Natsume в 1992 году эксклюзивно для игровой консоли Nintendo Entertainment System. Игра основана на манге и аниме Mitsume ga Tooru. Это вторая игра по мотивам аниме, разработанная Natsume; предыдущей была Mitsume ga Tooru: 3Lie-Mon, выпущенная для платформы MSX двумя годами ранее. В России игра более известна под названием “3 Eyes”, или ” Третий глаз”.

Номер 2

Товарищи, гордость берет за проекты которые были созданы на основе Flame Steel Framework 1 и конкретно на Flame Steel Engine 1, а именно Death-Mask, Cube Art Project, так как всё это задумывалось как большой эксперимент, создания мультимедия фреймворка в одиночку, способного работать на наибольшем количестве платформ. Считаю эксперимент завершился удачно сразу после выхода Cube Art Project.

Теперь о решениях к которым я пришел в ходе разработки новых проектов на FSFramework 1

Во время разработки Space Jaguar и шутера Space Jaguar Galaxy Bastards, стало понятно что инструменты Flame Steel Framework уже устарели, не успев даже стать хоть сколько-нибудь удобными.

Поэтому я принял решение разрабатывать полностью новый Flame Steel Framework 2. Основным решением будет переход на свой язык-транспайлер Rise 2, также архитектурно больше не будет использоваться система компонентов (ECS), т.к. она оказалась нужна только в рамках игровой логики с большой динамикой. По этой причине во Flame Steel Framework 2 система компонентов будет возможна только во время использования скриптовых языков которые планируется внедрить (как минимум Lua и JavaScript), интересной особенностью является то, что эти языки динамичны по своей природе, поэтому дополнительное создание системы компонентов избыточно.

Следить за развитием новых проектов можно в блоге и на Gitlab:

https://gitlab.com/demensdeum/rise2

https://gitlab.com/demensdeum/flamesteelengine2

https://gitlab.com/demensdeum/flame-steel-engine-2-demo-projects

https://gitlab.com/demensdeum/space-jaguar-action-rpg

https://gitlab.com/demensdeum/space-jaguar-galaxy-bastards

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