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

螃短信营业厅指令匹配算法初探螀作者:李文强肆摘要:短信营业厅指令的匹配直接影响到短信营业厅的整体性能,为了能达到快速高效的匹配用户的指令,需要对短信营业厅指令按照用户使用量支持动态优先级指令排序。肂关键字:短信营业厅;指令集;哈希算法;优先级排序薀引言罿随着手机用户数据的增加和科技的发展,使用短信营业厅受理业务的用户也越来越多,短信营业厅处理的数据量也急剧增加。对短信营业厅的性能要求也越来越高。而短信匹配是短信营业厅的一个关键性的环节,匹配短信的效率直接的影响着短信营业厅的整体性能。因此,对于优化短信营业厅的指令集也势在必行。蒅内存数据结构袂指令结构体蚂指令结构体是存放短信营业厅配置在表里的短信指令和对应的服务和数据。肇structsms_order_struct袅{薃stringstrSms;//短信指令,key蚃structsms_order*p_data;//短信指令对应的服务组件以及配置数据(使用者自行设计)莀structsms_order_struct*p_next;//hashtable指向下一个指令结构体芄structsms_order_struct*p_next_used;//用户指令使用动态排序芃};蒀其中,strSms数据库中配置的短信指令。*p_data是短信指令对应的数据结构(使用者根据业务自己定义)。*p_next指针用于把指令结构体挂载到哈希数组中,形成单向链表。*p_next_used指针用来排序最近使用的指令结构。初始化时,指针应都为NULL。薈哈希数组羈哈希数组为指针数组,指向短信指令集结构体。用户挂载所有的配置指令。肄#defineHASH_COUNT7//hash数组的大小薂structsms_order_struct*hash_table[HASH_COUNT];//哈希数组袀#define_hashfn(strSms)//哈希函数蒇HASH_COUNT哈希数组的大小定义成常量,使用者可根据短信营业厅的指令的数量级进行调整。*hash_table用来存储和挂载短信指令结构体。_hashfn哈希函数,根据指令计算对应的指令结构体应该挂载到哈希数组的那个数组下。哈希函数的算法由使用者自己定义,原则上应该能保证所有指令集挂载完毕后,每个哈希数组上挂载的指令集基本相等。目前,我设计的哈希函数的算法是根据短信指令的字母转换为大写取ASCII码的平均值,然后对HASH_COUNT取余。该方法可能不是最优的,但是至少可以保证每个哈希数组上挂载的指令结构体数组基本相等。螄最常使用指令链表荿最常使用指令链表结构,是用来维护和查找最常使用的指令。罿structsms_used_struct袆{薄intilock;//更新锁,0-没有更新锁定。1-更新锁定莁structsms_order_struct*p_next_used;//最常使用指令链表头指针膇intinum;//最常使用指令链表长度(默认为10,可以通过配置文件更改)该值也可以定义为常量,从该结构体抽离出去。芆};芅ilock更新队列锁。读取该队列时不需要获得该锁,只有更新该队列才必须获得该锁。*p_next_used该指针指向最常使用指令队列的第一个指令结构体,即指向最常使用的队列。每次需要更新该队列是,总更新队列的头部。每次匹配指令时从该指针指向的指令结构体开始匹配。inum最常使用指令链表长度,该值默认为10,可以通过配置文件进行修改,修改的大小可以根据短信营业厅指令集指令数量来定。蒂哈希数组指示结构体葿该结构体是为了动态更新指令集而设计的。蚅sturcthashTable_head肅{艿intilock;//更新锁(0-没有更新锁定,1-更新锁定)薈void*plockList;//等待队列膄intiuserNum;//正在使用指令集线程数量(初始化为0)螅};莁ilock更新锁用来动态更新哈希数组上挂载的所有指令集来使用。线程获取文件锁夺取配置文件上更新标识,如果需要动态更新,则必须获得该锁并且锁定。*plockList等待锁的线程队列。iuserNum正在遍历该哈希数组的线程数量。羀内存指令集预览袈节该内存预览图为定义的哈希数组长度为4,即:hash_table[3]。该内存指令集共有16个指令结构体。其中最常使用指令链表维护长度为4。莂内存中哈希数组上挂载的指令集不会因为指令使用重新排列,只有在内存指令加载时,加载一次。加载时,指令也不会排序。根据读取数据库配置的指令先后,计划哈希值后,挂载对应的哈希数组项上。最常使用单链表会根据用户使用动态更新。聿指令集挂载芇指令集初始化羂读取数据库中的配置指令数据集。根据配置的指令关键值,调用哈希函数,计算哈希值。根据计算结果找到哈希数组中的数组项,遍历该项链表,挂载到链表结尾。新挂载的结构体的所