Radio-Maximum-Electron

Radio Maximum Electron 是一款功能强大且方便的应用程序,旨在在运行 Windows、Linux 和 macOS 操作系统的计算机上收听 Radio Maximum 广播电台的流。该播放器结合了易用性和强大的功能,让您可以轻松地访问实时流媒体。

只需从 GitHub 下载应用程序:

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

作者与Radio Maximum无关,他只是非常喜欢这个收音机。
主要功能由Nativifier项目实现

https://github.com/nativefier/nativefier

MIT 构建脚本的许可证,运行时有自己的许可证!

水下北极熊冒险

一个使用 ThreeJS 无限生成迷宫的简单游戏。

作为主题为“家庭游戏”的为期 3 天的游戏即兴游戏“开始游戏”的一部分而创建。

一只极地探险家的幼崽正和妈妈在冰面上行走,突然灾难降临——冰面破裂,他掉进了冰冷的海水中。妈妈没有时间救他,这只熊最终进入了一个神秘的水下洞穴。令他惊讶的是,他发现自己可以在水下呼吸。只有一种方法可以摆脱这个陷阱——克服深海、解开谜语并与攻击性的鲨鱼战斗,而鲨鱼可以通过精准投掷苹果来击退。

现在他的目标是找到摆脱这个水下陷阱的方法,回到母亲身边,克服深海的危险并解开谜题。

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

Nixy Player

Nixy Player – 小型、可扩展、跨平台的 JavaScript 运行时。

跨平台:可在 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

来自哥斯达黎加的 4K 60fps HDR(超高清)剧照
https://www.youtube.com/watch?v=LXb3EKWsInQ
请访问版本页面以获取最新版本和更新:
https://github.com/demensdeum/RaidenVideoRipper/releases

Donki Hills

在一个月内,我制作了一个有趣的笑话,一个使用虚幻引擎 5 的模仿游戏。开发是在 Twitch 流上进行的。

该游戏的故事讲述了一个普通的俄罗斯小伙子詹姆斯,他在Tinder上找到了一个女孩玛丽亚,但由于俄罗斯的制裁和Tinder的终止,他与她失去了联系。现在他唯一留下的就是她照片的截图,他使用谷歌地图找到了照片的拍摄地点——新西伯利亚附近的Tikhie Donki村。詹姆斯去那里寻找玛丽亚……

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

机器人卫士

在讨论某些软件功能的正确操作时,我经常遇到这样的情况:从用户的角度来看,该功能看起来很奇怪且不合逻辑。与产品负责人的讨论如下所示:

–这里显然存在行为问题
–好吧,我们会发布它,当用户开始抱怨时,我们会修复它
– ???好吧…

这似乎是一个可行的方案,对吧?对于预算较小、期限紧迫、研究不足/缺乏 UI/UX 专家的团队来说,这是一个相当理想的算法。如果有什么事情用户会抱怨,没关系。
谷歌搜索发现,该方法的来源来自一篇文章《 “投诉驱动的开发”通过编码恐怖

有一次我卖食物,包括医生的香肠,售价 300 卢布。通过超市的终端,我带着这根香肠离开了商店,完全相信它已经付款了。终端提出不打印支票,我同意了,以免在这张支票上浪费宝贵的纸张。在为每个产品“打孔”货物的过程中,终端发出吱吱声,这表明一切正常。另外,终端会发出声音警报,并随着条形码扫描仪的背光闪烁。

第二天我又去超市买了菜,然后把菜放进了航站楼。在出口处,我遇到了一位南方长相、蓄着浓密胡须的男子,他手里拿着一部智能手机,他说:“ “镜头里是你吗?”,我看着他的手机,看到自己穿着大敌的旋律死亡金属T恤,上面有骷髅什么的,没有理由怀疑。
“是的,是我,怎么了?”男人眯着眼睛,说道,“昨天你没有打香肠。”哇

在对他是谁以及他如何得出这些结论进行简短调查后,他给我看了一段挂在商店天花板上的视频,在视频中我打了香肠,终端随着扫描仪的背光闪烁,我把香肠放进袋子里。

–视频展示了扫描仪的工作原理
–没有做任何事,付香肠钱!

对这种态度有点惊讶,我要求一本投诉书写下终端需要软件改进,因为它给出了正确操作的所有迹象,但实际上它只是有缺陷,没有在屏幕上发出信号。以任何方式。

与他和他的老板争吵了10分钟后,老板立即跑去维护他的员工和垃圾工作终端,他们决定打电话给管理员的女孩,让她带上一本投诉书并打医生的拳头。香肠。

那天我意识到用户抱怨硬件和软件产品是多么困难,最有可能的是“人们会抱怨”的口头禅。让我们来解决它”的效果非常糟糕。主要原因是那些捍卫损坏的机器人、损坏的软件解决方案的人,为了简单起见,我建议引入新术语“”。破碎机器人的防御者和破碎系统的防御者。

普通用户不能抱怨终端的故障,因为他们受到 ZasRoshniks 的干扰,ZasRoshniks 出于某种原因变得依恋并开始喜欢他们使用的机器,也许认为它们是某种有生命的实体,忘记了没有任何东西住在那里。

类似的情况也发生在 ZaSSoshniki 上,这些人可以为框架、编程语言或任何其他软件产品中的一些愚蠢缺陷辩护,尽管有用户和其他开发人员的抱怨。
与 ZaSSoshnik 的典型对话如下:

–这里有些东西不起作用,根据文档,一切似乎都是正确的
–哦,所以你没有读过 2005 年的手册,底部用小写字母写着你需要添加 PROGRAM_START:6969
– ???呃

这些人可能不明白他们自己如何助长了自己和他人的问题、错误、时间和金钱的浪费。因为它们,每个人都会受苦,因为如果隐瞒不明显的事情以及软件和硬件解决方案的问题,数字化转型是不可能的。
我知道最近有关英国邮局 Horizo​​n 软件中的一个错误的故事,该错误导致人们负债累累,破坏了婚姻,并毁掉了人们的生活数十年。这一切的持续都是由于人们的纵容,他们对软件中的问题保持沉默,从而“保护”了软件。他。

朋友们,不要成为 ZaSRoshniks 和 ZaSSoshniks,对待你使用的工具要持保留态度,否则你将面临着糟糕、破碎系统的完全奴役,就像未来新数字世界中的人质一样。对于那些不能“”的人来说至少不要打扰其他试图关注不工作、干扰的软件/硬件的人,因为这些产品的开发人员已经同意“ “当用户开始抱怨时,我们就会解决它。”

来源
https://blog.codinghorror.com/complaint-driven-development/< /a>
https://habr.com/ru/articles/554404/< br/>
https://en.wikipedia.org/wiki/British_Post_Office_scandal

构建 bgfx Emscripten 应用程序

在这篇文章中,我将描述一种使用 Emscripten 构建 bgfx 网络应用程序 (WebAssembly) 的方法。

安装平台为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



让我们为 WebAssembly 组装 bgfx –脚本:


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 文件夹中,您将拥有扩展名为 .bc 的位码文件,该文件需要与您的 bgfx 应用程序链接。
应该是bgfx.bc、bx.bc、bimg.bc;不同的程序集对这些文件有不同的名称,具体取决于程序集的类型(发布/调试)

添加带有 .bc 文件的 CMakeLists.txt 文件的链接,例如 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)



现在将平台数据中的本机窗口句柄更改为 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 中:


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



--preload-file VertexShader.glsl \



--preload-file FragmentShader.glsl \



仍然需要通过 emscripten_set_main_loop 使用 while 函数调用替换应用程序中的主渲染循环。

您可以在这里阅读:
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。

超现实引擎–一个游戏引擎,实现了Unreal Engine 1的大部分功能,著名的游戏都使用这个引擎–虚幻竞技场 99、虚幻、杀出重围、不朽。它指的是主要在单线程执行环境中工作的经典引擎。

最初,我有一个想法,那就是承担一个我无法在任何合理时间内完成的项目,从而向我的 Twitch 粉丝表明,有些项目甚至是我也无法完成。在我的第一次直播中,我突然意识到使用 Emscripten 将 Surreal Engine C++ 移植到 WebAssembly 的任务是可行的。

Surreal Engine Emscripten Demo

一个月后,我可以在 WebAssembly 上演示我的前叉和引擎组装:
https://demensdeum.com/demos/SurrealEngine/

与原始版本一样,控制是使用键盘箭头进行的。接下来,我计划将其调整为移动控制 (tachi),添加正确的光照和 Unreal Tournament 99 渲染的其他图形功能。

从哪里开始?

我想说的第一件事是,任何项目都可以使用 Emscripten 从 C++ 移植到 WebAssembly,唯一的问题是功能有多完整。选择一个库端口已经可用于 Emscripten 的项目;对于 Surreal Engine,你非常幸运,因为该引擎使用 SDL 2、OpenAL 库。它们都被移植到 Emscripten。不过,Vulkan 用作图形 API,目前无法用于 HTML5,实现 WebGPU 的工作正在进行中,但也处于草案阶段,也未知从 Vulkan 到 WebGPU 的进一步移植有多简单,完全标准化后。因此,我必须为 Surreal Engine 编写自己的基本 OpenGL-ES / WebGL 渲染器。

构建项目

在 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

接下来我们将准备索引.html ,其中包括项目文件系统预加载器。为了上传到网络,我使用了 Unreal Tournament Demo 版本 338。正如您从 CMake 文件中看到的,解压后的游戏文件夹已添加到构建目录中,并作为 Emscripten 的预加载文件进行链接。

主要代码更改

那就需要改变游戏的游戏循环,不能无限循环,这样会导致浏览器卡住,而是需要使用emscripten_set_main_loop,我在2017年的笔记中写过这个功能< a href="https://demensdeum.com/blog/ru/2017/03/29/porting-sdl-c-game-to-html5-emscripten/" rel="noopener" target="_blank">将 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

之后,您需要确保应用程序中没有后台线程;如果有,则准备将其重写为单线程执行,或者使用 Emscripten 中的 phtread 库。
Surreal Engine中的后台线程用于播放音乐,数据来自主引擎线程,有关当前曲目、是否需要播放音乐或是否缺少音乐,然后后台线程通过互斥体接收新状态并开始播放新音乐,或暂停。背景流还用于在播放期间缓冲音乐。
我尝试使用 pthread 为 Emscripten 构建 Surreal Engine,但没有成功,因为 SDL2 和 OpenAL 端口是在没有 pthread 支持的情况下构建的,而且我不想为了音乐而重建它们。因此,我使用循环将背景音乐流的功能转移到单线程执行。通过从 C++ 代码中删除 pthread 调用,我将缓冲和音乐播放移至主线程,这样就不会出现延迟,我将缓冲区增加了几秒钟。

接下来我会描述图形和声音的具体实现。

不支持 Vulkan!

是的,HTML5 不支持 Vulkan,尽管所有营销手册都将跨平台和广泛的平台支持作为 Vulkan 的主要优势。因此,我必须为简化的 OpenGL 类型编写自己的基本图形渲染器 – ES,它用在移动设备上,有时它不包含现代OpenGL的时尚功能,但它很好地移植到WebGL,这正是Emscripten所实现的。写了基本的tile渲染,bsp渲染,最简单的GUI显示,渲染模型+贴图,两周就完成了。这也许是该项目中最困难的部分。实现 Surreal Engine 渲染的全部功能还有很多工作要做,因此欢迎读者以代码和拉取请求的形式提供任何帮助。

支持 OpenAL!

幸运的是,Surreal Engine 使用 OpenAL 进行音频输出。在 OpenAL 中编写了一个简单的 hello world 并使用 Emscripten 在 WebAssembly 中将其组装后,我清楚地意识到一切是多么简单,然后我开始移植声音。
经过几个小时的调试,很明显 Emscripten 的 OpenAL 实现存在几个错误,例如,在初始化读取单通道数时,该方法返回无限数,并且在尝试初始化无限大小的向量后,C++崩溃并出现异常向量::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目前不支持在线游戏,支持与机器人一起玩,但我们需要有人为这些机器人编写AI。理论上,您可以使用Websockets在WebAssembly/Emscripten上实现网络游戏。

结论

总之,我想说,由于使用了 Emscripten 移植的库,以及我过去在 WebAssembly 中使用 C++ 实现游戏的经验,Surreal Engine 的移植非常顺利在 Emscripten 上。以下是有关该主题的知识来源和存储库的链接。
M-M-M-杀死怪物!

此外,如果您想帮助该项目,最好使用 WebGL/OpenGL ES 渲染代码,请在 Telegram 中给我写信:
https://t.me/demenscave

链接

https://demensdeum.com/demos/Sur​​realEngine/
https://github.com/demensdeum/SurrealEngine-Emscripten

https://github.com/dpjudas/SurrealEngine

Flash Forever – Interceptor 2021

Recently, it turned out that Adobe Flash works quite stably under Wine. During a 4-hour stream, I made the game Interceptor 2021, which is a sequel to the game Interceptor 2020, written for the ZX Spectrum.

For those who are not in the know – the Flash technology provided interactivity on the web from 2000 to around 2015. Its shutdown was prompted by an open letter from Steve Jobs, in which he wrote that Flash should be consigned to history because it lagged on the iPhone. Since then, JS has become even more sluggish than Flash, and Flash itself has been wrapped in JS, making it possible to run it on anything thanks to the Ruffle player.

You can play it here:
https://demensdeum.com/demos/Interceptor2021

Video:
https://www.youtube.com/watch?v=-3b5PkBvHQk

Source code:
https://github.com/demensdeum/Interceptor-2021

Masons-DR 演示游戏

Masonry-AR 是一款增强现实游戏,您需要在现实世界中的城市中导航,从书中收集共济会知识,为您的共济会订单获取货币并占领领土。游戏与任何真实组织无关,所有比赛都是随机的。

游戏演示:
https://demensdeum.com/demos/masonry-ar/client

维基:
https://demensdeum.com/masonry-ar-wiki-ru/

源代码:
https://github.com/demensdeum/Masonry-AR

增删改查存储库

在这篇笔记中,我将描述著名的经典 CRUD 模式的基本原理,以及 Swift 语言的实现。 Swift 是一种开放的跨平台语言,适用于 Windows、Linux、macOS、iOS、Android。

有许多解决方案可以抽象数据存储和应用程序逻辑。其中一种解决方案是 CRUD 方法,它是 C# 的缩写。创建,R-读取,U –更新,D–删除。
通常,此原则是通过实现数据库接口来实现的,其中使用唯一标识符(例如 id)来操作元素。为每个字母创建一个界面 CRUD –创建(对象,id),读取(id),更新(对象,id),删除(对象,id)。
如果一个对象在其内部包含一个 id,那么 id 参数可以从方法(Create、Update、Delete)中省略,因为整个对象及其字段 – 都被传递到那里。 ID。但对于– Read需要id,因为我们想通过id从数据库中获取一个对象。

所有名字均为虚构

让我们假设一个假设的 AssistantAI 应用程序是使用免费的 EtherRelm 数据库 SDK 创建的,集成很简单,API 非常方便,因此该应用程序被发布到市场。
突然,SDK 开发者 EtherRelm 决定付费,将价格定为每个应用程序用户每年 100 美元。
什么?是的! AssistantAI的开发者现在应该做什么,因为他们已经有100万活跃用户了!支付一亿美元?
相反,会做出评估将应用程序转移到平台本机 RootData 数据库的决定;根据程序员的说法,这样的转移将需要大约六个月的时间,这还不考虑应用程序中新功能的实现。经过深思熟虑,决定从市场上删除该应用程序,并在另一个带有内置BueMS数据库的免费跨平台框架上重写它,这将解决付费数据库的问题+将简化在其他平台上的开发。
一年后,该应用程序在 BueMS 中被重写,但突然框架开发人员决定对其进行付费。事实证明,团队已经两次陷入同一个陷阱,第二次是否能摆脱困境就完全是另外一回事了。

抽象来救援

如果开发人员在应用程序中使用接口的抽象,这些问题本来可以避免。 OOP 的三大支柱多态、封装、继承,不久前他们还添加了另一个“多态”、“封装”、“继承”。抽象。
数据抽象允许您用最少的细节以一般术语描述想法和模型,同时足够准确以实现用于解决业务问题的特定实现。
如何抽象数据库操作,使得应用逻辑不依赖于它?我们使用 CRUD 方法!

简化的 UML CRUD 图如下所示:

虚构的 EtherRelm 数据库示例:

真实 SQLite 数据库的示例:

正如您已经注意到的,当您切换数据库时,只有与应用程序交互的 CRUD 接口发生变化。 CRUD 是 GoF 模式的实现适配器,因为使用它,我们可以使应用程序接口适应任何数据库并组合不兼容的接口。
文字都是空的,给我看看代码
为了用编程语言实现抽象,使用接口/协议/抽象类。所有这些都是同一个顺序的现象,但是,在面试中你可能会被要求说出它们之间的区别,我个人认为这没有多大意义,因为使用的唯一目的是实现数据抽象,否则就是测试受访者的记忆力。
CRUD通常是在Repository模式的框架内实现的,但是,存储库可能会也可能不会实现CRUD接口,这完全取决于开发人员的聪明才智。

考虑一下 Book 结构存储库的相当典型的 Swift 代码,直接使用 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 存储库的完整具体实现,详细信息如下。
添加了类型别名以用于代码的自文档化。
弱耦合和强耦合
与特定结构 (struct) 的分离是使用通用 T 实现的,而通用 T 又必须实现可编码协议。 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 数据格式、客户端结构,也是写入和读取数组的示例:


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 检查期间,已实现异常处理,其中远程项目的读取将不再可用。

切换数据库

现在我将向您展示如何将当前代码传输到另一个数据库。例如,我将采用 ChatGPT 生成的 SQLite 存储库代码:


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 序列化的数组文件,具有一个客户端结构。

切换数据存储格式

现在让 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 -> XML数据转换器

总计

CRUD 存储库是可用于实现应用程序架构组件松散耦合的设计模式之一。另一种解决方案是“使用ORM(对象关系映射),简单来说,ORM使用一种将结构完全映射到数据库的方法,然后将模型的更改显示在数据库上(映射(!))。
但这是一个完全不同的故事。

Swift 的 CRUD 存储库的完整实现位于:
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 输入/输出错误

如果在 Linux 中使用 dd 复制普通磁盘时出现输入/输出错误,该怎么办?

西图维娜很伤心,但也是可以解决的。您很可能正在处理包含无法再使用、写入或读取的坏块的故障磁盘。

请务必使用 S.M.A.R.T. 检查此类磁盘,它很可能会显示磁盘错误。我的情况就是这样;坏块数量如此之大,以至于我不得不告别旧硬盘并更换为新的 SSD。

问题在于该磁盘包含一个完整工作的系统,其中包含工作所需的许可软件。我尝试使用partimage来快速复制数据,但突然我发现该实用程序只复制了磁盘的三分之一,然后它以段错误或其他一些有趣的Sishny/Sipplusplus笑话结束。

接下来,我尝试使用dd复制数据,结果发现dd到达的位置与partimage大致相同,然后出现输入/输出错误。与此同时,各种有趣的标志,如 conv=noerr、skip 或其他东西根本没有帮助。

但是使用名为 ddrescue 的 GNU 实用程序将数据复制到另一个磁盘时没有出现任何问题。

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

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

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

聊天GPT

大家好!在这篇文章中我想谈谈 ChatGPT – OpenAI 强大的语言建模可以帮助解决各种文本处理问题。我将向您展示该工具的工作原理以及如何在实际情况中使用它。让我们开始吧!

目前,ChatGPT 是世界上最好的基于神经网络的语言模型之一。创建它的目的是帮助开发人员创建能够生成自然语言并与其中的人进行交流的智能系统。

ChatGPT 的主要优势之一是它能够对文本进行上下文建模。这意味着该模型会考虑之前的对话,并利用它来更准确地了解情况并生成更自然的响应。

您可以使用 ChatGPT 执行各种任务,例如自动化客户支持、创建聊天机器人、文本生成等等。

ChatGPT 背后的神经网络接受了大量文本的训练,以确保高度准确的预测。这使得模型能够生成可以支持对话和回答问题的自然文本。

借助 ChatGPT,您可以创建自己的聊天机器人和其他可以用自然语言与人们交互的智能系统。这在旅游、零售和客户支持等行业尤其有用。

总之,ChatGPT –它是解决各种语言建模问题的强大工具。它的上下文建模能力使其对于创建聊天机器人和智能系统特别有用。

<小时/>

事实上,上面的所有内容都是 ChatGPT 自己编写的。什么?是的?我自己都震惊了!

您可以在这里尝试网格本身:
https://chat.openai.com/chat

在 macOS 上打开 USB 键盘背光

我最近买了一个非常便宜的 Getorix GK-45X USB 键盘,带有 RGB 背光。将其连接到配备 M1 处理器的 MacBook Pro 后,很明显 RGB 背光不起作用。即使按下神奇组合 Fn + Scroll Lock 也无法打开背光;只是 MacBook 屏幕的背光亮度发生了变化。
这个问题有几种解决方案,分别是OpenRGB(不起作用)、HID LED Test(不起作用)。只有 kvmswitch 实用程序有效:
https://github.com/stoutput/OSX-KVM

您需要从 GitHub 下载它并允许它从系统设置的安全面板中的终端运行。
据我从描述中了解到,启动该实用程序后,它会发送 Fn + Scroll Lock 按键,从而打开/关闭键盘上的背光。

光之瞳 (NES) –第三只眼注视着丹迪

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

Mitsume ga Tooru(三つ目がとおる Mitsume ga toru?,字面意思是“三眼”)是夏目于 1992 年专门为任天堂娱乐系统开发的一款平台视频游戏。该游戏基于漫画和动画《Mitsume ga Toru》。这是夏目开发的第二款动漫游戏;上一款是两年前在 MSX 平台上发布的《Mitsume ga Tooru: 3Lie-Mon》。在俄罗斯,这款游戏更广为人知的名称是“三眼”或“三眼”。第三只眼……

Number 2

Comrades, I take pride in projects that were created on the basis of Flame Steel Framework 1 and specifically on Flame Steel Engine 1, namely Death-Mask, Cube Art Project, since all this was conceived as a big experiment, creating a multimedia framework alone that can work on the most platforms. I think the experiment ended successfully immediately after the release of the Cube Art Project.

Now about the decisions that I came to during the development of new projects on FSFramework 1

During the development of Space Jaguar and the Space Jaguar Galaxy Bastards shooter, it became clear that the Flame Steel Framework tools were already outdated, not even having time to become at least somewhat convenient.

Therefore, I decided to develop a completely new Flame Steel Framework 2. The main decision will be to switch to my Rise 2 transpiler language, and the Component System (ECS) will no longer be used architecturally, because. it turned out to be needed only within the framework of game logic with great dynamics. For this reason, in Flame Steel Framework 2, the component system will only be possible while using the scripting languages ​​that are planned to be implemented (at least Lua and JavaScript), an interesting feature is that these languages ​​​​are dynamic in nature, so additional creation of the component system is redundant.

You can follow the development of new projects on the blog and on 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

树排序

树排序——使用二叉搜索树进行排序。时间复杂度– O(n²)。在这样的树中,左边的每个节点都有小于该节点的数字,右边的每个节点都有大于该节点的数字,当从根开始并从左到右打印值时,我们得到一个排序的数字列表。令人惊讶吧?

考虑二叉搜索树图:

Derrick Coetzee(公共领域)

尝试手动读取从左下角倒数第二个左侧节点开始的数字,对于左侧的每个节点 – 右侧的一个节点。

它看起来像这样:

  1. 左下角倒数第二个节点 – 3.
  2. 它有一个左分支 – 1.
  3. 取这个数字(1)
  4. 接下来我们采用顶点 3 (1, 3)
  5. 右侧是分支 6,但它包含分支。因此,我们以同样的方式阅读它。
  6. 节点 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

桶排序

桶排序——按桶排序。该算法类似于计数排序,不同之处在于将数字收集到“桶”范围中,然后使用任何其他足够高效的排序算法对桶进行排序,最后一步是将“桶”展开减一,得到一个排序列表。

算法的时间复杂度为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

基数排序

Radix Sort – 基数排序。该算法与计数排序类似,不进行元素比较;而是将元素逐个字符分组到“桶”(桶)中,桶是通过当前数字字符的索引来选择的。时间复杂度– O(nd)。

它的工作原理是这样的:

  • 输入为数字 6、12、44、9
  • 我们将创建 10 个列表桶 (0-9),我们将在其中逐位添加/排序数字。

下一个:

  1. 使用计数器 i 开始循环,直到达到数字中的最大字符数
  2. 通过索引 i 从右到左,我们为每个数字获取一个符号;如果没有符号,则假设它为零
  3. 将符号转换为数字
  4. 按索引 – 数字选择一个存储桶,并将整个数字放在那里
  5. 搜索完数字后,将所有桶转换回数字列表
  6. 获取按排名排序的数字
  7. 重复直到所有数字都消失

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

来源

<一href="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"目标=“_空白” rel="noopener">https://ru.wikipedia.org/wiki/%D0%9F%D0%BE%D1%80%D0%B0%D0%B7%D1%80%D1%8F%D 0%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

堆排序

堆排序——金字塔排序。算法的时间复杂度– 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

当你到达地板的尽头时,走到上面的地板上,如果可以的话,把所有东西都扔在那里。
结果是一个数据结构——堆,即最大堆,因为顶部是最大的元素:
⠀⠀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、79

接下来我们重复排序算法,忽略已经排序的,最后我们得到一个 类型:
⠀⠀0
⠀2⠀3
4 5 7 9

或者作为列表:
0、2、3、4、5、7、9

实施

算法通常分为三个函数:

  1. 创建堆
  2. 筛选算法(heapify)
  3. 替换最后一个未排序元素和第一个元素

堆是通过使用heapify函数从右到左遍历二叉树的倒数第二行,直到数组的末尾来创建的。接下来在循环中,进行第一次数字替换,之后第一个元素落入/保持在原位,因此最大的元素落入第一位,重复该循环,参与者减少一个,因为每次传递后,排序后的数字保留在列表的末尾。

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/博客/460087/

https://ru.wikipedia.org/wiki/Pyramid_sort

https://neerc.ifmo.ru/wiki /index.php?title=Heap_sort

https://wiki5.ru/wiki/Heapsort

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

<一href="https://ru.wikipedia.org/wiki/%D0%94%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_(%D1%81%D1 %82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D0%B0_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B %D1%85)" target="_blank" rel="noopener">https://ru.wikipedia.org/wiki/Tree(数据结构)

<一href="https://ru.wikipedia.org/wiki/%D0%9A%D1%83%D1%87%D0%B0_(%D1%81%D1%82%D1 %80%D1%83%D0%BA%D1%82%D1%83%D1%80%D0%B0_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85 )” target="_blank" rel="noopener">https://ru.wikipedia.org/wiki/Heap(数据结构)

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/二进制堆的数组表示/

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

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

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

<一href="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"目标=“_空白” rel="noopener">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

Bumblebee All Troubles

Recently, it turned out that users of modern Nvidia GPUs under Arch Linux do not need to use the bumblebee package at all, for example, for me it did not detect an external monitor when connected. I recommend removing the bumblebee package and all related packages, and installing prime using the instructions on the Arch Wiki.
Next, to launch all games on Steam and 3D applications, add prime-run, for Steam this is done like this prime-run %command% in additional launch options.
To check the correctness, you can use glxgears, prime-run glxgears.
https://bbs.archlinux.org/viewtopic.php? pid=2048195#p2048195

快速排序

快速排序是一种分而治之的排序算法。递归地,我们逐个解析数字数组,将所选参考元素中的数字按照较小和较大的顺序放置,并将参考元素本身插入到它们之间的截止位置。经过几次递归迭代后,您将得到一个排序列表。时间复杂度 O(n2)。

方案:

  1. 我们首先从外部获取元素列表,即排序边界。第一步,排序边界将从头到尾。
  2. 检查起始边界和结束边界是否相交;如果发生这种情况,则该结束了
  3. 从列表中选择某个元素并将其命名为数据透视
  4. 将其向右移动到最后一个索引处的末尾,这样就不会妨碍
  5. 创建一个*较小数字*仍等于零的计数器
  6. 从左到右循环遍历列表,直到引用元素所在的最后一个索引(包括该索引)
  7. 我们将每个元素与参考元素进行比较
  8. 如果小于参考值,则根据较小数字的计数器的索引进行交换。增加较小数字的计数器。
  9. 当循环到达支持元素时,我们停止并根据较小数字的计数器将支持元素与元素交换。
  10. 我们分别针对列表左侧较小的部分和列表右侧较大的部分分别运行该算法。
  11. 因此,由于检查点 2,所有递归迭代都将开始停止
  12. 获取排序列表

快速排序是由莫斯科国立大学的科学家 Charles Anthony Richard Hoare 发明的,他在学习俄语后,在 Kolmogorov 学院学习了计算机翻译以及概率论。 1960年,因政治危机离开苏联。

Rust 中的示例实现:


use rand::Rng;

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

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

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

    let mut less_insert_index = left;

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

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

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

    reference_numbers.sort();

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

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

如果不清楚,我建议观看圣地亚哥大学 Rob Edwards 的视频 https://www.youtube.com/watch?v=ZHVk2blR45Q 最简单、一步步展示了算法的本质和实现。

链接

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

来源

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

二元插入排序

二分插入排序是插入排序的一种变体,其中使用二分查找来确定插入位置。该算法的时间复杂度为O(n2)

该算法的工作原理如下:

  1. 循环从零开始到列表末尾
  2. 在循环中选择一个数字进行排序,该数字存储在单独的变量中
  3. 二分查找查找索引以将此数字插入左侧的数字
  4. 一旦找到索引,左侧的数字就会从插入索引开始向右移动一位。在此过程中,需要排序的数字将被删除。
  5. 之前保存的号码将插入到插入索引处
  6. 循环结束时,整个列表将被排序

在二分查找过程中,有可能找不到该数字并且不会返回索引。由于二分查找的特殊性,会找到与要查找的数字最接近的数字,然后要返回索引,需要将其与要查找的数字进行比较,如果要查找的数字较小,则要返回的索引应为左侧的索引,如果大于或等于右侧的索引。

执行代码:


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

const numbersCount = 20
const maximalNumber = 100

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

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

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

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

链接

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

来源

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

希尔排序

希尔排序 – 插入排序的一种变体,对数字数组进行初步组合。

我们需要记住插入排序是如何工作的:

1.一个循环从零开始到循环结束,因此数组被分成两部分
2. 对于左侧部分,启动第二个循环,从右到左比较元素,删除右侧较小的元素,直到找到左侧较小的元素
3. 在两个循环结束时,我们得到一个排序列表

很久以前,计算机科学家 Donald Schell 想知道如何改进插入排序算法。他还想出了这样的想法:首先分两个周期遍历数组,但在一定距离内,逐渐减少“梳子”,直到变成常规的插入排序算法。一切真的就是这么简单,没有陷阱,在上面的两个循环中我们添加了另一个循环,在这个循环中我们逐渐减小了“梳子”的尺寸。您唯一需要做的就是在比较时检查距离,使其不会超出数组。

一个真正有趣的主题是选择用于更改第一个循环每次迭代的比较长度的序列。有趣的是,算法的性能取决于它。

已知选项和时间复杂度表可以在这里找到:https: //en .wikipedia.org/wiki/Shellsort#Gap_sequences

不同的人参与计算理想距离;显然,这个话题对他们来说很有趣。他们不能只运行 Ruby 并调用最快的 sort() 算法吗?

总的来说,这些奇怪的人写的论文主题是计算 Shell 算法的“梳子”的距离/间隙。我简单地使用了他们的工作结果并检查了 5 种类型的序列:Hibbard、Knuth-Pratt、Chiura、Sedgwick。

import time
import random
from functools import reduce
import math

DEMO_MODE = False

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

insertionSortDistanceSequence = [1]

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

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

reference = sortedNumbersAsString(randomNumbers, defaultSort)

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

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

在我的实现中,对于一组随机数字,最快的差距是 Sedgwick 和 Hibbard。

mypy

我还想提一下 Python 3 的静态类型分析器——我的。有助于解决动态类型语言固有的问题,即它消除了将某些内容粘贴在不需要的地方的可能性。

正如经验丰富的程序员所说,“当你拥有一支专业团队时,就不需要静态类型”,有一天我们都会成为专业人士,我们将编写与机器完全统一和理解的代码,但现在您可以使用类似的实用程序和静态类型语言。

链接

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

来源

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

双选排序

双选择排序 – 选择排序的子类型,看起来它的速度应该是它的两倍。普通算法对数字列表进行双重循环,找到最小数字并与上一层循环指向的当前数字交换位置。双选择排序查找最小和最大数字,然后替换上一层循环所指向的两位数字。左边和右边两个数字。当在列表中间找到需要替换的数字的光标时,整个狂欢就结束了,这样,视觉中心左右就得到了排序后的数字。
该算法的时间复杂度类似于选择排序– O(n2),但据说加速度为 30 %。

边缘状态

已经到了这个阶段,你可以想象一下碰撞的瞬间,比如当左光标的数字(最小的数字)指向列表中的最大的数字,那么最小的数字重新排列,重新排列最大数量的立即崩溃。因此,该算法的所有实现都包含检查此类情况并用正确的索引替换索引。在我的实现中,一次检查就足够了:

  maximalNumberIndex = minimalNumberIndex;
}

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

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

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

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

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

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

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

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

链接

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

来源

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

鸡尾酒调酒器分类

鸡尾酒调酒器分类–摇床排序,双向冒泡排序的一种变体。
该算法的工作原理如下:

  1. 选择循环中搜索的初始方向(通常是从左到右)
  2. 接下来在循环中成对检查数字
  3. 如果下一个元素更大,则交换它们
  4. 完成后,搜索过程会以相反的方向重新开始
  5. 重复搜索,直到没有更多的排列

该算法的时间复杂度与bubble类似– O(n2)

PHP 实现示例:

<?php

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

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

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

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

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

?>

Ссылки

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

Источники

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

胖男孩尺寸–用于显示文件夹和文件大小的实用程序

FatBoySize –用于显示终端中文件夹和文件大小的实用程序。
适用于任何支持 Python 3 的系统。

运行:python3 fbs.py
输出方式1:python3 fbs.py -v
输出方式2:python3 fbs.py --version

仅适用于终端中当前打开的路径。

结果示例:
python3 ~/Sources/my/fatboysize/fbs.py
.local-> 145.GB
下载-> 103.GB
.缓存-> 37.0 GB
.android-> 11.6 GB
来源-> 8.63 GB

正如您所看到的,下载文件夹非常sh但是很大

链接

https://gitlab.com/demensdeum/fatboysize/ p>

…And Primus for All

In this note I will describe the launch of Steam games on the Linux distribution Arch Linux in the configuration of an Intel + Nvidia laptop

Counter-Strike: Global Offensive

The only configuration that worked for me is Primus-vk + Vulkan.

Install the required packages:
pacman -S vulkan-intel lib32-vulkan-intel nvidia-utils lib32-nvidia-utils vulkan-icd-loader lib32-vulkan-icd-loader primus_vk

Next, add launch options for Counter-Strike: Global Offensive:
pvkrun %command% -vulkan -console -fullscreen

Should work!

Sid Meier’s Civilization VI

Works in conjunction – Primus + OpenGL + LD_PRELOAD.

Install the Primus package:
pacman -S primus

Next, add launch options for Sid Meier’s Civilization VI:
LD_PRELOAD='/usr/lib/libfreetype.so.6:/usr/lib/libbrotlicommon.so.1:/usr/lib/libbrotlidec.so.1' primusrun %command%

LD_PRELOAD pushes the Freetype compression and font libraries.

Dota 2

Works in conjunction – Primus + OpenGL + removal of locks at startup.

Install the Primus package:
pacman -S primus

Next, add launch options for Dota 2:
primusrun %command% -gl -console

If the game doesn’t start with fcntl(5) for /tmp/source_engine_2808995433.lock failed, then try deleting the /tmp/source_engine_2808995433.lock file
rm /tmp/source_engine_2808995433.lock
Usually the lock file is left over from the last game session unless the game was closed naturally.

How to check?

The easiest way to check the launch of applications on a discrete Nvidia graphics card is through the nvidia-smi utility:

For games on the Source engine, you can check through the game console using the mat_info command:

References

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

睡眠排序

睡眠排序–睡眠排序,确定性奇怪排序算法的另一个代表。

它的工作原理如下:

  1. 循环遍历元素列表
  2. 为每个循环启动一个单独的线程
  3. 线程休眠一段时间–元素值和睡眠后的值输出
  4. 循环结束时,等待线程最长的睡眠完成,显示排序后的列表

C 中睡眠排序算法的示例代码:

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

typedef struct {
    int number;
} ThreadPayload;

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

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

    int maximal = 0;
    pthread_t maximalThreadID;

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

在此实现中,我在微秒上使用了 usleep 函数,其值乘以 1000,即以毫秒为单位。
算法的时间复杂度– O(很长)

链接

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

来源

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