公众号:来风说

因为这些排序算法的时间复杂度是线性的，所以我们把这类排序算法叫作线性排序（Linear sort）。之所以能做到线性的时间复杂度，主要原因是，这三个算法是非基于比较的排序算法，都不涉及元素之间的比较操作。 桶排序（Bucket sort）核心思想是将要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行排序。桶内排完序之后，再把每个桶里的数据按照顺序依次取出，组成的序列就是有序的了。 如果要排序的数据有 n 个，我们把它们均匀地划分到 m 个桶内，每个桶里就有 k=n/m 个元素。每个桶内部使用快速排序，时间复杂度为 O(k logk)。m 个桶排序的时间复杂度就是 O(m k logk)，因为 k=n/m，所以整个桶排序的时间复杂度就是 O(nlog(n/m))。当桶的个数 m 接近数据个数 n 时，log(n/m) 就是一个非常小的常量，这个时候桶排序的时间复杂度接近 O(n)。 桶排序对要排序数据的要求是非常苛刻的。要排序的数据需要很容易就能划分成 m 个桶，并且，桶与桶之间有着天然的大小顺序。这样每个桶内的数据都排序完之后，桶与桶之间的数据不需要再进行排序。 其次，数据 ...

测速原理往一个测速服务器post发送chunked数据，固定发到多少为止，可以采用多线程进行发送，统计发送的时间，这个时间是客户端的，仅仅作为参考，实际最后的测速结果是由服务端给出的。要发送分块编码（chunked）格式的数据，可以使用以下步骤： 设置HTTP请求头中的Transfer-Encoding字段为chunked。 将数据分成多个块（chunk），每个块都包含一个长度和数据本身。 将每个块发送到服务器，以回车换行符（\r\n）作为分隔符。 在所有块发送完成后，发送一个长度为0的块作为结束符，以回车换行符（\r\n）结尾。1234567891011121314151617# 发送请求头s.sendall(b'POST /api HTTP/1.1\r\n')s.sendall(b'Host: example.com\r\n')s.sendall(b'Content-Type: text/plain\r\n')s.sendall(b'Transfer-Encoding: chunked\r\n')s.sendall(b'\r\n')# 发送第一个块chunk1 = bytes(' ...

功能与实现原理允许多个线程同时加读锁，但只允许一个线程加写锁，可以写嵌套，即一个线程里面加写锁了，可以继续在这个线程加写锁，不会阻塞。当有线程在读取时，写入线程阻塞，当写入线程执行时，所有的读取线程都被阻塞。允许嵌套加锁 当前线程写入加锁时可以嵌套加读锁或写锁 当前线程读取加锁时可以嵌套加读锁，但不能嵌套加写锁，否则当前线程会陷入死锁，原理为：已经作为只读区了，就不应该存在写了 加读锁的时候： 判断当前线程是不是使用写锁的线程，如果是的话，可以加读锁。 如果当前线程不是使用写锁的线程，需要等待写锁线程使用完、以及正在等待写的先使用完写锁，因为写的优先级高。 加写锁的时候： 判断当前线程是不是使用写锁的线程，如果是的话，可以加写锁，因为允许嵌套写。 如果当前线程不是使用写锁的线程，需要等待读锁线程以及写锁线程都使用完，但可以不管正在等待读写的线程，因为自己先从条件变量抢到了锁。 释放读锁的时候： 如果有写锁正在等待，通知它 释放写锁的时候： 注意嵌套写锁全都释放了以后，才是真正的释放。 释放后，如果有写锁正在等待，先通知写锁，因为写锁的优先级高。 如果有读锁正在等待，再 ...

mem读取文件：/proc/meminfoMemTotal: 总内存freeMem: Cached + MemFree + Buffers程序占用mem：/proc/%d/statusVmRSS: 进程占用内存 cpu读取文件：/proc/stat包括：系统cpu、空闲、io等待、irq中断、软中断等。1fscanf(file, "%s%lld%lld%lld%lld%lld%lld%lld%lld%lld", temp, &user, &nice, &sys, &idle, &iowait, &irq, &softirq, &steal, &guest); 我们通过 iostat工具可以看到这几个状态的值，它们都是以百分比的形式显示的，CPU 是在这几个状态之间切换，所以这几个值总和是 100%：需要说明一点，上图中的 %sys, %user, %idle, %iowait 的百分比值都是针对所有的 CPU 来说的，统计的是全局的信息，并不是指单个进程的数据. 12%iowaitPercentage of tim ...

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亿，就不必要统计了，这样也可以控制val ...

如果中序遍历为有序的话则为二叉搜索树，为了避免退化为单链表，加入平衡规则后保持平衡则为平衡二叉树，搜索的时间复杂度为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 1234567891011121314151617181920212223void PreOrder(TreeNode *root){ if (root == nullptr) return; ...

系统级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两次，也有不同的文件表 ...

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如何实现可靠性设计先要理解TCP传输协议，丢包怎么处理？什么情况下重传数据？怎么确认数据？对方没有回应数据包收到，超时重传。怎么处理包的先后顺序问题？重排机制。拥塞控制怎么实现？有tcp可靠，为什么还要搞udp可靠？主要是可控：重传时间可控；业务认 ...

漏桶算法把请求比作是水，水来了都先放进桶里，并以限定的速度出水，当水来得过猛而出水不够快时就会导致水直接溢出，即拒绝服务。可以看出，漏桶算法可以很好的控制流量的访问速度，一旦超过该速度就拒绝服务。1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556#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; ...

进程和线程的区别？ 一个线程只能属于一个进程，而一个进程可以有多个线程，但至少有一个线程。线程依赖于进程而存在。 进程在执行过程中拥有独立的内存单元，而多个线程共享进程的内存。（资源分配给进程，同一进程的所有线程共享该进程的所有资源。同一进程中的多个线程共享代码段（代码和常量），数据段（全局变量和静态变量），扩展段（堆存储）。但是每个线程拥有自己的栈段，栈段又叫运行时段，用来存放所有局部变量和临时变量。） 进程是资源分配的最小单位，线程是CPU调度的最小单位； 系统开销： 由于在创建或撤消进程时，系统都要为之分配或回收资源，如内存空间、I／o设备等。因此，操作系统所付出的开销将显著地大于在创建或撤消线程时的开销。类似地，在进行进程切换时，涉及到整个当前进程CPU环境的保存以及新被调度运行的进程的CPU环境的设置。而线程切换只须保存和设置少量寄存器的内容，并不涉及存储器管理方面的操作。可见，进程切换的开销也远大于线程切换的开销。 通信：由于同一进程中的多个线程具有相同的地址空间，致使它们之间的同步和通信的实现，也变得比较容易。进程间通信IPC，线程间可以直接读写进程数据段（如全局变量）来 ...