ARTS-第-16-期

ARTS-第-16-期

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

每周完成一个 ARTS

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

1.Algorithm

31. Next Permutation 链接 难度：[Medium]

【题意】

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place and use only constant extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column。

【思路】

这道题给出一个当前的排列，让我们求下一个排列的顺序，一个直观的暴力的做法，举一个例子更好的说明：

由题目中给的例子可以看出来，如果给定数组是降序排列，则说明当前是全排列的最后一种情况，则下一个排列就是最初始的排列，我们再来看下面一个例子，有如下的一个数组

1　　2　　7　　4　　3　　1

下一个排列为：

1　　3　　1　　2　　4　　7

那么是如何得到的呢？

我们通过观察原数组可以发现，如果从末尾往前遍历，数字逐渐变大，到了 2 才减小，接着我们再从后往前找第一个比 2 大的数字是 3，那么我们交换 2 和 3，再把此时 3 后面的所有数字转置即可，步骤如下：

1　　2　　7　　4　　3　　1

1　　2　　7　　4　　3　　1

1　　3　　7　　4　　2　　1

1　　3　　1　　2　　4　　7

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

【参考代码】

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

/*
Author: rongweihe
Time:  2019-02-03
*/
class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int i,j,n = nums.size();
        if(n<=0) return;
        for(i=n-2; i>=0; --i){
            if(nums[i+1] > nums[i])
            {
                for(j=n-1; j>i; --j)
                {
                    if(nums[j]>nums[i]){
                        break;
                    }
                }
                swap(nums[j],nums[i]);  
                reverse(nums.begin()+i+1,nums.end());
                return;
            }
        }
        // 如果是逆序的情况，直接转置
    reverse(nums.begin(),nums.end());
   }
};

/*result*/
Runtime: 8 ms, faster than 27.90% of C++ online submissions for Next Permutation.

2.Review

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

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

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

下篇

上篇分享了有关用户空间和内核空间，进程切换，进程的阻塞，IO 模式的概念说明，本篇继续分享五种 IO 模型的具体内容和比较。

1）阻塞式 IO 模型

最流行的 IO 模型，就是阻塞式IO（blocking，IO）模型，在 Linux 环境中，默认情况所有套接字（socket）都是阻塞的。以 UDP 数据报套接字为例：

进程调用 recvfrom 函数，其系统调用直到数据报到达且被复制到应用进程的缓冲区中或者发生错误才返回。最常用的错误是系统调用被信号中断，注意的是进程在从调用 recvfrom 开始到它返回的整段时间内是被阻塞的，也就是说数据被拷贝到操作系统内核的缓冲区中是需要一个过程的。而在用户进程这边，整个进程会被阻塞（当然，是进程自己选择的阻塞）。

当 kernel 一直等到数据准备好了，它就会将数据从 kernel 中拷贝到用户内存，然后 kernel 返回结果，用户进程才解除 block 的状态，重新运行起来。recvfrom 成功返回后进程才开始处理数据报。

所以，阻塞 IO 的特点就是在 IO 执行的两个阶段都被 block 了。

2）非阻塞式 IO 模型

《Unix 套接字编程》：“进程把一个套接字设置为非阻塞是在通知内核：当所请求的 IO 操作非得把本进程投入睡眠才能完成时，不要把本进程投入睡眠，而是返回一个错误。前三次调用 recvform函数时没有数据报返回，因此内核转而立即返回一个EWOULDBLOCK 错误。第四次调用时有一个数据报准备好，它被复制到应用进程缓冲区中，于是recvform成功返回，我们接着处理数据。

当一个应用进程像这样对一个非阻塞描述符循环调用 recvform 时，我们称之为轮询（polling），应用进程持续轮询内核，以查看某个操作是否就绪。这么做往往耗费大量 CPU 时间，不过这种模型偶尔也会遇到，通常是在专门提供某一种功能的系统中才有。”

也就是说，当用户进程发出 read 操作时，如果 kernel 中的数据还没准备好，它不会阻塞用户进程而是返回一个错误（error），从用户进程角度讲，它发起一个 read 操作之后，并不需要等待，而是马上得到了一个结果，当用户得到这个结果（error）时它就知道数据还没准备好，于是用户进程还可以再次发出 read 操作，一旦 kernel 中数据准备好了，并且又再次收到了用户的 system call，那么它马上就将数据拷贝到用户内存，然后返回。

所以，非阻塞 IO 的特点是用户进程需要不断的主动询问 kernel 数据好了没有。

3） IO 多路复用

《Unix 套接字编程》：“有了 I/O 复用（IO multiplexing），我们就可以调用 select 或 poll，epoll阻塞在这些系统调用中的某一个，而不是阻塞在真正的 IO 系统调用上。

我们阻塞于 select 调用，等待数据报套接字变为可读。当 select 返回套接字可读这一条件时，我们调用 recvfrom 把所读数据报复制到应用进程缓冲区。”

IO 多路复用的好处就在于单个process 就可以同时处理多个网络连接的 IO，基本原理就是 select，poll，epoll，这个 function 会不断的轮询所负责的所有 socket，当某个套接字可读也就是数据到达了，就通知用户进程。

也就是说，当用户进程调用了 select，那么整个进程就会被阻塞。同时，kernel 会“监视”所有select负责的 socket，当任何一个 socket 中的数据都准备好了，select 就会返回。这个时候用户进程调用read 操作将数据从 kernel 拷贝到用户进程缓冲区。

我们看到这个图，事实上由于使用 select 需要使用两个 system call 而不是单个，但是优势在于它能同时处理多个连接。所以，如果处理的连接数不是很高的话，使用 select/epoll 的 web server 不一定比使用 multi-threading + blocking IO 的 web server 性能更好，可能延迟还更大。select/epoll 的优势并不是对于单个连接能处理得更快，而是在于能处理更多的连接。）

所以，I/O 多路复用的特点是通过一种机制一个进程能同时等待多个文件描述符，而这些文件描述符（套接字描述符）其中的任意一个进入读就绪状态，select() 函数就可以返回。

4） 异步IO模型（asynchronous IO）

《Unix 套接字编程》：“一般来说，这些函数的工作机制就是：告知内核启动某个操作，并让内核在整个操作（包括将数据从内核复制到我们自己的缓冲区中）完成后通知我们。我们调用 aio_read 函数（POSIX 异步 IO 函数以 aio_read 或 lio_ 开头），给内核传递描述符，缓冲区指针。缓冲区大小和文件偏移，并告诉内核当整个操作完成时如何通知我们。该系统调用立即返回，而且在等待 IO 完成期间，我们的进程不被阻塞。”

用户进程发起 read 操作之后，立刻就可以开始去做其他的事情，而另一方面，从内核的角度，当它受到一个 asynchronous read 之后，首先它会立即返回，所以不会对用户进程产生任何阻塞。然后内核会等待数据准备完成之后，将数据拷贝到用户内存的缓冲区中，当这一切完成之后，内核会给用户进程发送一个信号（signal），表示 read 操作已经完成。

5）信号驱动式 IO 模型

用户进程也可以用信号，让内核在描述符就绪时发送 SIGIO 信号通知用户进程。这种模型称为信号驱动式 IO。

《Unix 套接字编程》：“首先开启套接字的信号驱动式 IO 功能，并通过 sigaction 系统调用安装一个信号处理函数。该系统调用将立即返回，用户进程则继续工作，也就是说用户进程并没有被阻塞。当数据报准备好读取时，内核就为该进程产生一个 SIGIO 信号。随后用户进程既可以在信号处理函数中调用 recvfrom 读取数据报，并通知主循环数据已经准备好待处理；也可以立即通知主循环，让它读取数据报。”

无论何时处理 SIGIO 信号，这种模式的优势在于等待数据报到达期间进程不被阻塞。主循环可以继续执行，只要等待来自信号处理函数的通知：既可以是数据已经准备好被处理；也可以是数据报已经准备好被读取。

6）五种IO模型比较：

对比以上五种模型可以看出，前4种模型主要区别在于第一阶段，因为它们的第二阶段是一样的：在数据从内核复制到调用者的缓冲区期间，进程阻塞于 recvfrom 调用，而异步 IO 模型在这两个阶段都要处理，从而不同于其它模型。

同步（synchronous）IO和异步（asynchronous）IO的对比：

同步 IO 操作导致请求进程阻塞，知道 IO 操作完成。

异步 IO 操作不导致请求进程阻塞。

3 Tip

继续从项目中学习 Unix 网络编程， 分享 名字与地址转换 的相关内容。

gethostbyname 和 gethostbyaddr 在主机名字与 IPv4 地址之间进行转换。

getserverbyname 和 getserverbyport 在服务器名字与端口号之间进行转换。

getaddrinfo 和 getnameinfo 分别用于主机名字和IP地址之间 以及服务名字和端口号之间的转换。

域名系统（Domain Name System，DNS）主要用于主机名字与 IP 地址之间的映射。主机名既可以是一个简单名字，也可以是一个全限定域名。

解析器和名字服务器：每个组织机构往往运行一个或多个名字服务器（name server），它们通常就是所谓的 BIND 程序，诸如我们常见的编写的客户和服务器等应用程序通过调用称为解析器（resolver）的函数库中的函数接触 DNS 服务器。常见的解析器函数是将 gethostbyname 和 gethostbyaddr ，前者把主机名映射成 IPv4 地址，后者则执行相反的映射。

下图展示了应用程序，解析器和名字服务器之间的一个典型关系。现在考虑编写应用程序代码。解析器代码通常包含在一个系统函数库中，在构造应用程序时被链编（link-editing）到应用程序中。另有些系统提供一个由全体进程共享的集中式解析程序器守护进程，并提供向这个守护进程执行 RPC 的系统函数库代码。不论哪种情况，应用程序代码使用通常的函数调用来执行解析器中的代码，调用的典型函数就是 gethostbyname 和 gethostbyaddr 。

解析器代码通过读取其系统相关配置文件确定本组织机构的名字服务器所在的位置，在 Linux 系统下，文件 /etc/resolv.conf 通常包含本地名字服务器主机的 IP 地址。

这里要注意：

解析器使用 UDP 向本地名字服务器发出查询。如果本地名字服务器不知道答案，它通常就会使用 UDP 在整个英特网上查询其它名字服务器。如果答案太长，超出了 UDP 消息的承载能力，本地名字服务器和解析器就会自动切换到 TCP。

4 Share

趋势的力量

马上大家都要返乡过年了，除了吃喝玩乐之外，建议大家对几个方向重点关注下：

1. 你所在的城市/老家有变化没？

3. 家里人和村里人移动支付都在用了么？

4. 他们有在网上购物的习惯么？

5. 家里的消费状况是不是也变化了？

6. 村里是不是又掀起一波相亲的高潮？相亲有没有一个更好的形式？

等等等

这些变化，都是某种商业机会的细小的反应，别人只会吃喝玩乐，我们吃喝玩乐的同时，要多观察，多发现，多思考。

​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。