ARTS-第-18-期

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

每周完成一个 ARTS

Algorithm 来源 LeetCode 438. Find All Anagrams in a String。

Review 关于 IO 多路复用之 select，poll，epoll 详解。

Share 分享有关于批判性思维的一些思考。

1.Algorithm

438. Find All Anagrams in a String难度：[Eazy]

【题意】

Given a string s and a non-empty string p, find all the start indices of p's anagrams in s.

Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.

The order of output does not matter.

Example 1:

Input:s: "cbaebabacd" p: "abc"Output:[0, 6]Explanation:The substring with start index = 0 is "cba", which is an anagram of "abc".The substring with start index = 6 is "bac", which is an anagram of "abc".

Example 2:

Input:s: "abab" p: "ab"Output:[0, 1, 2]Explanation:The substring with start index = 0 is "ab", which is an anagram of "ab".The substring with start index = 1 is "ba", which is an anagram of "ab".The substring with start index = 2 is "ab", which is an anagram of "ab".

【解法一】

这道题是求这道题是给出两个字符串，源字符串 s 和匹配字符串 p，让我们在 源字符串 s 中找出匹配字符串 p 的所有变位字符串的位置，所谓变位字符串就是字符种类个数相同但是顺序可以不同的两个字符串。

首先想到的一种暴力解法：先在匹配字符串 p 中统计每个字符出现的次数，然后从源字符串 s 开头开始查找，每次寻找 p 个长度的字符串，并且判断每次寻找的 p 个长度的字符串里字符种类是否和匹配字符串 p 相同，如果不相同则跳出循环，否则记录索引位置。

【解法二】

下面这种利用 滑动窗口 Sliding Window 的方法也比较巧妙。建议手动写写代码调试一遍，领会该算法的精髓。

这种方法的思想也是首先统计匹配字符串 p 的字符个数，然后利用两个变量 left 和 right 表示滑动窗口的左右边界，另外用 cnt 表示匹配字符串 p 中需要匹配的字符个数。

注意 C++ 中的 后增 ++ 和后减 – 操作执行的是先赋值后运算，所以如果右边界的字符已经在哈希表中了即哈希表出现次数大于等于 1，说明该字符在 p 中有出现，则匹配的字符数减一，cnt 自减 1。

如果此时 cnt 减为 0 了，说明 p 中的字符都匹配上了，那么将此时左边界加入结果 res 中。

如果此时 right 和 left 的差正好为 p 的长度，说明此时应该去掉最左边的一个字符，并且此时应该还原哈希表 m 中该字符出现次数，即如果该字符在哈希表中的个数大于等于 0，说明该字符是 p 中的字符。

2.Review

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

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

继续分享 IO 多路复用之 epoll 详解。

第 17 期我们讲到了Select poll epoll 都是多路复用的机制。

IO多路复用就是通过一种机制，一个进程可以监视多个描述符，一旦某个描述符就绪（一般是读就绪或写就绪）能够通知应用程序进行相应的读写操作，但select，poll，epoll本质上都是同步IO，因为它们需要在读写事件就绪后自己负责进行读写，也就是说这个读写操作是阻塞的，而异步IO则无需自己负责进行读写。

在 第 17 期 里，我们可以看到，select 和 poll 都需要在返回后，通过遍历文件描述符来获取已经就绪的 socket，事实上，同时连接的大量客户端在同一时刻可能只是很少的处于就绪状态，因此随着监视的描述符数量的增长，其效率也会线性下降。

epoll 函数

epoll 操作过程需要三个接口，分别如下

int epoll_create(int size);

int epoll_ctl(int epfd, int op, int fd, struct epoll_event *event)；

int epoll_wait(int epfd, struct epoll_event * events, int maxevents, int timeout);

其中

int epoll_create(int size)：创建一个 epoll 句柄，size 用来告诉内核这个监听的数目一共有多大。这个参数不同于 select 中的第一个参数，给出最大监听的 fd+1 的值，参数 size 不是限制了 epoll 所能监听的描述的最大数，只是对内核初始化分配数据结构的一个建议。当创建好一个 epoll 句柄之后，它就会占用一个 fd 值，在 Linux 环境下通过 /proc/进程ID/fd 查看这个 fd，所以在用完 epoll 之后，必须使用 close 函数关闭，否则会导致 fd 被耗尽。

int epoll_ctl(int epfd, int op, int fd, struct epoll_event event)：该函数是对指定描述符 fd 执行 OP 操作。

– epfd 是 epoll_create() 函数的返回值。

–op 表示 操作，用三个宏来表示：添加 EPOLL_CTL_ADD，删除 EPOLL_CTL_DEL，修改EPOLL_CTL_MOD。分别表示添加、删除和修改对 fd 的监听事件。

–fd 表示需要监听的 fd（文件描述符）。

–epoll_event：告知内核需要监听什么事。

struct epoll_event 结构如下：

structepoll_event{

__uint32_tevents;/* Epoll events */

epoll_data_tdata;/* User data variable */

};

//events可以是以下几个宏的集合：

EPOLLIN ：表示对应的文件描述符可以读（包括对端SOCKET正常关闭）；

EPOLLOUT：表示对应的文件描述符可以写；

EPOLLPRI：表示对应的文件描述符有紧急的数据可读（这里应该表示有带外数据到来）；

EPOLLERR：表示对应的文件描述符发生错误；

EPOLLHUP：表示对应的文件描述符被挂断；

EPOLLET： 将EPOLL设为边缘触发(Edge Triggered)模式，这是相对于水平触发(Level Triggered)来说的。

EPOLLONESHOT：只监听一次事件，当监听完这次事件之后，如果还需要继续监听这个socket的话，需要再次把这个socket加入到EPOLL队列里

int epoll_wait(int epfd,struct epoll_event * events,int maxevents,int timeout)等待 epfd 上的 io 事件，最多返回 maxevents 个事件。参数 events 表示从内核得到事件的集合；maxevents 表示内核这个 events 有多大；这个 maxevents 的值不能大于创建 epoll_create() 的 size(); 参数 timeout 是超时时间（毫秒，0 会立即返回）该函数返回需要处理的事件数目，如返回 0 表示超时。

工作模式

epoll 对文件描述符的操作有两种模式：LT（level trigger ）和ET（edge trigger），LT模式是默认模式，LT模式与ET模式区别如下：

LT模式：当 epoll_wait 检测到描述符事件发生并将此事件通知应用程序，应用程序可以不立即处理该事件。下次调用 epoll_wait时，会再次响应应用程序并通知此事件。

ET模式：当 epoll_wait 检测到描述符事件发生并将此事件通知应用程序，应用程序必须立即处理该事件。如果不处理，下次调用 epoll_wait 时，不会再响应应用程序并通知此事件。

LT模式：LT（level trigger）是缺省模式，并且同时支持阻塞和非阻塞，在这种模式中，内核告诉你一个文件描述符是否就绪了，然后你可以对这个就绪的 fd 进行 IO 操作。如果你不做任何操作，内核还是会继续通知。

ET模式：ET（edge trigger）是高速模式，只支持阻塞套接字，在这种模式下，当描述符从未就绪变为就绪时，内核通过 epoll 告诉应用进程，然后它会假设你知道文件描述符已经就绪，并且不会再为那个文件描述符发送更多的就绪通知，直到你做了某些操作导致那个文件描述符不在变为就绪状态了(比如，你在发送，接收或者接收请求，或者发送接收的数据少于一定量时导致了一个 EWOULDBLOCK 错误）。但是请注意，如果一直不对这个 fd 做 IO 操作（从而导致它再次变为未就绪），内核不会发送更多的通知。

ET 模式在很大程度上减少了 epoll 事件被触发的次数，因此效率要比 LT 高，epoll 工作在ET模式的时候，必须使用阻塞套接字，以避免由于一个文件句柄的阻塞读/阻塞写操作把处理多个文件描述符的任务 dead 饿死。

关于 epoll 对文件描述符的两种工作模式，目前理解的还不是很深刻，后续有新的体会会持续分享。

3 Tip

文章灵感是来自作者 botoo，博客

：http://www.cnblogs.com/botoo/p/8622379.html。最近自己也在学习 itchat 库的使用，所以我把里面的代码改了下。

其中 get_news() 函数是用来获取金山词霸每日一句，英文和翻译。另一个函数 send_news() 是用来给你的好友每天定时发送消息。

最后运行程序，就会定时发送消息给你最心爱的人。运行结果如下。