短信营业厅指令匹配算法初探.docx

短信营业厅指令匹配算法初探作者：李文强摘要：短信营业厅指令的匹配直接影响到短信营业厅的整体性能，为了能达到快速高效的匹配用户的指令，需要对短信营业厅指令按照用户使用量支持动态优先级指令排序。关键字：短信营业厅；指令集；哈希算法；优先级排序引言随着手机用户数据的增加和科技的发展，使用短信营业厅受理业务的用户也越来越多，短信营业厅处理的数据量也急剧增加。对短信营业厅的性能要求也越来越高。而短信匹配是短信营业厅的一个关键性的环节，匹配短信的效率直接的影响着短信营业厅的整体性能。因此，对于优化短信营业厅的指令集也势在必行。内存数据结构指令结构体指令结构体是存放短信营业厅配置在表里的短信指令和对应的服务和数据。struct sms_order_struct { string strSms; //短信指令，key struct sms_order *p_data; //短信指令对应的服务组件以及配置数据（使用者自行设计） struct sms_order_struct *p_next; //hash table 指向下一个指令结构体 struct sms_order_struct *p_next_used; //用户指令使用动态排序};其中，strSms数据库中配置的短信指令。*p_data是短信指令对应的数据结构（使用者根据业务自己定义）。*p_next指针用于把指令结构体挂载到哈希数组中，形成单向链表。*p_next_used指针用来排序最近使用的指令结构。初始化时，指针应都为NULL。哈希数组哈希数组为指针数组，指向短信指令集结构体。用户挂载所有的配置指令。#define HASH_COUNT 7 //hash数组的大小struct sms_order_struct *hash_table[HASH_COUNT]; //哈希数组#define _hashfn(strSms) //哈希函数HASH_COUNT哈希数组的大小定义成常量，使用者可根据短信营业厅的指令的数量级进行调整。*hash_table用来存储和挂载短信指令结构体。_hashfn哈希函数，根据指令计算对应的指令结构体应该挂载到哈希数组的那个数组下。哈希函数的算法由使用者自己定义，原则上应该能保证所有指令集挂载完毕后，每个哈希数组上挂载的指令集基本相等。目前，我设计的哈希函数的算法是根据短信指令的字母转换为大写取ASCII码的平均值，然后对HASH_COUNT取余。该方法可能不是最优的，但是至少可以保证每个哈希数组上挂载的指令结构体数组基本相等。最常使用指令链表最常使用指令链表结构，是用来维护和查找最常使用的指令。struct sms_used_struct { int ilock; //更新锁，0-没有更新锁定。1-更新锁定 struct sms_order_struct *p_next_used; //最常使用指令链表头指针 int inum; //最常使用指令链表长度（默认为10，可以通过配置文件更改）该值也可以定义为常量，从该结构体抽离出去。};ilock更新队列锁。读取该队列时不需要获得该锁，只有更新该队列才必须获得该锁。*p_next_used该指针指向最常使用指令队列的第一个指令结构体，即指向最常使用的队列。每次需要更新该队列是，总更新队列的头部。每次匹配指令时从该指针指向的指令结构体开始匹配。inum最常使用指令链表长度，该值默认为10，可以通过配置文件进行修改，修改的大小可以根据短信营业厅指令集指令数量来定。哈希数组指示结构体该结构体是为了动态更新指令集而设计的。sturct hashTable_head { int ilock; //更新锁（0-没有更新锁定，1-更新锁定） void *plockList; //等待队列 int iuserNum; //正在使用指令集线程数量（初始化为0）};ilock更新锁用来动态更新哈希数组上挂载的所有指令集来使用。线程获取文件锁夺取配置文件上更新标识，如果需要动态更新，则必须获得该锁并且锁定。*plockList等待锁的线程队列。iuserNum正在遍历该哈希数组的线程数量。内存指令集预览该内存预览图为定义的哈希数组长度为4，即：hash_table[3]。该内存指令集共有16个指令结构体。其中最常使用指令链表维护长度为4。内存中哈希数组上挂载的指令集不会因为指令使用重新排列，只有在内存指令加载时，加载一次。加载时，指令也不会排序。根据读取数据库配置的指令先后，计划哈希值后，挂载对应的哈希数组项上。最常使用单链表会根据用户使用动态更新。指令集挂载指令集初始化读取数据库中的配置指令数据集。根据配置