1.STL 源码剖析：sort
2.腾讯T2I-adapter源码分析（1）-运行源码跑训练

STL 源码剖析：sort

       我大抵是太闲了。

       更好的阅读体验。

       sort 作为最常用的 STL 之一，大多数人对于其了解仅限于快速排序。

       听说其内部实现还包括插入排序和堆排序，于是租赁溯源码很好奇，决定通过源代码一探究竟。

       个人习惯使用 DEV-C++，不知道其他的编译器会不会有所不同，现阶段也不是很关心。

       这个文章并不是析完之后的总结，而是边剖边写。不免有个人的猜测。而且由于本人英语极其差劲，大抵会犯一些憨憨错误。

       源码部分sort

       首先，在 Dev 中输入以下代码：

       然后按住 ctrl，鼠标左键sort，就可以跳转到头文件 stl_algo.h，并可以看到这个：

       注释、模板和函数参数不再解释，我们需要关注的是函数体。

       但是，中间那一段没看懂……

       点进去，是超连接源码一堆看不懂的#define。

       查了一下，感觉这东西不是我这个菜鸡能掌握的。

       有兴趣的 戳这里。

       那么接下来，就应该去到函数__sort 来一探究竟了。

       __sort

       通过同样的方法，继续在stl_algo.h 里找到 __sort 的源代码。

       同样，只看函数体部分。

       一般来说，sort(a,a+n) 是对于区间 [公式] 进行排序，所以排序的前提是 __first != __last。

       如果能排序，那么通过两种方式：

       一部分一部分的看。

       __introsort_loop

       最上边注释的翻译：这是排序例程的帮助程序函数。

       在传参时，除了首尾迭代器和排序方式，还传了一个std::__lg(__last - __first) * 2，对应 __depth_limit。

       while 表示，当区间长度太小时，不进行排序。

       _S_threshold 是一个由 enum 定义的数，好像是uml前端源码叫枚举类型。

       当__depth_limit 为 [公式] 时，也就是迭代次数较多时，不使用 __introsort_loop，而是使用 __partial_sort（部分排序）。

       然后通过__unguarded_partition_pivot，得到一个奇怪的位置（这个函数的翻译是无防护分区枢轴）。

       然后递归处理这个奇怪的位置到末位置，再更新末位置，继续循环。

       鉴于本人比较好奇无防护分区枢轴是什么，于是先看的__unguarded_partition_pivot。

       __unguarded_partition_pivot

       首先，找到了中间点。

       然后__move_median_to_first（把中间的数移到第一位）。

       最后返回__unguarded_partition。

       __move_median_to_first

       这里的中间数，并不是数列的中间数，而是三个迭代器的中间值。

       这三个迭代器分别指向：第二个数，中间的数，最后一个数。

       至于为什么取中间的数，暂时还不是很清楚。

       `__unguarded_partition`

       传参传来的彩票站点源码序列第二位到最后。

       看着看着，我好像悟了。

       这里应该就是实现快速排序的部分。

       上边的__move_median_to_first 是为了防止特殊数据卡 [公式] 。经过移动的话，第一个位置就不会是最小值，放在左半序列的数也就不会为 [公式] 。

       这样的话，__unguarded_partition 就是快排的主体。

       那么，接下来该去看部分排序了。

       __partial_sort

       这里浅显的理解为堆排序，至于具体实现，在stl_heap.h 里，不属于我们的讨论范围。

       （绝对不是因为我懒。）

       这样的话，__introsort_loop 就结束了。下一步就要回到 __sort。

       __final_insertion_sort

       其中某常量为enum { _S_threshold = };。

       其中实现的函数有两个：

       __insertion_sort

       其中的__comp 依然按照默认排序方式 < 来理解。

       _GLIBCXX_MOVE_BACKWARD3

       进入到_GLIBCXX_MOVE_BACKWARD3，是一个神奇的 #define：

       其上就是move_backward：

       上边的注释翻译为：

       __unguarded_linear_insert

       翻译为“无防护线性插入”，应该是网站选项源码指直接插入吧。

       当__last 的值比前边元素的值小的时候，就一直进行交换，最后把 __last 放到对应的位置。

       __unguarded_insertion_sort

       就是直接对区间的每个元素进行插入。

       总结

       到这里，sort 的源代码就剖完了（除了堆的那部分）。

       虽然没怎么看懂，但也理解了，sort 的源码是在快排的基础上，通过堆排序和插入排序来维护时间复杂度的稳定，不至于退化为 [公式] 。

       鬼知道我写这么多是为了干嘛……

腾讯T2I-adapter源码分析（1）-运行源码跑训练

       稳定扩散、midjourney等AI绘图技术，为人们带来了令人惊叹的效果，不禁让人感叹技术发展的日新月异。然而，AI绘图的可控性一直不是很好，通过prompt描述词来操控图像很难做到随心所欲。为了使AI绘制的图像更具可控性，Controlnet、T2I-adapter等技术应运而生。本系列文章将从T2I-adapter的源码出发，分析其实现方法。

       本篇是第一篇，主要介绍源码的运行方法，后续两篇将以深度图为例，分别分析推理部分和训练部分的代码。分析T2I-Adapter，也是为了继续研究我一直在研究的课题：“AI生成同一人物不同动作”，例如：罗培羽：stable-diffusion生成同一人物不同动作的尝试（多姿势图），Controlnet、T2I-adapter给了我一些灵感，后续将进行尝试。

       T2I-Adapter论文地址如下，它与controlnet类似，都是在原模型增加一个旁路，然后对推理结果求和。

       T2I-Adapter和controlnet有两个主要的不同点，从图中可见，其一是在unet的编码阶段增加参数，而controlnet主要是解码阶段；其二是controlnet复制unit的上半部结构，而T2I-Adapter使用不同的模型结构。由于采用较小的模型，因此T2I-Adapter的模型较小，默认下占用M左右，而controlnet模型一般要5G空间。

       首先确保机器上装有3.6版本以上python，然后把代码clone下来。随后安装依赖项，打开requirements.txt，可以看到依赖项的内容。然后下载示例，下载的会放到examples目录下。接着下载sd模型到model目录下，再下载T2I-Adapter的模型到目录下，模型可以按需到huggingface.co/TencentA...下载。这里我下载了depth和openpose。sd模型除了上述的v1-5，也还下载了sd-v1-4.ckpt。

       根据文档，尝试运行一个由深度图生成的例子，下图的左侧是深度图，提示语是"desk, best quality, extremely detailed"，右侧是生成出来的。运行过程比较艰辛，一开始在一台8G显存的服务器上跑，显存不够；重新搭环境在一台G显存的服务器上跑，还是不够；最后用一台G显存的服务器，终于运行起来了。

       接下来尝试跑openpose的例子，下图左侧是骨架图，提示词为"Iron man, high-quality, high-res"，右侧是生成的图像。

       既然能跑推理，那么尝试跑训练。为了后续修改代码运行，目标是准备一点点数据把训练代码跑起来，至于训练的效果不是当前关注的。程序中也有训练的脚步，我们以训练深度图条件为例，来运行train_depth.py。

       显然，习惯了，会有一些问题没法直接运行，需要先做两步工作。准备训练数据，分析代码，定位到ldm/data/dataset_depth.py，反推它的数据集结构，然后准备对应数据。先创建文件datasets/laion_depth_meta_v1.txt，用于存放数据文件的地址，由于只是测试，我就只添加两行。然后准备，图中的.png和.png是结果图，.depth.png和.depth.png是深度图，.txt和.txt是对应的文本描述。

       文本描述如下，都只是为了把代码跑起来而做的简单设置。设置环境变量，由于T2I-Adapter使用多卡训练，显然我也没这个环境，因此要让它在单机上跑。而代码中也会获取一些环境变量，因此做简单的设置。

       做好准备工作，可以运行程序了，出于硬件条件限制，只能把batch size设置为1。在A显卡跑了约8小时，完成，按默认的配置，模型保存experiments/train_depth/models/model_ad_.pth。那么，使用训练出来的模型试试效果，能生成如下（此处只是为了跑起来代码，用训练集来测试），验证了可以跑起来。

       运行起来，但这还不够，我们还得看看代码是怎么写法，下一篇见。

       PS：《直观理解AI博弈原理》是笔者写的一篇长文，从五子棋、象棋、围棋的AI演进讲起，从深度遍历、MAX-MIN剪枝再到蒙特卡罗树搜索，一步步介绍AI博弈的原理，而后引出强化学习方法，通俗易懂地介绍AlphaGo围棋、星际争霸强化学习AI、王者荣耀AI的一些强化学习要点，值得推荐。

       AUTOMATIC的webui是近期很流行的stable-diffusion应用，它集合stable-diffusion各项常用功能，还通过扩展的形式支持controlnet、lora等技术，我们也分析了它的源码实现，写了一系列文章。