实际上没有福尔马林的框图

框图是一种视觉工具,有助于将复杂的算法转变为可理解且结构化的动作序列。从编程到业务流程管理,它们是一种可视化,分析和优化最复杂系统的通用语言。

想象一下一张地图,而不是道路是逻辑,而不是城市 – 行动。这是一个框图 – 在最令人困惑的过程中导航的必不可少的工具。

示例1:简化的游戏启动方案
要了解工作原理,让我们提出一个简单的游戏发布计划。

当一切都没有失败时,该方案显示了完美的脚本。但是在现实生活中,一切都更加复杂。

示例2:扩展的方案用于使用数据加载开始游戏
现代游戏通常需要互联网连接才能下载用户数据,保存或设置。让我们将这些步骤添加到我们的计划中。

该方案已经更现实,但是如果出现问题,会发生什么?

怎么样:一款“破产”的游戏,失去了互联网

在项目开始时,开发人员无法考虑所有可能的情况。例如,他们专注于游戏的主要逻辑,并且不认为如果玩家具有互联网连接会发生什么。

在这种情况下,其代码的框图看起来像这样:

在这种情况下,该游戏在等待数据的阶段冻结了,而不是由于缺乏连接而无法收到的数据,而不是发出错误或关闭。这导致了“黑屏”并冻结了应用程序。

如何变成:用户投诉纠正

在许多用户对徘徊的投诉之后,开发人员团队意识到我们需要纠正错误。他们通过添加错误处理单元来更改代码,该单元允许应用程序正确响应缺乏连接。

这就是校正的框图的外观,其中两个方案都被考虑:

借助这种方法,游戏现在正确地通知了用户有关问题的信息,在某些情况下,它甚至可以进入离线模式,从而使您可以继续游戏。这是一个很好的例子,说明了为什么框图如此重要:他们使开发人员不仅考虑了理想的执行方式,而且还考虑了所有可能的失败,从而使最终产品更加稳定和可靠。

不确定的行为

悬挂和错误只是该程序不可预测行为的一个例子。在编程中,存在一个不确定行为(不确定的行为)的概念 – 这是语言标准无法描述程序在某种情况下应如何行为的情况。

这可能会导致任何事情:从撤回的随机“垃圾”到程序的失败甚至严重的安全漏洞。例如,使用内存时,通常会发生不确定的行为。

语言C的一个示例:

想象一下,开发人员将线路复制到缓冲区中,但忘了添加到零符号(`\ 0`)的端,该符号标记了线路的末端。

这就是代码的样子:

#include 

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

memcpy(buffer, my_string, 5);

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

预期结果:“你好”
真正的结果是不可预测的。

为什么会发生这种情况?使用指定符的“ printf”函数期望该行以零符号结束。如果他不是,她将继续阅读突出显示的缓冲区之外的记忆。

这是此过程的框图,并具有两个可能的结果:

这是一个明显的例子,说明了框图如此重要的原因:它们使开发人员不仅考虑了理想的执行方式,而且还考虑了所有可能的失败,包括如此低级的问题,使最终产品更加稳定和可靠。

Pixel Perfect:在声明性时代的神话还是现实?

在界面开发的世界中,有一个共同的概念 – “小屋中的像素完美” 。它意味着设计机对最小像素的最准确再现。很长一段时间以来,它一直是黄金标准,尤其是在经典的网页设计时代。但是,随着声明性英里的到来和各种设备的快速增长,“ Pixel Perfect”的原理变得越来越短暂。让我们尝试找出原因。

帝国wysiwyg vs.声明守则:有什么区别?

传统上,许多接口,尤其是桌面,是使用命令式方法或编辑器的Wysiwyg(您看到的)创建的。在这样的工具中,设计师或开发人员直接用元素来操纵,将它们放在画布上,以准确的像素。它类似于使用图形编辑器 – 您会看到元素的外观,并且肯定可以将其定位。在这种情况下,“ Pixel Perfect”的成就是一个非常真实的目标。

但是,现代发展越来越基于声明性里程。这意味着您不告诉计算机“在此处放这个按钮”,而是要描述您想要获得的内容。例如,您没有指示元素的特定坐标,而是描述其属性:“此按钮应为红色,从各个方面有16px的凹痕,并且位于容器的中心。”像React,Vue,Swiftui或JetPack一样,只需使用此原理即可。

为什么“ Pixel Perfect”不适合许多设备的声明英里

想象一下,您创建了一个在iPhone 15 Pro Max,Samsung Galaxy Fold,iPad Pro和4K分辨率上看起来同样不错的应用程序。这些设备中的每一个都有不同的屏幕分辨率,像素密度,派对和物理大小。

当您使用声明性方法时,系统本身会考虑其所有参数在特定设备上显示您所描述的接口。您设置规则和依赖性,而不是苛刻的坐标。

* 适应性和响应能力:声明英里的主要目标是创建自适应和响应式接口。这意味着您的接口应自动适应屏幕的大小和方向,而不会破坏和保持可读性。如果我们试图在每个设备上“像素完美”,则必须为同一界面创建无数的选项,这将完全阐明声明方法的优势。
* 像素密度(DPI/PPI):设备具有不同的像素密度。如果您不考虑缩放率,则具有高密度的设备上的100个“虚拟”像素的尺寸将比低密度设备上的元素小得多。声明的框架是通过物理像素抽象的,与逻辑单元一起工作。
* 动态内容:现代应用程序中的内容通常是动态的 – 其体积和结构可能会有所不同。如果我们用力地将像素破烂,文本或图像的任何更改都会导致布局的“崩溃”。
* 各种平台:除了各种设备之外,还有不同的操作系统(iOS,Android,Web,桌面)。每个平台都有自己的设计,标准控件和字体。尝试在所有平台上制作绝对相同的Pixel完美界面的尝试将导致不自然的类型和差的用户体验。

旧方法没有消失,而是进化了

重要的是要了解,接口的方法不是“命令”和“声明性”之间的二元选择。从历史上看,对于每个平台,都有自己的工具和方法来创建接口。

* 本机接口文件: iOS是xib/故事板,用于android-xml标记文件。这些文件是一个完美的Wysiwyg布局,然后像编辑器一样在广播中显示。这种方法并没有在任何地方消失,它继续发展,并与现代宣言框架集成。例如,苹果和Jetpack的Swiftui在Android中构成了纯粹的声明代码的道路,但同时保留了使用经典布局的机会。
* 混合解决方案:经常在实际项目中,使用多种方法。例如,可以声明地实现应用程序的基本结构,并且对于需要准确的元素定位,可以使用较低的,命令式方法或开发的本机组件,以考虑到平台的细节。

从整体到适应性:设备的演变如何形成声明英里

在过去的几十年中,数字界面的世界发生了巨大变化。从具有固定许可证的固定计算机来看,我们来到了各种用户设备的指数增长的时代。今天,我们的应用程序应该同样擅长:

* 智能手机的所有形式和屏幕尺寸的大小。
* 平板电脑具有独特的方向模式和一个分开的屏幕。
* 笔记本电脑和台式机具有各种监视器的许可。
* 电视和媒体中心,远程控制。值得注意的是,即使对于电视,它的备注也很简单,因为 Apple TV Remote 具有最少的按钮,反之亦然,但具有许多功能,对接口的现代要求也不应需要对这些输入功能进行特定的适应。该接口应“好像自身”工作,而不必对与特定遥控器进行交互的“如何”相互作用。
* 智能手表和可穿戴设备带有简约屏幕。
* 虚拟现实头盔(VR),需要一种全新的空间接口方法。
* 增强现实设备(AR),应用有关现实世界的信息。
* 汽车信息和娱乐系统
*甚至是家用电器:从带有感官屏幕和带有交互式显示器的洗衣机到智能烤箱和智能房屋系统的冰箱。

这些设备中的每一个都有其独特的功能:物理维度,派对比率,像素密度,输入方法(触摸屏,鼠标,控制器,手势,声乐命令),以及用户环境的微妙之处。例如,VR Shlesh需要深层沉浸,并且在旅途中进行了智能手机的快速和直观的工作,而冰箱界面应像快速导航一样简单而大。

经典方法:支撑各个接口的负担

在台式机和第一个移动设备的主导时代,通常的业务是对单个接口文件的创建和支持,甚至是每个平台的完全独立的接口代码。

* ios 下的开发通常需要在Xcode中使用故事板或XIB文件,在Objective-C或Swift上编写代码。
*对于 android ,创建了XML标记文件和Java或Kotlin上的代码。
* Web接口打开了HTML/CSS/JavaScript。
*对于 c ++应用程序在各种桌面平台上,使用了它们的特定框架和工具:
*在 Windows 中,这些是MFC(Microsoft Foundation类),带有手动绘制元素的Win32 API或使用资源文件用于对话框Windows和Control Elements。
*可可(Objective-C/Swift)或用于直接控制图形界面的旧碳API。
*在 linux/unix样系统中,经常使用诸如GTK+或QT之类的库,这些库通常通过类似XML的标记文件(例如,QT Designer中的.UI文件)或直接的软件创建元素来提供其用于创建接口的小部件和机制。

这种方法可确保对每个平台的最大控制,从而使您可以考虑其所有特定功能和本机元素。但是,他有一个巨大的缺点:重复的努力和支持的巨大成本。设计或功能的最小变化需要引入几个独立代码库的权利。对于开发人员团队来说,这变成了真正的噩梦,减慢了新功能的输出并增加了错误的可能性。

声明英里:多样性的单一语言

正是为了回应这种快速的并发症,声明性的里程似乎是主要的范式。像 React,Vue,Swiftui,JetPack构成之类的Framws不仅是编写代码的新方法,而且是思维的根本转变。

声明性方法的主要思想:我们没有说“如何”绘制每个元素(势在必行),而是描述了“我们想看到的(声明性)。我们设置了接口的属性和条件,框架决定如何最好地在特定设备上显示它。

由于以下主要优势,这可能是可能的:

1。从平台的详细信息中抽象:声明的fraimvorki专门设计为忘记每个平台的低级别详细信息。开发人员使用单个传输的代码以更高的抽象级别描述了组件及其关系。
2。自动适应性和响应能力: freimvorki负责自动缩放,将元素的布局和适应性更改为不同尺寸的屏幕,像素密度和输入方法。这是通过使用灵活布局系统(例如Flexbox或Grid)以及类似于“逻辑像素”或“ DP”的概念来实现的。
3。用户体验的一致性:尽管存在外部差异,但声明的方法使您可以在整个设备家族中维护行为和交互的单一逻辑。这简化了测试过程,并提供了更可预测的用户体验。
4。开发和降低成本的加速:具有能够在许多平台上工作的相同代码,大大减少了发展和支持的时间和成本。团队可以专注于功能和设计,而不是重复重写相同的接口。
5。未来的准备就绪:从当前设备的细节中抽象的能力使声明代码更具对新型设备和形式因素的出现的抵抗力。可以更新Freimvorki以支持新技术,并且您已经编写的代码将获得此支持相对无缝。

结论

声明的英里不仅是一种时尚趋势,而且是由用户设备快速开发(包括物联网(IoT)和智能家用电器)引起的必要进化步骤。它允许开发人员和设计师创建复杂,自适应和统一的接口,而不会淹没每个平台的无尽特定实现。从对每个像素的命令控制到所需状态的声明性描述的过渡是一种认识,即在未来的世界中,无论显示哪种屏幕,都应灵活,传递和直观

程序员,设计师和用户需要学习如何生活在这个新世界。 Pixter Perfect的额外细节,设计为特定设备或分辨率,导致不必要的时间成本进行开发和支持。此外,这种刺激性的布局可能根本无法在具有非标准界面的设备上使用,例如有限的输入电视,VR和AR Shifts以及未来的其他设备,我们仍然不知道今天。灵活性和适应性 – 这些是创建现代世界中成功接口的关键。

Vibe核心技巧:为什么LLM仍然无法与固体,干燥和干净一起使用

随着大型语言模型(LLM)的开发,例如ChatGpt,越来越多的开发人员使用它们来生成代码,设计体系结构和加速集成。但是,通过实用的应用,它变得明显:建筑的经典原理 – 固体,干燥,清洁 – 与LLM Codgendation的特殊性相同。

这并不意味着原理已经过时了 – 相反,它们与手动开发完美合作。但是使用LLM,必须适应该方法。

为什么LLM无法应对建筑原理

封装

不合时间需要了解系统部分之间的界限,对开发人员意图的知识以及严格的访问限制。 LLM通常会简化结构,无缘无故地公开字段或重复实现。这使得代码更容易受到错误的影响,并违反了架构边界。

摘要和接口

设计模式,例如抽象工厂或策略,需要对系统的整体视图并了解其动态。模型可以在没有明确目的的情况下创建一个界面,而无需确保其实现或违反层之间的连接。结果是过量或非功能架构。

干(托管重复自己)

LLM不要寻求最大程度地减少重复代码 – 相反,与制作一般逻辑相比,他们更容易复制块。尽管他们可以根据要求提供重构,但默认模型倾向于生成“自给自足的”片段,即使它导致冗余。

干净的体系结构

清洁意味着严格的层次结构,远离框架,定向依赖性以及层之间的最小连接性。这样的结构的产生需要对系统的全球理解,而llm则以单词概率而不是建筑完整性的含义来起作用。因此,该代码混合在一起,违反了依赖的方向和简化的划分。

使用LLM 时效果更好

湿而不是干
在与LLM合作时,湿(写两次)方法更为实用。代码的重复不需要保留模型中的上下文,这意味着结果是可以预测的,并且更易于正确纠正。它还减少了非明显连接和错误的可能性。

此外,重复有助于补偿模型的短记忆:如果在多个地方发现了某些逻辑片段,LLM更有可能将其考虑到进一步的生成中。这简化了伴奏,并增加了对“忘记”的抵制。

简单结构而不是封装

避免复杂的封装并依靠代码部分之间的数据直接传输,您可以大大简化生成和调试。通过快速的迭代开发或MVP的创建,尤其如此。

简化体系结构

该项目的简单,平坦的结构具有最少的依赖性和抽象,从而在生成过程中产生了更稳定的结果。该模型可以更轻松地调整这样的代码,并且较少违反了组件之间的预期连接。

SDK集成 – 手动可靠

大多数语言模型接受过过时的文档版本培训。因此,当生成用于安装SDK的指令时,通常会出现错误:过时的命令,无关参数或链接到无法访问的资源。实践显示:最好使用官方文档和手动调整,而LLM则是辅助角色 – 例如,生成模板代码或配置的改编。

为什么原理仍然有效 – 但是手动开发

重要的是要了解,固体,干燥和清洁的困难与LLM有关的CODHENELISERALION。当开发人员手动编写代码时,这些原则继续证明其价值:它们降低了连接性,简化支持,提高项目的可读性和灵活性。

这是由于人类思维容易概括的事实。我们正在寻找模式,将重复的逻辑带入单个实体,创建模式。可能,这种行为具有进化的根源:减少信息量可节省认知资源。

LLM的行为不同:他们没有从数据量中体验到负载,也不会努力储蓄。相反,与构建和维护复杂的抽象相比,他们更容易使用重复的,分散的信息。这就是为什么他们更容易在没有封装的情况下应对代码,重复结构和最小的架构严重性。

结论

大型语言模型是开发中的有用工具,尤其是在早期或创建辅助代码时。但是,重要的是要适应它们的方法:为了简化体系结构,限制抽象,避免复杂的依赖关系,并且在配置SDK时不依赖它们。

固体,干燥和清洁的原则仍然是相关的,但它们在人的手中赋予了最佳效果。使用LLM时,使用简化的实用风格是合理的,该样式使您可以获取可靠且易于理解的代码,该代码易于手动完成。 LLM忘记的地方 – 复制代码可以帮助他记住。

将 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

在 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 按键,从而打开/关闭键盘上的背光。

树排序

树排序——使用二叉搜索树进行排序。时间复杂度– 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