LongLong's Blog

26 June 2016

由于一些需求，需要在PC上读取超声波传感器的数据，而超声波传感器使用的是I²C/TTL接口，虽然可以使用TTL转USB来接入PC，但是TTL接口只能够支持同时连接两个超声波传感器，而这里可能需要使用6个。

想到的一只解决办法是将超声波传感器连接到Raspberry PI的GPIO的I²C接口上，然后PC和Raspberry PI使用WIFI进行通信。这里需要在Raspberry PI上启动一个TCP Server，PC通过调用此TCP Server的接口获取超声波传感器的测量数据。虽然也可以让Raspberry PI将超声波传感器的数据发送到PC，但这样就需要让超声波传感器一直处于工作状态，会带来较大的能耗。

1. 实现一个简单的Echo Server

Echo Server可以作为一个最简单的TCP Server的模版，通过简单的修改就可以实现其他的TCP通信服务。一般的TCP Echo Server实现大致如下，由于Raspberry PI中的主流编程语言是Python，以下代码均使用Python。

from SocketServer import BaseRequestHandler, TCPServer;

class ServerHandler(BaseRequestHandler):
    def handle(self):
        data = self.request.recv(1024);
        self.request.send(data);

server = TCPServer(('', 1987), ServerHandler);
server.serve_forever();

测试效果如下

Trying 127.0.0.1...
Connected to 127.0.0.1.
Escape character is '^]'.
Hello
Hello
Connection closed by foreign host.

这里使用了Python中的TCPServer框架，但一般的TCPServer框架所实现的方式基本是类似HTTP Server，即处理完成后就关闭连接，并不能支持连接的服务。而获取超声波传感器的频率可能是比较高的，因此如果每次都重新建立连接会产生较大的开销，同时也增加了测量的延迟。

2. Linux的Epoll系统调用

Epoll是Linux 2.6中支持的路复用IO接口，是对select/poll的增强版本，显著提高程序在大量并发连接中只有少量活跃的情况下的系统CPU利用效率。目前大多数Linux下的应用程序（Nginx Redis等）都使用了Epoll方式进行网络IO操作。同时Epoll提供了水平触发(LT)和边界触发(ET)两种IO事件。

3. 使用Epoll实现Echo Server

这里我们只能直接使用Epoll调用来实现连接复用的Echo Server，其中关键是将数据输出之后重新调整为接收数据的模式，其实现的代码大致如下

import socket;
import select;

#开启一个Socket
HOST = '';
PORT = 1987
sock = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
sock.bind((HOST, 1987));
sock.listen(1);

#初始化Epoll
epoll = select.epoll();
epoll.register(sock.fileno(), select.EPOLLIN);

#连接和接受数据
conns = {};
recvs = {};

try:
    while True:
        #等待事件发生
        events = epoll.poll(1);
        #事件循环    
        for fd, event in events:
            #如果监听的Socket有时间则接受新连接
            if fd == sock.fileno():
                client, addr = sock.accept();
                client.setblocking(0);
                #注册新连接的输入时间
                epoll.register(client.fileno(), select.EPOLLIN);
                conns[client.fileno()] = client;
                recvs[client.fileno()] = '';
            elif event & select.EPOLLIN:
                #读取数据
                while True:
                    try:
                        buff = conns[fd].recv(1024);
                        if len(buff) == 0:
                            break;
                    except:
                        break;            
                    recvs[fd] += buff;
                #调整输出事件
                if len(buff) != 0:
                    epoll.modify(fd, select.EPOLLOUT);
                else:
                #如果数据为空则连接已断开
                    epoll.modify(fd, select.EPOLLHUP);
            elif event & select.EPOLLOUT:
                #发送数据
                try:
                    n = conns[fd].send(recvs[fd]);
                    recvs[fd] = '';
                    #重新调整为接收数据
                    epoll.modify(fd, select.EPOLLIN);
                except:
                    epoll.modify(fd, select.EPOLLHUP);
            elif event & select.EPOLLHUP:
                #关闭清理连接
                epoll.unregister(fd);
                conns[fd].close();
                del conns[fd];
                del recvs[fd];
finally:
    epoll.unregister(sock.fileno());
    epoll.close();
    sock.close();

4. 测试效果

使用Telnet连接上Echo Server，先输入Hello，会返回Hello，再输入Hi，则会继续返回Hi

Trying 127.0.0.1...
Connected to 127.0.0.1.
Escape character is '^]'.
Hello
Hello
Hi
Hi

21 May 2016

在实际应用中经常会遇到需要对给定的文本进行关键词搜索的操作，而在关键词较少时，通常的做法是将文本对每一个关键词都进行一次匹配，而随着关键词数量的增加此种算法的效率下降会非常明显。而这里将给出一种给予TrieTree（字典树）的检索算法，能够达到对于关键词个数O(1)的检索效率。

1. TrieTree数据结构

TrieTree可以像字典一样进行数据的存储，例如对于PHP Perl Pear三个单词，用TrieTree进行存储的结果大致如下

<?php
$trie_tree = array(
    'P' => array(
        'H' => array(
            'P' => array(
            ),
        ),
        'e' => array(
            'r' => array(
                'l' => array(
                ),
            ),
            'a' => array(
                'r' => array(
                ),
            ),
        ),
    ),
);

多于多字节组成的编码，如GBK或UTF-8，这里也只需要按照其单子节的编码进行处理即可，因此算法并不依赖于文本的编码，只要保证关键词列表与待检索文本的编码一致即可。另外对于每一个节点还需要标注其是否是某个关键词的结尾，例如PHP和PHP5都是关键词，如果不进行结尾标记，在生成TrieTree时PHP这个关键词就相当于不存在了，当文本中只还有PHP关键词时将不能够匹配成功。

2. TrieTree生成和匹配算法

TrieTree节点包含两部分——子节点散列表和自身是否是某个词的结尾，生成算法是对每一个词，将其按字节插入到TrieTree的每一层中，并在结尾处做标记。匹配时是将文本从第一个字节开始按子节匹配，如果能够匹配到则返回(如果需要匹配到全部，则这里对匹配结果进行记录而不返回)，未能匹配到时，如果第一个字节就没有匹配到则将下一个字节做为开头进行递归匹配，不是第一个字节没有匹配到，则将此位置做为开头进行递归匹配。

<?php
class TrieTreeNode {
    public $h = array();
    public $b = false;    
}

class TrieTree {
    private $root;

    public function __construct() {
        $this->root = new TrieTreeNode();
    }

    public function init($file) {
        $fp = fopen($file, 'r');
        while (($buffer = fgets($fp)) != null) {
            //插入一个词
            $node = $this->root;
            $w = trim($buffer);
            $len = strlen($w);
            for ($i = 0; $i < $len; $i++) {
                //插入每一个字节
                $c = $w[$i];
                //如果不存在对应的节点则进行插入
                if (!array_key_exists($c, $node->h)) {
                    $next = new TrieTreeNode();
                    $node->h[$c] = $next;
                    $node = $next;
                } else {
                    $node = $node->h[$c];
                }
            }
            $node->b = true;
        }
    }

    protected function _match($text, $pos) {
        $len = strlen($text);
        //如果匹配位置已超过文本长度，则匹配失败
        if ($pos >= $len) {
            return false;
        }
        $node = $this->root;
        $match = '';
        for ($i = $pos; $i < $len; $i++) {
            $c = $text[$i];
            if (array_key_exists($c, $node->h)) {
                $match .= $c;
                $next = $node->h[$c];
                $node = $next;
                //匹配到结束为止，返回结果
                if ($next->b) {
                    //匹配的词和匹配的位置
                    return array('w' => $match, 'p' => $pos);
                }
            } else {
                //已到达TrieTree末端还未完成匹配，则退出后重新开始匹配
                break;
            }
        }
        //递归匹配
        return $this->_match($text, $i > $pos ? $i : $pos + 1);
    }

    public function match($text) {
        return $this->_match($text, 0);
    }
}

其时间复杂度只与关键词长（TrieTree高度）和待匹配的文本长度有关，与关键词的个数无关，在关键词非常多时仍能保持较好的性能。但TrieTree的生成过程与关键词的个数有关，如果每次匹配都重新生成TrieTree会丧失TrieTree算法的优势，因此通常可以将生成的TrieTree保持住，可以使用服务化或是将TrieTree结构进行序列化来避免每次重新生成。

3. 服务化

对于此类功能单一的业务逻辑，可以将其作为一种服务单独进行维护，其好处是服务可以在不同的业务之间进行共享。最简单的服务化是将其作为一个HTTP服务，这里使用PHP的swoole扩展进行实现，测试证明其能够提供较好的性能

<?php
$tree = new TrieTree();
$tree->init($argv[1]);

$http = new swoole_http_server("0.0.0.0", 9501);
$http->on('request', function ($request, $response) use($tree) {
    $args = $request->get;
    $match = $tree->match($args['c']);
    $response->end(json_encode($match));
});
$http->start();

使用时将待匹配的文本通过URL参数c进行传递，如果文本较长则可以使用POST来实现。

curl "http://127.0.0.1:9501/?c=%E4%BD%9C%E5%BC%8A%E5%99%A8" -v

HTTP/1.1 200 OK
Server: swoole-http-server
Content-Type: text/html
Connection: keep-alive
Date: Sat, 21 May 2016 05:45:57 GMT
Content-Length: 32

{"w":"\u4f5c\u5f0a\u5668","p":0}

对1000左右数量的关键词进行压力测试，发现性能还是不错的

Server Software:        swoole-http-server
Server Hostname:        127.0.0.1
Server Port:            9501

Document Path:          /?c=%E4%BD%9C%E5%BC%8A%E5%99%A8
Document Length:        32 bytes

Concurrency Level:      20
Time taken for tests:   11.601 seconds
Complete requests:      100000
Failed requests:        0
Total transferred:      18000000 bytes
HTML transferred:       3200000 bytes
Requests per second:    8619.72 [#/sec] (mean)
Time per request:       2.320 [ms] (mean)
Time per request:       0.116 [ms] (mean, across all concurrent requests)
Transfer rate:          1515.18 [Kbytes/sec] received