Wolf's Blog - C++/C
type: channel
link: https://www.guwolf.com/category/C/
items: 万级并发的秘密：一文彻底搞懂 Linux Epoll
items: GuWolf的ICPC算法模板
items: 基础算法-二分查找篇
items: 基础算法-排序篇

万级并发的秘密：一文彻底搞懂 Linux Epoll
type: item
date: 2025-12-05T19:26:00+08:00
description: 在高并发网络编程中，如何高效地处理大量连接是一个核心问题。Linux 提供的 epoll 机制，正是解决这一问题的利器。本文将深入剖析 epoll 的设计原理、核心 API 以及触发模式的区别，帮助你理解为什么 epoll 能够支撑起万级并发，也就是著名的 C10K 问题。一、为什么需要 epoll？—— select/poll 的性能瓶颈在 epoll 出现之前，Linux 主要使用 select 和 poll 来实现 I/O 多路复用。然而，当需要处理大量（$N$ 个）连接时，它们存在两个致命的性能瓶颈：$O(N)$ 的遍历开销每次调用 select 或 poll 时，内核都必须遍历检查所有 $N$ 个文件描述符（FD），以找出哪些是就绪的（可读/可写）。即使只有 1 个连接有数据到达，内核也要检查全部 $N$ 个 FD，这是极大的性能浪费。$O(N)$ 的拷贝开销每次调用都需要将完整的 $N$ 个 FD 列表从用户空间拷贝到内核空间。当连接数达到数万时，这种频繁的内存拷贝会成为严重的性能负担。二、epoll 的解决方案：持久化管理与高效数据结构epoll 的设计理念很简单但很高明：既然 FD 列表变化不频繁，为什么每次都要重新传递呢？于是，epoll 针对这两个问题分别设计了解决方案：解决拷贝开销：持久化注册核心思想：程序只需在内核中注册一次感兴趣的 FD 列表，之后调用 epoll_wait 时不需要再传递整个列表。epoll 通过 epoll_create 在内核中创建一个持久化的实例，所有被监听的 FD 都存储在这个实例中。应用程序通过 epoll_ctl 增删改 FD，而不是每次调用时都传递完整列表。这种"注册一次，长期有效"的设计，彻底消除了 $O(N)$ 的拷贝开销。解决遍历开销：红黑树 + 就绪列表遍历开销体现在两个地方，epoll 分别用两种数据结构来解决：红黑树：高效管理 FD当调用 epoll_ctl 增删改 FD 时，需要快速定位目标 FD。epoll 使用红黑树来存储所有被监听的 FD，使得每次操作的时间复杂度稳定在 $O(\log N)$，可能你会好奇为什么不用哈希表。固然，从纯粹的算法时间复杂度来看，哈希表的查找/插入/删除平均复杂度是 $O(1)$，确实要比红黑树的 $O(\log N)$ 要快。但在内核场景下，理论最快并不等于工程最优，就好像贪心得到的是局部最优解一般。下面从几个维度告诉你为什么会选择红黑树动态扩容成本哈希表的动态扩容的成本是它在内核场景下最大的劣势，哈希表一般基于数组（Bucket），我们假设连接数从 10K 增加至 100K 甚至 1000K 时，哈希表就不可避免地需要扩容 (Rehash)。哈希表的扩容需要申请一块更大的内存，然后把旧表里的所有数据重新计算 Hash 并移动过去，这是一个 $O(N)$ 的操作。在内核态中，这种瞬间的大量计算和内存操作会造成剧烈的系统抖动 (Jitter)，导致那一瞬间的 epoll_ctl 的响应时间急剧增加，这是不可接受的。而红黑树则是动态生长的，每插入一个节点，只需要少量的指针操作，它没有扩容的概念，性能曲线非常平滑，而不会像哈希表在某个时刻突然 Rehash 造成卡顿。内存利用率epoll 需要适应各种规模的场景（从监听几个 FD 到监听几万个 FD）。哈希表为了减少哈希冲突以尽可能维持 $O(1)$ 的性能，通常会预分配比实际数据量大的内存。这就会产生一些问题：如果预分配得太大，对于只有几个连接的情况会造成巨大的内存浪费。如果预分配太小，又会频繁触发扩容。内核无法预测用户会创建多少个连接，因此很难预分配一个完美的初始大小。而红黑树则是用多少拿多少，它不需要预分配连续的内存，因此对内存的利用率可以说是100%的。确定性内核开发非常看重可预测性 (Predictability)。哈希表的时间复杂度虽然平均是 $O(1)$，但在最坏情况下会退化成链表 $O(N)$，虽然可以通过良好的 Hash 函数缓解，但风险依然存在。而红黑树的时间复杂度有着严谨的数学证明，无论数据如何分布，查找、插入、删除永远都稳定在 $O(\log N)$。对于内核而言，“稳定的慢”往往比“不稳定的快”要优。💡 小知识 $O(\log N)$ 其实并不慢，假设数据量为 100 万，$\log_2(10^6) \approx 20$，单次操作也仅仅需要进行约 20 次比对。总结特性哈希表 (Hash Table)红黑树 (RB-Tree)Epoll 的选择平均查找速度$O(1)$$O(\log N)$红黑树够用了最坏查找速度$O(N)$（冲突时）$O(\log N)$红黑树胜内存开销高 (预分配 bucket，存在内存空洞)低 (按需分配)红黑树胜扩容成本极高 …

GuWolf的ICPC算法模板
type: item
date: 2025-10-23T16:37:00+08:00
description: 模板只有DS和一点点数学，因为DP和数学感觉没必要写在模板里(其实主要是懒OωO)点击查看/下载: GuWolf的模板.pdfPS: SAM(后缀自动机)是AI写的,要比赛了来不及~杂项快读普通快读inline int read() { int x = 0, f = 1; char ch = getchar(); while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); } while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar(); return x * f; }优化快读char *p1, *p2, buf[100000]; #define nc() (p1==p2 && (p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++) int read() { int x = 0, f = 1; char ch = nc(); while (ch < 48 || ch > 57) { if (ch == '-') f = -1; ch = nc(); } while (ch >= 48 && ch <= 57) x = x * 10 + ch - 48, ch = nc(); return x * f; }快写void write(int x) { if (x < 0) putchar('-'), x = -x; if (x > 9) write(x / 10); putchar(x % 10 + '0'); }超级快读写(待测试)namespace __Coel_FastIO { const int SIZE = 1 << 20; static char buf_r[SIZE], *p1 = buf_r, *p2 = buf_r; static char buf_w[SIZE], *p3 = buf_w, *p4 = buf_w + SIZE; static std::streambuf *inbuf = std::cin.rdbuf(), *outbuf = std::cout.rdbuf(); //流初始化 inline static void gc(char &ch) { //这里三目运算符的效率略高一些 ch = p1 == p2 && (p2 = (p1 = buf_r) + inbuf->sgetn(buf_r, SIZE), p1 == p2) ? EOF : *p1++; /*逻辑：先判断有没有读完一个缓存，如果缓存空了就继续往下读， 否则用 sgetn 读入一个缓存，如果还是空的就返回 EOF*/ } inline static void pc(char c) { p3 == p4 ? outbuf->sputn(p3 = buf_w, SIZE), *p3++ = c : *p3++ = c; /*逻辑差不多，如果写完整个缓存就全部输出，否则写入缓存*/ } inline static int Flush() { return outbuf->sputn(buf_w, p3 - buf_w), 0; } //清空数组 struct IOdesu { template<typename T> IOdesu& operator >>(T &x) { x = 0; int f = 1; char ch; gc(ch); while (ch < '0' || ch > '9') { if (ch == '-') f = -1; gc(ch); } while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', gc(ch); return x *= f, *this; } template<typename T> IOdesu& operator <<(T x) { if (x < 0) x = -x, pc('-'); static int buf[35]; int top = 0; do { buf[top++] = x % 10; x /= 10; } while (x); while (top) pc(buf[--top] + '0'); return *this; } IOdesu& operator <<(char ch) { return pc(ch), *this; } } qwq; } /* 使用教程 qwq >> x; qwq << x; */卡时有一个 clock() 函数，返回程序运行时间。while ((double)clock()/…

基础算法-二分查找篇
type: item
date: 2024-01-04T20:41:00+08:00
description: 什么是二分查找二分查找也叫折半搜索，是用来在一个有序数组中查找某一元素的算法。相较于线性查找,二分查找利用了数组的有序性质,通过调整边界快速缩减查找范围,大大提高了查找效率。线性查找时间复杂度:时间复杂度(最好) O(1)时间复杂度(最坏) O(n)二分查找时间复杂度:时间复杂度(最好) O(1)时间复杂度(最坏) O(logn)1. 整数二分的代码实现以升序数组为例int binarySearch(int arr[], int left, int right, int target) { while (left <= right) { int mid = left + (right - left) / 2; if (arr[mid] == target) return mid; if (target > arr[mid]) left = mid + 1; else right = mid - 1; } return -1; } STL库里的二分C++ STL库里有两个查找函数std::lower_bound实现了查找首个不小于给定值的元素std::upper_bound实现了查找首个大于给定值的元素二者均采用二分查找，所以使用前应确保数组有序。传入参数first, last -要搜索部分范围的迭代器value -要与元素比较的值返回值指向范围首个符合条件的元素的迭代器，在找不到这种元素时返回last要得到符合条件的元素的下标只需要使用返回迭代器减去first即可比如--- int a[5] = {1,3,5,7,9}; int loc = lower_bound(a, a+5, 3) - a; // loc = 1 int loc = upper_bound(a, a+5, 3) - a; // loc = 2 ---

基础算法-排序篇
type: item
date: 2024-01-04T19:03:00+08:00
description: PS:页面右边有该文章的目录，可快捷跳转到对应位置目前该篇只介绍了三种排序算法:冒泡排序、插入排序、快速排序(极度推荐)。以及C++ STL里快排函数sort()的使用。1.冒泡排序1.1 算法介绍时间复杂度(平均) O(n²)时间复杂度(最好) O(n)时间复杂度(最坏) O(n²)空间复杂度 O(1)这应该是世界上知名度最广的一个排序算法了吧(也是时间复杂度最高的算法) ::twemoji:tilted::1.2 代码实现void bubbleSort(int arr[], int n) { for (int i = 0; i < n - 1; ++i) { for (int j = 1; j < n - i; ++j) { if (arr[j-1] > arr[j]) swap(arr[j-1], arr[j]); } } } 1.3 GIF原理图2.插入排序2.1 算法介绍时间复杂度(平均) O(n²)时间复杂度(最好) O(n)时间复杂度(最坏) O(n²)空间复杂度 O(1)2.2 代码实现void insertionSort(int arr[], int n) { for (int i = 1; i < n; ++i) { int key = arr[i]; int j = i - 1; while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; --j; } arr[j + 1] = key; } }2.3 GIF原理图3.快速排序3.1 算法介绍时间复杂度(平均) O(nlogn)时间复杂度(最好) O(nlogn)时间复杂度(最坏) O(n²)空间复杂度 O(nlogn)快速排序采用了分治策略,通过一个pivot(基准值)将数组分成两部分,一部分小于pivot,一部分大于pivot。然后递归对两部分继续排序,直到数组有序。复杂度分析: 最坏情况下,每次pivot都位于边界,会导致递归树退化为链表,时间复杂度为O(n^2)平均情况下,递归树深度为O(logn),每层partition时间为O(n),所以平均时间复杂度为O(nlogn)3.2 代码实现int partition(int arr[], int left, int right) { int pivot = arr[right]; int i = left - 1; for (int j = left; j < right; ++j) { if (arr[j] < pivot) { ++i; swap(arr[i], arr[j]); } } swap(arr[i + 1], arr[right]); return i + 1; } void quickSort(int arr[], int left, int right) { if (left < right) { int pivot = partition(arr, left, right); quickSort(arr, left, pivot - 1); quickSort(arr, pivot + 1, right); } }3.3 GIF原理图没找到合适的动图，排序过程请看算法介绍4. C++ STL里的排序C++ 标准库里实现了排序的函数std::sort(),印象中其效率是和快排差不多的,该函数定义于头文件 <algorithm>传入参数:参数说明first,last要搜索部分范围的迭代器comp比较函数4.1 对数组进行升序排序sort默认排序顺序是升序#include <iostream> #include <algorithm> using namespace std; int main() { int a[10] = {1,5,9,8,7,5,3,2,6,4}; sort(a, a+10); for (int i = 0; i < 10; ++i) cout << a[i] << ' '; // 1 2 3 4 5 5 6 7 8 9 return 0; } 4.2 对数组进行降序排序这时候就需要自定义比较函数bool compare(int a, int b) { return a > b; } 然后再排序sort(a, a+10, compare); 4.3 对结构体数组进行排序同理自定义排序函数可以让我们对结构体进行排序bool compare(struct aaa A, struct aaa B) { if (A.a == B.a) return A.b > B.b; return A.a > B.a; } 然后再进行排序sort(aaa, aaa+10, compare); 猫猫说