东风草堂博客

什么是递归

周末你带着女朋友去电影院看电影，女朋友问你，咱们现在坐在第几排啊？电影院里面太黑了，看不清，没法数，现在你怎么办？

别忘了你是程序员，这个可难不倒你，递归就开始排上用场了。于是你就问前面一排的人他是第几排，你想只要在他的数字上加一，就知道自己在哪一排了。但是，前面的人也看不清啊，所以他也问他前面的人。就这样一排一排往前问，直到问到第一排的人，说我在第一排，然后再这样一排一排再把数字传回来。直到你前面的人告诉你他在哪一排，于是你就知道答案了。

这就是一个非常标准的递归求解问题的分解过程，去的过程叫“递”，回来的过程叫“归”。基本上，所有的递归问题都可以用递推公式来表示。刚刚这个生活中的例子，我们用递推公式将它表示出来就是这样的：

1

f(n)=f(n-1)+1 其中，f(1)=1

因为这些排序算法的时间复杂度是线性的，所以我们把这类排序算法叫作线性排序（Linear sort）。之所以能做到线性的时间复杂度，主要原因是，这三个算法是非基于比较的排序算法，都不涉及元素之间的比较操作。

桶排序（Bucket sort）

核心思想是将要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行排序。桶内排完序之后，再把每个桶里的数据按照顺序依次取出，组成的序列就是有序的了。

如果要排序的数据有 n 个，我们把它们均匀地划分到 m 个桶内，每个桶里就有 k=n/m 个元素。每个桶内部使用快速排序，时间复杂度为 O(k * logk)。m 个桶排序的时间复杂度就是 O(m * k * logk)，因为 k=n/m，所以整个桶排序的时间复杂度就是 O(n*log(n/m))。当桶的个数 m 接近数据个数 n 时，log(n/m) 就是一个非常小的常量，这个时候桶排序的时间复杂度接近 O(n)。

桶排序对要排序数据的要求是非常苛刻的。要排序的数据需要很容易就能划分成 m 个桶，并且，桶与桶之间有着天然的大小顺序。这样每个桶内的数据都排序完之后，桶与桶之间的数据不需要再进行排序。

深入解析网络测速的核心逻辑与实现方案，涵盖chunked数据传输格式、HTTP POST请求机制、基于epoll的高并发网络编程技术，详解客户端与服务端协同测速原理，提供完整的C++代码实现示例。

详细解析读写锁的功能与实现原理，包括读写锁的基本概念、加锁与解锁机制、读写锁的优化策略、读写锁的性能分析等。提供完整的C++代码示例，帮助开发者理解并在实际项目中应用读写锁。

mem

读取文件：/proc/meminfo
MemTotal: 总内存
freeMem: Cached + MemFree + Buffers
程序占用mem：/proc/%d/status
VmRSS: 进程占用内存

cpu

读取文件：/proc/stat
包括：系统cpu、空闲、io等待、irq中断、软中断等。

1

fscanf(file, "%s%lld%lld%lld%lld%lld%lld%lld%lld%lld", temp, &user, &nice, &sys, &idle, &iowait, &irq, &softirq, &steal, &guest);

2G内存在20亿个整数中找出次数最多的数？

kv来描述一个数，一个整数4byte，两个整数8byte，20亿个整数需要16G内存。
数据结构存储：平衡二叉树map、散列表unordered_map。
分治：20亿个整数拆分成若干个范围，分别统计若干个范围中的次数多最大值，汇总若干个范围中的次数最大值，找出次数最大值对应的树。
逆向分析：
2GB = 2 * 2^10 * 2^10 * 2^10 B = 2^31 B，小范围的数字最多 2^31 / 8 = 2^28
有多少个小范围？整数4个字节共32bit，范围为-2^31～2^31，共2^32个整数，2^32/2^28 = 2^4
正向解决：

• 将20亿个数拆分为16个范围
• 将20亿个数依次除以2^28，得到一个0-15的值，放在一个小文件中，另外一种解法：hash分流，相同的key，经过多次hash总是得到相同的值，hash具备随机性，crc16、md5、murmurhash2、siphash、cityhash
• 每个小文件unordered_map[k]++，散列表进行词频统计，如果某一个key出现次数超过10亿，就不必要统计了，这样也可以控制value的范围

40亿个非负整数中算中位数和找出现两次的数

1. 最多使用1GB的内存，找出所有出现了两次的数
   出现了两次，共三种状态：

如果中序遍历为有序的话则为二叉搜索树，为了避免退化为单链表，加入平衡规则后保持平衡则为平衡二叉树，搜索的时间复杂度为O(lgn).
满二叉树、完全二叉树又推出最大堆、最小堆（堆排序、定时器）。平衡二叉树又推出avl、红黑树。
对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。

二叉树的递归遍历

前序遍历：根->左->右，1>2>4>5>3>6>7，245这棵树是作为一个整体子树从根节点遍历，这就是递归的思想。
中序遍历：左->根->右，4>2>5>1>6>3>7，每次遍历到子树也是重新左->根->右进行遍历。
后序遍历：左->右->根，4>5>2>6>7>3>1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

void PreOrder(TreeNode *root)
{
    if (root == nullptr) return;
    result.push_back(root->val);
    PreOrder(root->left);
    PreOrder(root->right);
}

void InOrder(TreeNode *root)
{
    if (root == nullptr) return;
    InOrder(root->left);
    result.push_back(root->val);
    InOrder(root->right);
}

void PostOrder(TreeNode *root)
{
    if (root == nullptr) return;
    PostOrder(root->left);
    PostOrder(root->right);
    result.push_back(root->val);
}

二叉树的迭代遍历

系统级IO

每个进程都有个umask，通过umask函数来设置的，当进程通过带某个mode参数的open函数来创建一个新文件时，文件的访问权限位被设置为mode & ~umask，也就是umask是程序设定的掩码，哪怕你open时mode为777，最后出来的权限有可能不是777了。

共享文件：

• 每个进程都有它独立的描述符表，它的表项是由进程打开的文件描述符来索引的。每个打开的描述符表项指向文件表中的一个表项。
• 打开文件的集合是由一张文件表来表示的，所有进程共享这张表。文件表表项包括当前的文件位置、引用计数即当前指向该表项的描述符表项数，以及一个指向v-node表中对应表项的指针。引用计数变为0内核才会删除这个文件表项。
• 所有进程共享v-node表。表项包含stat结构中的大部分信息，如st_mode、st_size成员。
  描述符1/4打开不同的文件，有不同的文件表项，以及相对应的v-node:
  
  子进程有父进程描述符的副本，父子进程共享相同的文件表，所以共享相同的文件位置，另外，内核删除相应文件表表项之前，父子进程都必须关闭了它们的文件描述符。
  
  同一个文件open两次，也有不同的文件表项，记录自己的文件位置，但v-node是同一个，这种属于文件共享：
  

IO重定向：

TCP/UDP应用场景分析

游戏行业（可以让业务定制化，比如自定义重传策略，有些包可以不需要重发）、音视频通话（比如超过1s的包可以不重发）、出于资源的考虑，比如dns解析，手机定位获取隐私，嵌入式设备发送信息(用电池的设备，比如家里的消防传感器，一个电池用5年)、大块数据下载，不考虑网络拥塞。
tcp相比于udp，主要是重发导致的延迟。

UDP sendto/recvfrom的坑

tcp时流式传输，而udp是报文传输，发完的数据需要对端一次性读取完整，否则会造成数据丢失，所以一次性最多只能发送1500-20-8=1472的数据量（1500为网卡MTU的大小），避免拆包，加上PPPOE的协议头，一般发送1400就够了，在游戏领域，由于发送的数据量少，一般为572或者500就行了，如果发超过了，tcpdump可以看到会报bad length。

UDP如何实现可靠性设计

漏桶算法

把请求比作是水，水来了都先放进桶里，并以限定的速度出水，当水来得过猛而出水不够快时就会导致水直接溢出，即拒绝服务。

可以看出，漏桶算法可以很好的控制流量的访问速度，一旦超过该速度就拒绝服务。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

#include <iostream>
#include <chrono>
#include <thread>
using namespace std;
using namespace std::chrono;

class LeakyBucket {
public:
    LeakyBucket(int capacity, int rate){
        this->capacity = capacity;
        this->rate = rate;
        this->water_count = 0;
        this->last_leak_time = duration_cast<milliseconds>(system_clock::now().time_since_epoch());
    }

    bool take_request(){
        auto now = duration_cast<milliseconds>(system_clock::now().time_since_epoch());
        int passed_time = (int)(now - last_leak_time).count();

        water_count -= passed_time * rate; // 固定的速度流水
        if(water_count < 0){
            water_count = 0;
        }

        if(water_count < capacity){ // 请求就是加入的水，加满了就拒绝服务
            water_count++;
            last_leak_time = now;
            return true;
        }

        return false;
    }

private:
    int capacity;
    int rate;
    int water_count;
    time_point<system_clock> last_leak_time;
};

int main() {
    LeakyBucket bucket(10, 2);

    for(int i = 0; i < 20; i++){
        if(bucket.take_request()){
            cout << "request " << i + 1<< " passed" << endl;
        } else {
            cout << "request " << i + 1 << " discarded" << endl;
        }
        if(i != 19){
            std::this_thread::sleep_for(100ms);
        }
    }

    return 0;
}

令牌桶算法

令牌桶算法的原理是系统会以一个恒定的速度往桶里放入令牌，而如果请求需要被处理，则需要先从桶里获取一个令牌，当桶里没有令牌可取时，则拒绝服务。从原理上看，令牌桶算法和漏桶算法是相反的，一个“进水”，一个是“漏水”。