Видео демонстрация установки и настройки OldUnreal для Unreal Tournament 99 на macOS с CPU M1/M2/M3/M4
Вам нужны файлы из Steam или GoG версии Unreal Tournament 99 для Windows!
Почему важен 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.

Кадр из 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 выполнима.

Спустя месяц я могу продемонстрировать свой форк и сборку движка на 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
Запускаем Unreal Tournament 99 на MacBook с M1/M2/M3 (Apple Silicon)
Включаем подсветку 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)
Попробуйте вручную прочитать числа начиная с предпоследней левой ноды нижнего левого угла, для каждой ноды слева – нода – справа.
Получится так:
- Предпоследняя нода слева внизу – 3.
- У нее есть левая ветвь – 1.
- Берем это число (1)
- Дальше берем саму вершину 3 (1, 3)
- Справа ветвь 6, но она содержит ветви. Поэтому ее прочитываем таким же образом.
- CЛева ветвь ноды 6 число 4 (1, 3, 4)
- Сама нода 6 (1, 3, 4, 6)
- Справа 7 (1, 3, 4, 6, 7)
- Идем наверх к корневой ноде – 8 (1,3, 4 ,6, 7, 8)
- Печатаем все что справа по аналогии
- Получаем итоговый список – 1, 3, 4, 6, 7, 8, 10, 13, 14
Чтобы реализовать алгоритм в коде потребуются две функции:
- Сборка бинарного дерева поиска
- Распечатка бинарного дерева поиска в правильно порядке
Собирают бинарное древо поиска также как и прочитывают, к каждой ноде прицепляется число слева или справа, в зависимости от того – меньше оно или больше.
Пример на 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
Источники
Convert Sorted Array to Binary Search Tree (LeetCode 108. Algorithm Explained) – YouTube
Sorting algorithms/Tree sort on a linked list – Rosetta Code
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), в которые будем поразрядно складывать/сортировать числа.
Далее:
- Запускаем цикл со счетчиком i до максимального количества символов в числе
- По индексу i справа налево получаем один символ для каждого числа, если символа нет, то считаем что это ноль
- Символ преобразовываем в число
- Выбираем ведро по индексу – числу, кладем туда число полностью
- После окончания перебора чисел, преобразовываем все ведра назад в список чисел
- Получаем числа отсортированные по разряду
- Повторяем пока не кончатся все разряды
Пример 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
Реализация
Алгоритм обычно разделяют на три функции:
- Создание кучи
- Алгоритм просеивания (heapify)
- Замена последнего неотсортированного элемента и первого
Куча создается с помощью прохода по предпоследнему ряду бинарного дерева с помощью функции 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://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://ru.wikibrief.org/wiki/Heapsort
https://www.youtube.com/watch?v=GUUpmrTnNbw