如何进行并行编程？本文给了一些pthead库基本的多进程、多线程API，和详细的样例帮助理解这些API。 本教程基于AUPE 2013、 perfbook Shell中的并行 后台执行 & 通过&符号指定实例在后台运行，然后统一等待结束。 1 2 3 4 compute_it 1 > 1.out & compute_it 2 > 2.out & wait cat 1.out 2.out 管道 | 对于一个足够大的输入文件来说，grep模式匹配将与sed编辑和sort处理并行运行。 1 grep "$pattern" | sed -e "s/a/b/" | sort POSIX多进程 下面给出的程序中建立了一个进程，然后修改了x的值并打印，最后父进程等待子进程结束。 fork int fork()马上创建一个当前进程的子进程。子进程会复制(而不是共享)父进程的堆栈、数据空间、fd。 如果是父进程，fork返回子进程的pid。如果是子进程，fork返回0。一般用这个区分不同的分支。 fork返回负数表示失败。失败的原因可能有：系统有了太多的进程；系统中用户进程数超过了CHILD_MAX。此时返回负数。 fork后如果不需要父进程的存储空间会立马调用exec。 使用fork一般有两个目的。父进程希望复制自己，或者想执行另外的程序（调用exec） 为了避免拷贝成本，出现了写时拷贝技术(Copy-On-Write, COW)，子进程创建后分享父进程的数据，并把内存区域设置为只读。当需要写数据时再为这块数据创建副本。 vfork int vfork()创建一个子进程，但分享(不复制)父进程的数据。当执行exec时父进程才退出休眠。专为了避免fork的拷贝成本设计。因为share父进程的数据有很大风险，所以man手册里明确说明vfork()之后，子进程只应该调用_exit()或者exec函数族。 exit void exit(int)退出当前进程。不像return会析构局部变量，弹栈，回到上级函数。如果在子进程的main中调用了return，main会返回两次，导致程序出错。exit不会有这个问题。 wait pid_t wait(int &status) 阻塞等待任意一个子进程结束 a)如果子进程都在运行则阻塞 b)如果一个子进程已经终止，内核向父进程发出了SIGCHLD信号，则获得终止状态并立即返回 c)成功了返回pid，没有子进程，立即出错返回-1 d)子进程状态status可以用四个返回bool的宏 WIFEXITED(int)、WIFEXITSIGNALED(int)、WIFSTOPPED(int)、WIFCONTINUED(int)、来判断属于正常、异常、暂停、暂停后继续的状态。此外还有对应的WEIXTSTATUS(int)返回子进程exit函数的参数、WTERMSIG(int)返回信号编号、WCOREDUMP(int）返回是否生成coredump等。 pid_t waitpid(pid_t pid, int &status, int option)等待指定的pid的子进程结束。

scrapy是个很简单强大的python爬虫框架，不需要处理网络相关逻辑就可以轻松爬取。本文介绍了一些基本的内容。需要注意的是，本文档中所有的●表示非必须内容。 本教程基于官方文档：官方文档 安装scrapy CentOS 1 2 yum install python34-devel.x86_64 pip3 install scrapy 创建项目 1 2 3 4 //创建项目hello scrapy startproject hello //创建一个爬虫（在项目根目录运行，不要加http://），名字为baidu，域名为www.baidu.com scrapy genspider baidu "www.baidu.com" ● 需要注意的是，如果要无视robots.txt文件，请在下面的settings.py中设置ROBOTSTXT_OBEY = False ● 刚才建好的项目目录文件树如下： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 tree hello hello |-- hello | |-- __init__.py | |-- items.py // 输出结构体定义 | |-- middlewares.py | |-- pipelines.py | |-- __pycache__ | |-- settings.

平衡树 在谈红黑树之前，可以先看看红黑树的根源，234树。234树也是一种平衡树。 平衡树的原型都是二叉查找树，即左面的节点比他小，右边的节点比他大。但是在二叉查找树的过程中，很有可能变成树朝一边严重倾斜的情况。为了解决这个问题，设计了如下变种： avl：严格控制树的平衡，左右树的高度差不大于1。所以查找性能是logn。在插入和删除操作时，最差的情况是每一级的父节点都会旋转。时间复杂度都是O(logn)。 红黑树：红黑树的左右子树最高差时，一个子树是另一个子树的一倍。最坏查找性能是2logn。在插入操作时，最差旋转2次，删除操作最差旋转三次，可以减少avl的平衡操作，但是依然是O(logn)的复杂度（在找到节点的插入位置就要花费logn时间）。 splay：插入删除复杂度也是O(logn)，可以用数组实现，不需要额外维护树的节点信息。但在最坏情况下他会退化成一条链。而且只读操作也会影响树的结构，在多线程环境访问下比较复杂。 替罪羊树：在查找树不平衡的时候，找到最高的一个节点（满足左右子树不差0.7倍的平衡点），重构整个子树 查找问题还可以用哈希表解决。哈希表是无序的，而且会耗费大块的内存。 一些常见的面试题：常见面试题-cnblog 各种树的性能 2-3-4树 2-3-4树-CSDN 234树是红黑树的等价变种。先来看看2-3树，这种树有两种节点，2节点和3节点。 2-节点：普通节点，有两个子连接 3-节点：有两个值A、B，三个连接（分别指向小于A，介于AB之间，大于B的儿子） 2-3树可以保证插入的时候所有叶子到根节点的距离是相同的。我们看看他如何插入： (1) 如果值插入2节点，把他扩充成一个3节点。 (2) 如果插入插入3节点 A. 整个树只有一个3节点：把他扩展成4-节点，然后分解4-节点，然后将分解后的新树的父节点融入到2-节点的父节点中去。 B. 3-节点有一个2-节点的父节点，此时的操作是，3-节点扩充为4-节点，然后分解4-节点，然后将分解后的新树的父节点融入到2-节点的父节点中去。 C. 3-节点有一个3-节点的父节点，此时操作是：3-节点扩充为4-节点，然后分解4-节点，新树父节点向上融合，上面的3-节点继续扩充，融合，分解，新树继续向上融合，直到父节点为2-节点为止，如果向上到根节点都是3-节点，将根节点扩充为4-节点，然后分解为新树，至此，整个树增加一层，仍然保持平衡。 23树的流程比较复杂，而且涉及不同节点的转换，所以出现了红黑树来简化操作。我们把3节点的两个元素红色连接连起来。这时候红色连接出去的那个节点就成了红黑树的红节点，其余的都是黑节点。如果你将红黑树中所有的红色链接放平，那么它所有的叶子节点到根节点的距离都是相同的，所以是一个完美的黑色平衡。 所以，红黑树的另一种定义是满足下列条件的二叉查找树： ⑴ 红链接均为左链接。 ⑵ 没有任何一个结点同时和两条红链接相连。(这样会出现4-节点) ⑶ 该树是完美黑色平衡的，即任意空链接到根结点的路径上的黑链接数量相同。 红黑树 github红黑树(有比较好的图解) cnblog红黑树流程详解 红黑树的五条性质： 1）每个结点要么是红的，要么是黑的。 2）根结点是黑的。 3）每个叶结点（叶结点即指树尾端NIL指针或NULL结点）是黑的。 4）如果一个结点是红的，那么它的俩个儿子都是黑的。 5）对于任一结点而言，其到叶结点树尾端NIL指针的每一条路径都包含相同数目的黑结点。 如果我们插入一个节点，并把他染红，则树的1235项原则都不会被破坏。如何保证原则4呢？调整的原则是把红色问题向上修正到根节点，最后把根节点染黑，来达到平衡。 我们先把插入的节点染红，然后进行修正操作： 插入修复情况1：当前结点的父结点是红色且叔叔结点是红色。 将当前结点的父结点和叔叔结点涂黑，祖父结点涂红。在以祖父节点为新的当前结点再做一遍。 A. 为了解决本节点和父节点都是红色，把父节点染黑。 B. 但是父节点的在子树多了个黑色，所以要把叔叔也染黑来平衡。 C. 此时爷爷节点的子树也多了个黑色，所以把他染红。 D. 爷爷节点被染红了上面的节点曾爷爷有可能是红的，在做一次。 插入修复情况2：当前结点的父结点是红色,叔叔结点是黑色，当前结点是其父结点的右子 对策：当前结点的父结点做为新的当前结点，以新当前结点为支点左旋。左旋后，本节点上移，把问题向上修正。可以转化到情况3 插入修复情况3：当前结点的父结点是红色,叔叔结点是黑色，当前结点是其父结点的左子 解法：父结点变为黑色，祖父结点变为红色，在祖父结点为支点右旋 A. 为了解决本节点和父节点都为红，把父节点染黑 B. 为了解决父节点在的子树多了一个黑色，把叔叔染红并右旋解决

C1W1: 什么是deep learning 单一神经元 deeplearning是模拟大脑的一种机器学习算法。以房价预测为例： 上图把房子面积作为输入X，房价作为输出Y，通过拟合得到了一个一次函数 $$ Y=aX+b $$ 这个函数的负值均视为0，即使用了ReLU函数作为神经元的激活函数做了处理。 $$ f(x) = \max(aX+b, 0) $$ Note: ReLU函数：f(x)=\max(0, x)，近年来使用ReLU函数代替sigmoid函数为计算速度做了巨大的提升。 看看更多特征的情况： 飞速发展 上图中可以看到传统算法和神经网络的效果的一个对比，在数据多的情况下神经网络有明显的优势。近年来以下的一些原因导致deep learning飞速发展成为主流 计算速度飞速提升，使得训练较大的神经网络成为可能 数据变多（labeled data 变多） 生命周期 一个典型的深度学习的流程，即是一个Idea-Code-Train 的循环 C1W2: 基本的神经网络 问题描述 这里从一个简单的问题开始说起：识别一个64x64的图像是否为猫： 每个像素有RGB三个值组成，64*64个像素就是12228个值。所以X可以表示为一个12228维的向量。Y则是0或1（是或不是猫咪）。 这里需要很多(X, Y)组成的labeled data数据用来学习。每个样本用如下的数学方式表示： $$ X\in R^{n_x}, Y\in{0,1} \qquad 其中n_x为每个图片的维度(12288) $$ 训练集可以用很多样本表示： $$ \textrm{m training examples: } \{(X^{(1)}, Y^{(1)}), (X^{(2)}, Y^{(2)}), … ,(X^{(3)}, Y^{(3)})\} $$ 其中每个X都有n_x列，所以整个样本集可以表示为 $$ X\in R^{n_x\times m},Y \in R^{1 \times m} $$ 逻辑回归 Sigmoid函数 在开始正题之前，先看一个函数：

命令行参数 gdb有下面几种运行方式： 1 2 3 4 5 6 // 1. 通过coredump文件，或者存在的进程id分析，不会拉起新进程 gdb [options] [executable-file [core-file or process-id]] // 2. 带参数运行程序 gdb [options] --args executable-file [inferior-arguments ...] // 3. redhat等含有用于调试python的工具 // gdb [options] [--python|-P] script-file [script-arguments ...] 几个值得注意的参数： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 // 和上面的类似，使用参数指定的 --args Arguments after executable-file are passed to inferior --core=COREFILE Analyze the core dump COREFILE. --pid=PID Attach to running process PID.

CAP Brewer’s CAP Theorem, 2009 CAP理论是分布式系统的基石，他指出了分布式系统的以下特性： Consistency 强一致性(返回的数据时刻一致) Availability 高可用性(服务一直可用，响应时间正常) Tolerance of network Partition 分区容错性(保证有机器宕机服务依然正常) CAP理论表明，一个分布式系统不可能同时满足一致性，可用性和分区容错性这三个需求， 最多只能同时满足两个。证明可以看上面的链接。 所以架构师往往要做出牺牲某一特性的选择： CP：金融行业的数据库，价格昂贵，符合ACID CA：传统关系型数据库，用于小型系统或单机系统 AP：key-value数据库，现代UGC服务基本都是这种架构，用最终一致性来换取高可用和分区容错性。 电商：牺牲少量的可用性和一致性，比较平衡，符合BASE ACID 老生常谈的数据库事务的特性： 原子性(Atomicity) 事务中有失败，立即回滚到执行前。没有失败，全部成功 一致性(Consistency) 事务执行后数据的约束没有被破坏 隔离性(Isolation） 事务之间不交叉进行 持久性(Durability） 事务完成，永久储存 BASE 可伸缩性最佳实践：来自eBay的经验 BASE理论是对CAP理论的延伸，核心思想是即使无法做到强一致性（CAP的Consistency），但应用可以采用适合的方式达到最终一致性，来保证系统的容量和可用性。 Basically Availble （基本可用） 基本可用是指系统只保证核心可用，在访问量突增时采用有损服务的策略，让部分用户使用降级的服务。 什么是基本可用的服务？以秒杀为例： 逻辑有损：秒杀时只执行重要逻辑，加载资源可以先使用预加载的或者小图等 业务有损：秒杀需要会员、抢秒杀资格 流程有损：比如秒杀时前段丢掉大部分请求，从后端少量请求中选取中奖的请求处理 Soft-state （软状态/柔性事务） “Soft state” 可以理解为"无连接"的, 而 “Hard state” 是"面向连接"的。换句话说，软状态的数据库可能存在很多中间状态，不同节点到达最终统一的状态前会有延迟（如异步复制）。 Eventual Consistency （最终一致性） 并非时刻保持一致，所有复制节点在某段时间后保持一致。 最终一致性是弱一致性的一种特例： Step 1. A首先write了一个值到存储系统 Step 2. 存储系统保证在A,B,C后续读取之前没有其它写操作更新同样的值 Step 3. 最终所有的读取操作都会读取到最A写入的最新值 从A写入到读取操作读取成功有一定的时间，即不一致性窗口。如果没有失败发生的话，“不一致性窗口”的大小依赖于以下的几个因素：交互延迟，系统的负载，以及备机slave的个数。最终一致性方面最出名的系统可以说是DNS系统，当更新一个域名的IP以后，根据配置策略以及缓存控制策略的不同，最终所有的客户都会看到最新的值。 在下一篇文章的中，会表明只要集群$V_r + V_w \leq N$，即此时读取和写入操作是不重叠的， 就能保证最终一致性。这个时候不一致性的窗口依赖于存储系统的异步实现方式，不一致性的窗口大小就等于从更新开始到所有的节点都异步更新完成之间的时间。

sizeof 是什么 首先明确一点，sizeof是运算符，不是函数。运算符是一个对于编译器来说的概念，是由编译器处理的，在程序编译好之后所有的sizeof都已经被替换为实际的值。类似的还有decltype。所以像 1 sizeof(++i); 这类的语句是不会改变i的值的。在C99之后，sizeof增加了一些运行时特性，可以算出可变数组的大小，像这样： 1 2 3 4 int num; scanf("%d", &num); //input 4 int arr[num]; sizeof(arr); //output 16 sizeof 怎么用 sizeof 支持下面的语法： 1 2 sizeof(type) (1) 以字节数返回type类型对象表示的大小 sizeof expression (2) 以字节数返回expression的类型对象表示的大小 其中，sizeof(char)、 sizeof(signed char)以及sizeof(unsigned char)始终返回1。 sizeof不能用于函数类型、不完整类型（含void）或位域左值。在一些编译器里，sizeof(void)会返回0，但这是没有定义的。 普通的sizeof 几个上面用法的例子： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 int main(void) { // type argument: printf("sizeof(float) = %u\n", sizeof(float)); //4 printf("sizeof(void(*)(void)) = %u\n", sizeof(void(*)(void))); //4 printf("sizeof(char[10]) = %u\n", sizeof(char[10])); //10 // expression argument: printf("sizeof 'a' = %u\n", sizeof 'a'); // 'a'的类型是int, 4 // printf("sizeof main = %zu\n", sizeof main); // 错误：函数类型 printf("sizeof &main = %u\n", sizeof main()); //类型为返回值int, 4 printf("sizeof \"hello\" = %u\n", sizeof "hello"); // 类型为char[6], 6 printf("sizeof(\"12345\" + 1) = %u\n", sizeof("12345" + 1)); // 类型为指针, 4 } 需要注意的是，在函数传参等数组退化为指针的时候sizeof返回的当然是指针大小，切忌用它来计算数组大小。

一个100行左右的简单线程池。用到了std::mutex和std::thread等新特性。 线程池模型 首先把每个函数抽象为一个任务(Task)，任务的过程就是调用这个Task的run函数。 然后把线程池中的线程封装为一个线程类（Thread），一直等待调度器分配任务（空闲状态），如果有任务分配立即进入忙状态。等任务执行结束再次变为空闲状态。 最后是一个调度器类（TreadPool），包含任务队列（随时添加新任务），和一个包含了Thread的vector（线程池中的线程）。如果任务队列非空，调度器每次从中取出一个任务，然后轮询线程池，搜寻空闲线程并把这个任务交给线程。 模型如下图所示： 代码实现 下面的代码实现了上述模型。其中Task类通过睡眠一定的秒数模拟任务，可以看到T1先执行完毕（1秒完毕），T2和T3在之后同时完毕，说明调度非常成功。 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 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 //linux, g++ -std=c++14 -o t *.

各种锁的基本概念以及在C++里的使用，还有C的一个生产消费模型。 操作系统的知识 概念 临界区：访问和操作共享数据的代码段 避免死锁：嵌套加锁时按顺序加锁, 防止发生饥饿 原子操作：atomic_t 自旋锁 自旋锁：请求该锁的线程在等待时自旋（特别耗费处理器时间），所以只能轻量级加锁（一般锁的时间小于上下文切换的开销）。 注意：对数据而不是对代码加锁。 读写自旋锁：读时(允许读，不允许写)，写时（不允许读，不允许写）。 注意：不能把读锁升级为写锁，不然会死锁。读写操作要清晰地分开。 信号量 信号量：请求锁的进程在等待时加入等待队列并睡眠。一般用于长时间加锁（唤醒、睡眠、加入队列都是很大的开销）。 通过P/V或者down()/up()操作来控制允许同时进行的线程数。信号量减一就等同与获取一个锁，锁为负数时线程就会进入等待队列。 0/1信号量（互斥信号量）：只允许同时一个线程执行。 计数信号量：允许同时多个线程执行。 读写信号量：互斥信号量的一种。 互斥体 互斥体(mutex): 可以睡眠的强制互斥锁。比信号量更加首选。 mutex和自旋锁的区别： 需求 加锁方法 低开销加锁 优先自旋锁 短期加锁 优先自旋锁 长期加锁 优先mutex 中断上下文加锁 只能自旋锁 持有锁时需要睡眠 只能mutex C++11 的线程库 std::thread std::thread用于创建一个执行的线程实例，所以它是一切并发编程的基础，使用时需要包含头文件，它提供了很多基本的线程操作，例如get_id()来获取所创建线程的线程 ID，例如使用join()来加入一个线程等。 std::mutex, std::unique_lock, std::lock_guard 使用std::mutex创建互斥体，std::unique_lock上锁。由于C++保证了所有栈对象在声明周期结束时会被销毁，所以这样的代码是异常安全的。无论发生异常还是正常结束，都会自动调用unlock()。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 #include <iostream> #include <thread> #include <mutex> std::mutex mtx; void block_area() { std::unique_lock<std::mutex> lock(mtx); //.

本部分介绍了c++11的容器、智能指针和正则。 std::array 代替原来的c数组，提供了size()，empty()，大小比较以及迭代器。 注意： 声明的第二个模板参数必须是编译期常量 不能隐式转换为指针，调用data()返回c数组地址 1 2 3 4 5 6 7 8 9 std::array<int,4> arr = {1,2,3,4}; // C 风格接口传参 // foo(arr, arr.size()); // 非法, 无法隐式转换 foo(&arr[0], arr.size()); foo(arr.data(), arr.size()); // 使用 `std::sort` std::sort(arr.begin(), arr.end()); std::forward_list 单向实现的列表，提供了O(1)的插入，并且比双向更省空间。 无序容器 传统 C++ 中的有序容器 std::map/std::set，这些元素内部通过红黑树进行实现，插入和搜索的平均复杂度均为 O(log(size))。在插入元素时候，会根据 < 操作符比较元素大小并判断元素是否相同，并选择合适的位置插入到容器中。当对这个容器中的元素进行遍历时，输出结果会按照 < 操作符的顺序来逐个遍历。 而无序容器中的元素是不进行排序的，内部通过 Hash 表实现，插入和搜索元素的平均复杂度为 O(constant)，在不关心容器内部元素顺序时，能够获得显著的性能提升。 C++11 引入了两组无序容器：std::unordered_map, std::unordered_multimap 和std::unordered_set, std::unordered_multiset。 它们的用法和原有的std::map/std::multimap/std::set/set::multiset基本类似。 std::tuple 提供了N元组的数据结构。 该数据结构在cpp14中还不够完善。 智能指针 在传统 C++ 里我们使用 new 和 delete 去『记得』对资源进行释放。而 C++11引入了智能指针的概念，使用了引用计数的想法，让程序员不再需要关心手动释放内存。这些智能指针包括 std::shared_ptr/std::unique_ptr/std::weak_ptr，使用它们需要包含头文件 <memory>。