ARTS-第-15-期

阅读本文大概需要 10 分钟。

每周完成一个 ARTS

Algorithm 来源 LeetCode 18.4Sum。

Review 关于Linux IO模式及 select、poll、epoll 的知识。

Tip 分享 TCP 模式和 UDP 模式在两个客户与服务器建立连接的区别。

Share 分享「信息素养」一些看法。

下面更新 ARTS 第 十五 周的内容。

1.Algorithm

18.4Sum。难度：[Medium]

【题意】

Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note:

The solution set must not contain duplicate quadruplets.

Example:

Given array nums = [1, 0, -1, 0, -2, 2], and target = 0.A solution set is:[ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2]]

给出一个序列，找出四个数字之和为给定的 target。

【思路】

这道题是 sum3 的加强版，但是解决思路都是一样的，只不过就是多了一层循环的判断，为了去重，这里我采用了set 容器，如果新加入的数在原先的容器存在过，则不能加入，另外就是几个剪枝的地方，细节处理跟 sum3 差不多。

时间复杂度 O（n^3），空间复杂度 O（n）。

【参考代码】

/*

Author: rongweihe

Time: 2019-01-25

*/

classSolution{

public:

vector>fourSum(vector &nums,inttarget){

set>res;

sort(nums.begin(),nums.end());//sort the nums

if(nums.empty() || nums.front()>|| nums.back()

for(inti=; i

if(i >&& nums[i] == nums[i -1])continue;//剪枝，去掉重复的

for(intj=i+1; j

if( j > i+1&& nums[j]==nums[j-1])continue;//剪枝，去掉重复的

intthree = j+1,four = nums.size()-1;//枚举第三，四个数

while(three

intsum = nums[i]+nums[j]+nums[three]+nums[four];

if(sum == target){

vectortmp;

res.insert(tmp);

while(three

while(three

++three;--four;

}

elseif(sum

else--four;

}

}

}

returnvector>(res.begin(),res.end());

}

};

/*result*/

Runtime:20ms, faster than81.43% of C++ online submissionsfor4Sum.

2.Review

Linux IO模式及 select、poll、epoll详解

本次 Review 阅读了 一篇关于Linux IO模式及 select、poll、epoll 的知识。结合 《UNPVTN》学到了很多。

因为本篇文章篇幅较长，为了不影响阅读，增强美观体验，拆为上下篇。

上篇

总的来说，同步 IO 和异步 IO，阻塞 IO 和非阻塞 IO分别是什么？到底有什么区别？不同的人在不同的上下文给出的答案是不同的，所以先限定一下本文的上下文。本文讨论的背景是 Linux 环境下的 network IO。

一些概念说明

1）用户空间和内核空间

现在操作系统都是采用虚拟存储器，那么对 32 位操作系统而言，它的寻址空间（虚拟存储空间）为 4G （2的 32 次方）。

操作系统的核心是内核，独立于普通的应用程序，可以访问受保护的内核空间，也有访问底层硬件设备的所有权限。

为了保证用户进程不能直接操作内核（kernel），保证内核的安全，操作系统将虚拟空间划分为两个部分：一个部分为内核空间；一个部分为用户空间。针对 linux 操作系统而言，将最高的 1G 字节（从虚拟地址0xC0000000到0xFFFFFFFF）供内核使用，称为内核空间；而将较低的3G字节（从虚拟地址0x00000000到0xBFFFFFFF），供各个进程使用，称为用户空间。

2）进程切换

为了控制进程的执行，内核必须有能力挂起正在 CPU 上运行的进程，并且恢复以前挂起的某个进程的执行。这种行为称为进程切换。因此可以说，任何进程都是在操作系统内核的支持下运行的，是与内核紧密相关的。从一个进程的运行转到另一个进程上运行，这个过程必须经过下面这些变化：

【1】保存处理机上下文；包括程序计数器和其它寄存器

【2】更新进程控制块PCB信息

【3】把新的进程的PCB移入相应的队列，如就绪，在某件事上阻塞等待队列

【4】选择另一个进程执行，并更新其PCB

【5】更新内存管理的数据结构【6】恢复处理机上下文。总而言之就是很消耗资源。

3）进程的阻塞

正在执行的进程，由于期待的某些事件未发生，如请求系统资源失败，等待某种操作的完成，新数据尚未到达或无新工作等。则有系统自动执行阻塞原语（block），使得自己由运行状态变为阻塞状态。可见，进程的阻塞是进程自身的一种主动行为，也只有处于运行状态的进程（获得CPU）才有可能将其转为阻塞状态。当进入阻塞状态，是不占用CPU资源的。

4）IO 模式

对于第一次 IO 访问（以read举例），数据会先被拷贝到操作系统内核的缓冲区中，然后才会从操作系统内核的缓冲区拷贝到应用程序的地址空间。

所以说，当一个read 操作发生时，会经历两个阶段：

1. 等待数据准备；

2. 将数据从内核拷贝到进程中。对于一个套接字上的输入操作，第一步通常涉及等待数据从网络中到达。当所有等待分组到达时，它被复制到内核中某个缓冲区。第二步就是把数据从操作系统的缓冲区中复制到应用进程的缓冲区。

正因为这两个阶段，Linux 有以下的5种IO模式。

（1）阻塞式 IO；

（2）非阻塞式IO；

（3）IO 复用；

（4）信号驱动IO（SIGIO）；

（5）异步IO；

下篇继续分享五种 IO 模型的具体内容和比较。

3 Tip

继续从项目中学习 Unix 网络编程

分享 TCP 模式和 UDP 模式在两个客户与服务器建立连接的区别。

对于 TCP 而言，提供的是一个并发服务器。其中通过 fork 实现子进程处理不同的请求。

而对于 UDP 而言，没有对 fork 的调用，因此单个服务器进程就得处理所有的客户。

一般来说，大多数 TCP 服务器都并发的，UDP 服务器是迭代的。

事实上每个UDP套接字都有一个接收缓冲区，到达该套接字的每个数据报都进入这个套接字接收缓冲区。当进程调用 recvfrom时，缓冲区中的下一个数据报以 FIFO (先入先出)顺序返回给进程。

这样，在进程能够读该套接字中任何已排好队的数据报之前，如果有多个数据报到达该套接字，那么相继到达的数据报仅仅加到该套接字的接收缓冲区中。然而这个缓冲区的大小是有限的。

下图总结了TCP 客户/服务器在两个客户与服务器建立连接时的情形。

下图总结了 UDP 客户/服务器在两个客户与服务器建立连接时的情形。

我们可以看到：

对于 TCP 来说，服务器主机上有两个已连接的套接字，其中每一个都有各自的套接字接受缓冲区。

对于 UDP 来说，其中只有一台服务器进程，它仅有的单个套接字用于接受处理所有到达的数据报并发回所有的响应，该套接字有一个接受缓冲区用来存放所到达的数据报。

4Share

最近在逛 GitHub 的时候，发现了几个非常不错的计算机领域专业的 Repository，一方面对这些非常厉害的牛人佩服的同时，一方面也在思考一个问题：在互联网时代，面对浩如烟海的资讯和各种参差不齐的资料，我们如何进行有效的筛选，甄别出对我们最有用，最精炼的知识？

学了很多知识，但总是忘得很快，知识广度越大越容易接纳新东西，但从考察角度来说，自然是对某个方面了解越深越好。那些大而全的经典著作虽然每本都是经典中的经典，但实际工作中可能大部分只用到了其中的一小部分。

想起耗子叔（知乎 ID：陈皓）说过的：你有没有发现，在知识的领域也有阶层之分，那些长期在底层知识阶层的人，需要等着高层的人来喂养，他们长期陷于各种谣言和不准确的信息环境中，于是就导致错误或幼稚的认知，并习惯于那些不费劲儿的轻度学习方式，从而一点点地丧失了深度学习的独立思考能力，从而再也没有能力打破知识阶层的限制，被困在认知底层翻不了身。

不知道上面几段话，对大家有没有一些启发，对我个人而言，耗子叔其实讲的就是一种「信息素养」的问题。

信息输入给你，你会不会查找信息的来源？比如说当你看到标题里面带着名人名言的时候，你有没有去核实一下这个人说过类似的话没有？当你看到同一篇新闻稿你会不会稍微花点时间去看一下其他媒体的新闻来求证信息的真伪。

每天面对这么多的知识，我们要学会筛选有价值的知识，养成一种批判性思维，一种怀疑的精神，一种好奇心。学会将时间和重点关注在精炼的知识本身。