[算法]并查集以及优化 这是Wikipedia中对并查集的介绍：在计算机科学中，并查集（英文：Disjoint-set data structure，直译为不交集数据结构）是一种数据结构，用于处理一些不交集（Disjoint sets，一系列没有重复元素的集合）的合并及查询问题。并查集支持如下操作：查询：查询某个元素属于哪个集合，通常是返回集合内的一个“代表元素”。这个操作是为了判断两个元素是否在同一个集合之中。合并：将两个集合合并为一个。添加：添加一个新集合，其中有一个新元素。添加操作不如查询和合并操作重要，常常被忽略。由于支持查询和合并这两种操作，并查集在英文中也被称为联合-查找数据结构（Union-find data structure）或者合并-查找集合（Merge-find set）。“并查集”可以用来指代任何支持上述操作的数据结构，但是一般来说，“并查集”特指其中最常见的一种实现：不交集森林（Disjoint-set forest）。经过优化的不交集森林有线性的空间复杂度（O(n)，n为元素数目，下同），以及接近常数的单次操作平均时间复杂度(O(log*(n)),log*(n)为反阿克曼函数）)是效率最高的常见数据结构之一。并查集是用于计算最小生成树的克鲁斯克尔演算法中的关键。由于最小生成树在网络路由等场景下十分重要，并查集也得到了广泛的引用。此外，并查集在符号计算，寄存器分配等方面也有应用。{dotted startColor="#ff6c6c" endColor="#1989fa"/}基本并查集首先从最简单的开始，我们先完成并查集查询，合并和添加的操作。表示一般我们使用树的形式表达一个并查集集合。大概就像这样这里有两个集合，以0为根节点的，以5为根节点的。添加添加操作MakeSet(x)添加一个元素x，这个元素单独属于一个仅有它自己的集合。在不交集森林中，添加操作仅需将元素标记为根节点。首先，为了简单理解我这里使用一个数组表示出并查集的节点。int djs[100];我们要保留它的数据，还要保留它的根节点，所以在这里，我们简单定义成这样。MakeSet函数里对节点初始化，让root指向自己。void MakeSet(int x) { djs[x] = x; }查询在不交集森林中，每个集合的代表即是集合的根节点。查询操作Find(x)从x开始，根据节点到父节点的引用向根行进，直到找到根节点。这段代码也很简单：int Find(int x) { if(djs[x] == x) return x; return Find(djs[x]); }合并合并操作Union(x, y)把元素x所在的集合与元素y所在的集合合并为一个。合并操作首先找出节点x与节点y对应的两个根节点，如果两个根节点其实是同一个，则说明元素x与元素y已经位于同一个集合中，否则，则使其中一个根节点成为另一个的父节点。用图来说就是在将图1对以0为根节点与以3为根节点的集合合并后就会变成图2代码这样写：void Union(int x, int y) { djs[Find(y)] = djs[Find(x)]; }好了现在你已经学会并查集了，做一下这道题吧Islands优化上边这些代码好吗？他不好，因为在最坏情况下会Union成一条链，这时候Find操作是O(n)的{0,0,1,2,3,4,...}对这种情况我们肯定是要优化他的，优化肯定是从Union入手了，常见的优化方法有两种，一种是根据权重，另一种是根据树的深度，这时候情况就有点复杂了，无论是权重还是深度，显然都不是一个数组就能解决的了的，所以我们可以再引入一个数组来保存。下边以权重为例1int djs[100]; int power[100]; void MakeSet(int x) { djs[x] = x; power[x] = 1; } int Find(int x) { if(djs[x] == x) return x; return Find(djs[x]); } void Union(int x, int y) { int a = Find(y); int b = Find(x); if(power[a] < power[b]) std::swap(a,b); djs[a] = djs[b]; power[a] += power[b]; }这样就可以通过权重选择合并的树了，这时候查找达到了O(log(n))的。难道这就是极限？还记得刚开始提到的反阿克曼函数吗？它的优化可以达到什么地步呢？2^65535 的数据均摊也只需要五步就可以找到他的根节点！这就是通过路径压缩算法实现的。路径压缩对于这样的一颗树，我现在执行了查找7的根节点的操作我们在Find(7)的时候都经过了哪些节点？（7,6,5,0），如下：这时候我让这条路径所有节点的根节点都之间变成根节点0，就成了这样这时候，下次再查这条路径上的节点的根节点的时候，都只需一步就可查出结果。代码实现我选择新建vector来保存，只要修改一下Find就好了。std::vector<int> temp; int Find(int x) { temp.push_back(x); if(djs[x] == x) return x; int root = Find(djs[x]); for(int v : temp) { djs[v] = root; } temp.clear(); return root; }无论是根据权重还是根据深度，最后优化下来的结果都是O(log(n))的，权重写起来也更简单 ↩

[算法]堆排序 堆排序我是跟着这个视频学习然后自己实现了一下算法，视频已经讲的很清楚了，我就不多说了{bilibili bvid="BV1AF411G7cA" page=""/}{dotted startColor="#ff6c6c" endColor="#1989fa"/}建堆堆排序顾名思义，要在堆上排序，堆是一种完全二叉树，分大根堆小根堆，我们现在只讲一种，就是小根堆建堆，小根堆用自顶而下建堆法，在建堆之前我们写好上滤、下滤操作。我的实现是用数组，根节点从下标1开始，这样可以保证一个节点int(index/2)就能得到它的父节点下滤就是跟子节点比较，然后交换或者退出操作。index就是需要执行操作的下标，size就是当前堆节点数void UpToDown(int a[], unsigned int index, size_t size) // 下滤 { int maxindex; // maxindex用来储存a[index]的最大子节点 do // 既然选择执行下滤那么index一定不在最底层，所以至少执行一次下滤 { maxindex = 2 * index; if (maxindex + 1 < size && a[maxindex + 1] > a[maxindex]) // 首先得保证读数据不会内存溢出吧 maxindex++; if (a[index] < a[maxindex]) swap(a[index], a[maxindex]); else break; index = maxindex; } while (index < size / 2); }与下滤对应的是上滤，就是跟父节点比较。void DownToUp(int a[], unsigned int index) // 上滤 { int faindex = index / 2; do { if (a[index] > a[faindex]) swap(a[index], a[faindex]); else break; index /= 2; faindex = index / 2; } while (faindex > 0); }代码都很简单，就不详细说了。实现了上滤、下滤，剩下的就是建堆了，至于建大根堆还是小根堆看你自己意愿。void BuildHeap(int a[], size_t size) // 自顶而下建堆法 { if (size < 3) return; for (int i = 2; i < size; i++) { DownToUp(a, i); } }都写一下吧void BuildHeap(int a[], size_t size) // 自下而上建堆法 { for (int i = size / 2; i > 0; i--) { UpToDown(a, i, size); } }这就是堆排序前的所有操作，剩下的就是排序了，代码也很简单：堆排序void HeapSort(int a[], size_t size) { for (int i = size - 1; i > 0; i--) { swap(a[i], a[1]); UpToDown(a, 1, i); } swap(a[1], a[2]); }注意堆排序的前提是对堆排序，需要先BuildHeap的，直接排序你只能看到一堆乱七八糟的结果，然后怀疑自己写的哪有问题（别问我怎么知道的）。现在在你的main函数中写下你需要排序的数据，再试试你的代码就好了。 int a[9] = {0, 3, 5, 4, 1, 2, 0, 85, 7}; BuildHeap(a, 9); for (int i = 1; i < 9; i++) cout << a[i] << ' '; cout << endl; HeapSort(a, 9); for (int i = 1; i < 9; i++) cout << a[i] << ' ';

[doris]doris编译环境 这是尝试doris编译的第n次，这玩意是真难搞...无数次尝试直接编译之后，我的建议是使用docker首先拉取镜像docker pull apache/doris:build-env-ldb-toolchain-latest拉取成功之后使用docker images查看是否拉取成功。之后可以下载你fork的doris源码，再使用docker挂载目录docker run -it --network=host --name mydocker -v /your/local/.m2:/root/.m2 -v /your/local/doris-DORIS-x.x.x-release/:/root/doris-DORIS-x.x.x-release/ apache/doris:build-env-ldb-toolchain-latest注意自己修改成你自己的目录（/your/local/..）。如果你因为某些原因开放端口，那样上网的话，打开docker之后你可能没法联网，这时候就需要把--network=host去掉，接下来就是thirdparty。thirdparty是真难搞，我尝试了无数次还是没编译好，而且有时候download-thirdparty还会下载不了，还得自己下好再放到src目录，这里我建议用编译好的，能省无数的事。https://github.com/apache/doris-thirdparty/releases/tag/automation，你可以在这里找到合适的资源下载，最后把installed文件夹放在你的doris/thirdparty/目录下即可，其他的可以看官方文档就行了，如果有其他问题，修改就行，最后在docker里运行build.sh就好

[xv6]Lab1-Utilities 开始6.S081的学习了，在这里记录下我对xv6的理解以及我的题解，这里我会尽可能详细的写。我写了我的代码实现，但是肯定是不完善的，所以你最好都自己写，你如果实在写不出来，可以评论一句 “看看代码”。{dotted startColor="#ff6c6c" endColor="#1989fa"/}环境安装这个照着官网的 教程 来就行，注意一下自己的linux版本（ubuntu20.04）。sleep (easy)因为不知道该怎么开始，所以这个我是直接看写好的，知道了怎么开始才能继续下边的任务对吧。就是调用提供的sleep接口就行。#include "kernel/types.h" #include "kernel/stat.h" #include "user/user.h" int main(int argc, char *argv[2]) { if (argc < 2) { fprintf(2, "usage sleep <ticks>\n"); exit(1); } sleep(atoi(argv[1])); exit(0); }pingpong (easy)这个任务要求我们利用管道在两个进程之间通信，最后实现这样的效果：{card-describe title="pingpong"}$ make qemu ... init: starting sh $ pingpong 4: received ping 3: received pong ${/card-describe}管道是一个小的内核缓冲区，它以文件描述符对的形式提供给进程，一个用于写操作，一个用于读操作。从管道的一端写的数据可以从管道的另一端读取。管道提供了一种进程间交互的方式。xv6中我们可以使用pipe()函数创建管道，提到这个我们要先了解一下文件描述符。具体请自行查阅xv6文档，简单来说就是在一个进程中一些读写等操作需要文件描述符来确定，比如read(0, buf,sizeof buf);这里的0就是代表从这个“0”处读取，或者说输入端是0绑定的文件（注意这个0是文件索引）。我们创建一个管道之后，这个管道也有他的文件描述符。例如int p[2];pipe(p);这个管道的文件描述符就被保存在了p数组中。p[0]是管道的读端口，p[1]是管道的写端口，有了管道的文件操作符我们就可以操作管道了。这个任务既可以用一个管道也可以用两个管道，两个管道更容易理清关系，记得关闭无用描述符，比如p1在process1只写那么就close(p1[1])等等，双管道双进程关系如图： 一个管道也可以做，我就是一个管道做的，这样做有没有什么风险我不知道，但是确实可以用。在我的理解中单管道是这样工作的：首先在process1中fork出process2。process2在read时如果p[0]没有接收到数据并且process1的p[1]也没有关闭，所以无论怎样process2都会等待接收process1的数据，process1传输ping之后close(p[1])，process2接收ping再输出，此时process1也会被read阻塞，直到process2传入pong，这样就保证了顺序即使只有一个管道也不会乱。隐藏内容，请前往内页查看详情primes (moderate)/(hard)这个任务是让我们写出素数筛，具体实现请思考这张图： 思考完了吗？那我来讲讲实现吧。 首先呢一个进程只会输出一个数，之后他会接收上一个进程中已经筛过数继续筛，上图的drop就是被筛掉的数，我们可以看到在输出2的进程中4、6、8...等所有2的倍数都被drop了，通过筛选的第一个数也就是3会进入新进程并输出，第二个数5因为不被3整除且是输出3的进程的第一个通过筛选的数所以他又进入了一个新进程并被输出...以此类推，就完成了素数筛选。 然后讲讲我的实现方法，我使用了一个id作为一个进程的标识，这个id代表通过了上一个进程筛选的第一个数也就是确认的素数。首先这个进程输出这个id，或者输出之后再创建进程随你，之后它接收通过了上一个进程的筛选的数并使用自己来筛选，比如2筛选4、6、8，3筛选9这些，如果这个数通过，那么就传给下一个进程，如果它是第一个通过的，那么优先为它创建新进程并以它命名id，这样的工作持续到上一个进程的管道的写端口关闭，那么我们就关闭进程，上边的进程wait之后也相继关闭。 这方面请了解read，write，wait等系统调用。 我的文字描述可能有点不清晰，那请看图，相信你可以看懂的（我是做的时候为了自己能理清所以画了这张图，第一次觉得流程图这么有用） {alert type="info"}写的时候请思考每个管道应该什么时候关闭，不然你可能会遇到许多想不明白的问题。{/alert}隐藏内容，请前往内页查看详情find (moderate)find 需要我们实现查找文件功能，但是会遍历给定文件夹的所有子孙文件夹（我自己起的名字），接着输出所有名称与给定名称的一样的文件。这个函数给出的提示是让我们看ls的实现源码，接下来我们就好好分析一下ls部分的源码。void ls(char *path) { char buf[512], *p; int fd; struct dirent de; struct stat st; if((fd = open(path, O_RDONLY)) < 0){ fprintf(2, "ls: cannot open %s\n", path); return; } if(fstat(fd, &st) < 0){ fprintf(2, "ls: cannot stat %s\n", path); close(fd); return; } switch(st.type){ case T_DEVICE: case T_FILE: printf("%s %d %d %l\n", fmtname(path), st.type, st.ino, st.size); break; case T_DIR: if(strlen(path) + 1 + DIRSIZ + 1 > sizeof buf){ printf("ls: path too long\n"); break; } strcpy(buf, path); p = buf+strlen(buf); *p++ = '/'; while(read(fd, &de, sizeof(de)) == sizeof(de)){ if(de.inum == 0) continue; memmove(p, de.name, DIRSIZ); p[DIRSIZ] = 0; if(stat(buf, &st) < 0){ printf("ls: cannot stat %s\n", buf); continue; } printf("%s %d %d %d\n", fmtname(buf), st.type, st.ino, st.size); } break; } close(fd); }这个是主体两个if里就是给文件描述符赋值并将文件的信息保存在stat中，在switch中如果给出的path不是文件夹那么就输出当前文件的一些信息，重点是在T_DIR中，while这里就是遍历了所有子文件。//通过while循环不断读取数据，我们可以看dirent的解释： Directory is a file containing a sequence of dirent structures. while(read(fd, &de, sizeof(de)) == sizeof(de)){ if(de.inum == 0) continue; memmove(p, de.name, DIRSIZ); p[DIRSIZ] = 0; if(stat(buf, &st) < 0){ printf("ls: cannot stat %s\n", buf); continue; } printf("%s %d %d %d\n", fmtname(buf), st.type, st.ino, st.size); }知道了怎么遍历文件，剩下的就好做了，我们在遍历时候判断name是不是等于给定filename就行，当然如果是文件夹，那么我们进入这个文件夹再遍历，就是遇到文件就判断，遇到文件夹就递归，就完成了。隐藏内容，请前往内页查看详情xargs (moderate)这个我感觉比素数筛难，但是居然不带hard。首先呢，xargs就是执行它后边的程序也就是 xargs echo hello这样的，它接收管道的数据并加到hello之后，不过呢如果遇到换行\n，那就输出一行并继续执行相同操作，我这里描述的不太清晰，看个例子就明白了:echo hello\nworld | xargs echo say 这个不是很准确，因为\n会被识别成两个字符，但是我们假设这就是一个。程序是这样执行的：xargs echo say helloxargs echo say world看明白了吗？我们需要写一个字符串处理，就是把\n前和\n后的字符串分开，再用exec执行就行。通过分析，xargs的argv参数是这样的argv[0] = "xargs" argv[1] = "echo" argv[2] = "say"没有argv[3]，也就是说我们要使用read对文件操作符0进行读取，注意read读取一次只读取一个单词，所以我们还需要能读一整行的函数，不然还没读到\n就输出了不是？因为没有意识到read只读一个单词（或者说一直读到空格和换行）我这个做了很长时间但是找不到问题在哪，还有根据xv6book的描述，参数argv是根据argv==0结束的，在传参时候我们要注意这点。隐藏内容，请前往内页查看详情

[C++]Windows环境下给Clion安装Boost库 Boost下载打开官网https://www.boost.org/你现在可以看到这个界面 你可以选合适的版本安装，保证你的CMAKE支持该版本即可，这里下载1.82 建议下载7z的，zip解压太慢了（至少在我电脑上是这样）点击bootstrap.bat后生成b2.exe文件，再点这个exe等他编译完就好了Clion的CMakeList文件的修改这是我的配置：cmake_minimum_required(VERSION 3.27.0) project(CPP23) set(CMAKE_CXX_STANDARD 23) set(Boost_DEBUG on) set(Boost_DETAILED_FAILURE_MSG ON) set(BOOST_ROOT D:/local/boost_1_82_0) set(BOOST_INCLUDEDIR ${BOOST_ROOT}/boost) set(BOOST_LIBRARYDIR ${BOOST_ROOT}/stage/lib) set(Boost_LIB_PREFIX "lib") set(Boost_ARCHITECTURE "-x64") find_package(Boost COMPONENTS REQUIRED) add_executable(CPP23 main.cpp) include_directories(${BOOST_ROOT}) target_link_libraries(CPP23 ${Boost_LIBRARIES})项目名称是CPP23，里边有一个main.cpp文件，BOOST_ROOT后边填写你的boost解压目录即可Boost编译时提示找不到vswhere，build engine找不到文件的解决办法直接先上结论，装一下VS就好了昨天准备在Clion上安装Boost库，但是Clion的Cmake版本不支持最新的1.83的Boost库，所以我就去下载了1.82版本的。但是这次下载之后我运行bootstrap.bat一直出错，无法生成b2.exe，于是我打开了booststrap.bat文件发现它会检测有没有生成b2文件，没有的话会运行build.bat，打开build.bat它是默认找Visual Studio的，但是我之前把VS删了所以一直没成功，这时候我忘了自己删了VS，就到网上各种查，甚至该build文件，最后发现都是多余了。上了床查了vswhere想到找找我的正确的目录，今天才发现是我给卸载了...