Category Archives: Techs

A Simple Image Hosting Solution Using FTP

Previously trying to use NextCloud and webdav as the way to upload and manage images, but it turns out that deal with share links of those images in NextCloud is not a easy thing to do, so I started to think another way. I found this project on GitHub called PicGo, which allows user toContinue reading “A Simple Image Hosting Solution Using FTP”

Gitea – Self-Hosted Git & CI/CD Tools

This article is about my deployment experience of Gitea, a self-hosted GitHub like code hosting service which also support CI/CD pipeline workflows like GitHub Action. Why I Need It Recently, I was searching for a way to host Obsidian vault on the Internet. There is an official way to achieve this using Obsidian Publish, however,Continue reading “Gitea – Self-Hosted Git & CI/CD Tools”

Simple Callback Function In C++

This article will discuss the basic practice of using callback functions in C++ Function Type To use function type as parameter, it’s recommended to use functional library to define function type: In the code snippet above: Use With Lambda It’s recommended to use Function Type with Lambda Expression: For more info about the C++ LambdaContinue reading “Simple Callback Function In C++”

Lambda Expression in C++

Lambda表达式是编程中很实用的工具，作为热门的，最受欢迎编程语言之一（大概？），C++11及其以后版本，也提供了对lambda表达式的支持，下面让我们逐步学习和了解C++中的Lambda表达式吧 首先我们先看一个lambda表达式的使用例子： 观察得到，C++ lambda表达式基本结构如下： 接下来我们将逐个部份进行介绍。 Capture Clause 首先是第一部份[]。这一部份被称之为捕获语句（Capture Clause）。在这一部份，你可以捕获lambda声明时范围内的变量。你可以在周围环境中捕获需要的变量，同时可以选择捕获类型为值传递还是引用传递。 默认情况下，Capture语句中捕获的变量将会以值传递形式传递。 需要注意，配置默认捕获模式将会将周围环境的所有变量暴露给lambda表达式。如上述代码，lambda c和d均设置了默认Capture设置，这种情况下，周围环境的所有变量都将会被Capture，c和d可以各自依照自己设定好的默认捕获模式访问到num2，但是a和b不能访问到num2。 同时，lambda表达式初始化时，也允许进行赋值操作，请看下面的代码。 如上述代码，我们可以在lambda表达式的 Capture Clause 部分声明新的变量。新的声明变量同样可以是值传递或者引用传递。需要注意的是，在 Capture Clause 声明变量时，我们无需显式指定变量类型，lambda表达式会自动推断其类型（如上述代码中，refToC自动被推断为 int & 类型） 还有一个需要注意的点，默认情况下，Capture Clause 中捕获和声明的所有变量将会以const形式进行传递。也就是说lambda body中，默认不可以对 Capture Clause 中的变量进行更改。如果您想在 lambda body 中对 Capture Clause 中的值或者引用进行更新或修改，请在参数列表，函数体前加上mutable关键字。

Sparse Table

ST表，全称 SparseTable，也叫做稀疏表。是用来解决区间和和区间最大最小值问题的一种工具。其实推广开来，其可以用来解决任何可重复贡献（associative）问题。 使用条件 可重复贡献问题 ST表要求其处理的问题必须具有“可重复贡献”这一特征。具体是什么意思呢？ 假设有操作F，使得其满足下列关系: 则称F符合可重复贡献问题的特征。 如图，不难发现max()最大值函数就符合可重复贡献问题的特征；读者可以自行验证，sum()，min()等函数都符合这个特征，这也证明了ST表可以解决最大最小值以及区间和等问题。 元数据可不能改变噢 在使用ST表解决问题时，我们必须确保所有的查询结束前，ST表所对应的元数据都不改变。 有些数据结构（比如线段树）在元数据更新之后（比如原来的数组中，某个数值由3变成了5），可以有对应的事件复杂度比较低的方法对结构进行更新，以达到一边更新一边查询的效果。ST表则无法提供类似的方法，所以确保你的问题中没有要求在查询期间动态调整元数据的要求。 SparseTable意义与使用 接下来，我们采用由表及里的过程，先了解ST表的意义以及使用方法，之后再来说明如何生成ST表。 一些准备——向下取整的Log2函数 由于SparseTable的特性，无论是根据数据生成ST表，还是得到ST表后对数据进行查询，都会比较频繁的用到向下取整的log2函数，所以特地说明。我们对于向下取整的log2运算稍加分析，可以得到log2(x)向下取整的具体意义是： 对于某一个数N，返回可能的最大的数字n，使得2的n次方小于等于N，且2的n+1次方必定大于N。 比如对于7，log2(7)向下取整为2，2的2次方不超过7，但可以保证2的3次方一定大于7（8>7）。 了解了这个之后，让我们来看看SparseTable如何快速解决规模庞大的可重复贡献问题吧~ ST表中数据的意义 我们接下来选择一个经典的可重复贡献问题——区间最大值问题，作为示例。 假设我们有一个数组 {3, 2, 1, 4, 5, 9, 7}, 其数据元素个数为7，要求必须在非常低的事件复杂度内，查询某个特定区间（比如从下标0到下标5）的最大值。此时，如果直接循环求解，会导致复杂度随着查询区间长度不断增高，这就是ST表登场的时候啦。 如上图，对数组进行处理之后，就可以得到下方的二维数组，也就是我们大名鼎鼎的SparseTable——ST表。那么问题来了，图中ST表中的数据，到底具有什么含义呢？ 首先需要知道的是，ST表正常情况下使用一个二维数组st[idx][pow]来储存。下面对这个二维数组每一个位置元素的意义做出解释： 例如，对于区间最大值问题，假设原数组为arr，处理后得到的ST表中，st[1][2] = 5，则说明：原数组，从下标为1开始，长度为2^2=4的区间内，最大值是5。 特定区间的查询 知道了ST表的数据的意义，我们就可以着手解决特定区间查询问题。 这里需要注意的是，虽然ST表可以解决不同的可重复贡献问题，但是其在面对不同的可重复贡献问题时，最优查询方式可能有一定的区别。接下来，我们先通过上方的“区间最大值”例子，介绍一下区间最值问题的ST表查询。 合适的长度 首先，为了降低时间复杂度，我们希望用尽可能少的区间查询来拼凑出完整答案。可以证明，在ST表处理区间最值问题时，无论区间长度位置，我们都可以用ST表支持的两个区间，拼接出答案。比如对于区间(1, 6)，可以由区间(1, 4)和区间(3, 6)区间的结果再求最值得到。对于“最值”问题，我们只需要保证选择的区间完整覆盖住所求区间，且不超过所求区间即可，而这多个区间允许有重复部分。 同时，为了保证所用区间尽可能少，每个区间就要尽可能大。这个时候，上方说到的log2向下取整计算就派上用场了。由于ST表代表的区间长度只能是2的n次方倍，所以，不超过区间范围的区间，其最长长度就是log(区间长度)向下取整。 比如对于(1,6)区间进行最值计算，log2(6)向下取整=2。说明只需要在合适的位置，用两个长度为2^2=4的区间覆盖即可。这代表了，我们要取的数据肯定在ST[idx][2]内——我们确定了pow。 合适的位置 我们已经知道了，只要位置安排合理，我们肯定能用两个长度为4的区间覆盖住(1, 6)，那么这两个区间的位置，应该如何选择呢？ 思考之后发现，我们肯定希望： 如上图，最终，我们可以得到： 我们对这两个区间的最大值再求一次最大值即可，最终答案为max(5, 9) = 9。 如果用ST表来计算，运算过程如下： 是时候该自己实现ST表啦Continue reading “Sparse Table”

Bellman Ford Shortest Path

开始之前 本Blog之前已经介绍过一种单源最短路算法——Dijkstra算法。但Dijkstra算法也有着自己的缺点，其中最明显的问题就是无法处理带负权边的图，其原因与其算法中包含的贪心原理有关。 而接下来介绍的算法，则拥有处理负权边的能力，该算法就是Bellman Ford单源最短路算法。该算法的核心思想是，对图中的每条边，都进行足够次数的Relaxation（松弛）操作，从而逐步推导出每个点距离出发点都最短路径长度。 关于Bellman Ford算法的原理和代码实现，网络中已有大量优秀的资料，这里便不再说明算法本身的详细工作流程。接下来着重说明一些Bellman Ford算法中一些限制条件，及其相关的一些理解。 Bellman Ford算法特性 当出现负权回路时… 在通过Bellman Ford算法计算单源最短路时，会要求所计算的图中不得存在权值为负值的回路。这个限制相对较好理解，下面举一个简单的例子。 如图，图中的A->B->C->A便是一个负权回路。而假设我们现在需要以A点作为出发点计算最短距离，请问A->D的最短距离应该是多少？不难发现这里出现了死循环。我们可以从原点出发，不停的走A->B->C->A这条路，每循环一次，我们距离出发点的距离就会越来越小。这也就意味着，只要我们的路径不断的在负权回路中重复足够多次，每一个点距离出发点的距离都可以认为是无穷小，这显然是不合理的。 负权回路对于图来说是存在特殊意义的，比如在经济学的部分领域中，“负权回路”是一个非常具有吸引力的词，因为可能代表着可持续的收益链，也可以代表着套利的机会，但Bellman Ford不认这些，在单元最短路算法的世界中，我们暂且不接受“套利机会”的存在。也就是说我们不允许待处理的图中出现负权回路，以此来保证计算结果是有意义的。 对于Bellman Ford算法的一些理解 迭代次数的理解 Bellman Ford算法的核心思想，在于每迭代一次，就对所有边进行遍历，并执行Relaxation操作。这里不难发现，迭代k次时，得到的结果，可以保证至少是路径条数为k时的最优解。 为什么说是至少呢，因为其遍历的结果可能跟边遍历的顺序有关，如下图： 如图，我们发现对于图中的无向图，如果从左边的边开始遍历，实际上遍历一次之后我们就已经得到了最优解。而如果从右边开始遍历，我们就需要遍历3次才能得到最优解。 按照这个思路理解，不难推出，遍历k次时，得到的答案，只能保证，至少是路径条数为k限制下的最优解。 这里对路径条数做出说明，一个路径由多个边组成，上方所说的“路径条数”，指的是对于某条路径，其经过的边的个数的和。 为什么迭代次数等于点的个数？ 上方我们已经论述了迭代次数k的意义，迭代k次时，得到的结果至少是路径条数k情况下的最优解，部分点的数据可能比会更优，但对于所有的点，只能保证其为路径条数k情况下的最优解。 那么我们到底需要迭代几次呢？根据定义，我们将问题转换成为：对于一个无向图，其某个点A到某个点B的全局最优路径中，最多可能经过几条边。 经过思考之后发现，最坏情况下，最优路径将会不重复的经过所有点。接下来对这个结论进行简单的说明： 首先是经过所有点。如果我们想要强迫最优路径经过尽可能多的点，最坏的情况之一，便是这个图形成了一个没有分叉的纯线性结构（就像上方对于迭代次数解释时所用图一样，每两个点用一条边链接，总边数为点数-1），这样从最左边到最右边的点，最优路径边毋庸置疑是经过所有的点。 其次是不重复。为什么我们可以确保最优路径中不会重复经过同一个点呢？这从某个角度上来说得益于算法前面的一个前提条件——不允许负权回路。想象一下，如果路径重复经过了同一个点，说明这个路径必定存在一段回路（从重复点出发，经过某个路径，又回到重复点）。而此时如果这个回路确定不是负权回路，那么说明如果跳过这段回路，我们可以得到一个权重更短的路径，反向说明了目前的路径不是最优路径。因而可以确定，如果一个路径被确定为最优路径，且该图中没有负权回路，那么这个路径绝对不会重复经过同一个点。 说明完毕，接下来让我们看看这两个结论，不难发现，不重复经过所有点，那么对于一个点个数为N的图，符合条件的路径，最长只能是N-1（因为一旦大于N-1，说明必定要产生回路，与条件冲突），所以最终确定，如果需要得到全局最优，其最少迭代次数为N-1。 综上所述，容易得到，算法的时间复杂度为O(N*M)。其中，N为点的个数，M为边的个数。 为什么它能攻克负权边？ 在Dijkstra算法的文章中，笔者提到了一个观点，Dijkstra的核心是基于贪心的，而贪心带来了局部最优解这一隐患。带着这个角度再来看Bellman Ford算法，是否有一种熟悉的感觉？Bellman Ford算法的每次迭代都基于上一次的迭代结果。先知道路径条数1情况下的最优解，再根据此状态推出条数2情况下的解，以此类推最终得到路径条数为N-1时的最优解（也就是全局最优解），是不是有点「动态规划」的味道了呢？正是借助这这种工作模式，不像Dijkstra算法一样看到一点点甜头就着急的把点Close掉，Bellman Ford拥有了不被眼前甜美假象迷惑的能力，坚持着自己的本分，不断想着正确的道路一步步迈进，最终终于得到了令人满意的结果。 相关链接 GeeksForGeeks Bellman Ford算法介绍（英文） 「编程笔记」Dijkstra算法为什么无法处理带有负权边的图