接前文
Session重叠问题学习(二)，这是问题和需求的描述，执行时间90秒
http://blog.itpub.net/29254281/viewspace-2150229/

Session重叠问题学习(三)--优化，一次优化后,执行时间25秒
http://blog.itpub.net/29254281/viewspace-2150259/

Session重叠问题学习(四)--再优化，二次优化后,执行时间10秒
http://blog.itpub.net/29254281/viewspace-2150297/

Session重叠问题学习(五)--最优化，三次优化后,执行时间1.6秒
http://blog.itpub.net/29254281/viewspace-2150339/

Session重叠问题学习(六)--极致优化，四次优化后,执行时间1250-1300毫秒
http://blog.itpub.net/29254281/viewspace-2150364/


这是对这个问题的算法总结和最后一次优化.
经过这次优化,在我的电脑上(SSD硬盘,机械硬盘还是没有这么快),运行时间是980毫秒左右.真正意义上的秒出.并且我确实觉得是优无可优了。

之所以能从10秒的版本,跳跃优化到1.6s,1.3s的版本.是因为采用了小花狸Session合并算法。

假如用户间首尾时间段没有重复的情况下,满足如下的规律


但是该规律仅仅存在于用户首尾时间段不重合的情况.
比如A用户上线时间是 10点至11点整,而用户B上线时间是11点整到12点.
因为11点整这个时刻,用户A和B重合了,所以这个算法就不能生效了.

所以当时取巧,如果重合了,就增加或者减去一个很小的时间
s+interval startnum/1000000 second s,
e-interval endnum/1000000 second e

insertintot2(roomid,s,e) selectroomid, s+intervalstartnum/1000000seconds, e-intervalendnum/1000000seconde from( select roomid, s,e, startnum, when@eflag=eflagthen@rn:=@rn+1when@eflag:=eflagthen@rnelse@rnendendnum from( select*from( selectwhen@sflag=sflagthen@rn:=@rn+1when@sflag:=sflagthen@rnelse@rnendstartnum,roomid,s,e,sflag,eflagfrom ( select*from ( selectt1.*,concat('[',roomid,'],',s)sflag,concat('[',roomid,'],',e)eflagfromt1orderbyroomid,sflag )a,(select@sflag:='',@rn:=0,@eflag:='')vars )b )bborderbyroomid,eflag )c )d;

但是这样引入一个问题,就是有误差.误差只能缩小却不能消除.
这也是为什么1.3s和1.6s版本使用timestamp(6)的原因,就是为了缩小误差.

但是经过反复的思考,之前发现的规律其实是一个特例.

小花狸Session合并的通用情况其实是下图所示


先给每个点标号.
每个点,如果是开始点则+1,结束点则-1.
以图中左侧第二点为例,该点是四个点的重合,其中有一个结束点（-1）三个开始点（+3）,所以该点标号是2.

然后从左到右计算,
最左点是0加上该点标号,作为右侧点的最大在线人数.
其他点的最大在线人数 都是左侧点的最大在线人数加上标号.

最后查询最大在线人数大于等于2的时间段,汇总即可。

改进的过程如下:

DELIMITER$$CREATEDEFINER=`root`@`localhost`PROCEDURE`p`()BEGINdroptableifexistst1;droptableifexistst2;droptableifexiststmp_time_point;droptableifexiststmp_min_range;droptableifexiststmp_s;CREATEtemporaryTABLE`t1`(`roomid`int(11)NOTNULLDEFAULT'0',`userid`bigint(20)NOTNULLDEFAULT'0',`s`timestamp,`e`timestamp,primarykey(roomid,userid,s,e))ENGINE=memory;CREATEtemporaryTABLE`t2`(`roomid`int(11)NOTNULLDEFAULT'0',`timepoint`timestamp,cint,key(roomid,timepoint))ENGINE=memory;CREATEtemporaryTABLE`tmp_min_range`(`roomid`int(11)NOTNULLDEFAULT'0',`s`timestamp,`e`timestamp,primarykey(roomid,s,e),key(roomid,e))ENGINE=memory;createtemporarytabletmp_time_point(roomidbigint,timepointtimestamp,typesmallint,key(roomid,timepoint))engine=memory;createtemporarytabletmp_s(roomidbigint,useridbigint,stimestamp,etimestamp,iint)engine=memory;SET@A=0;SET@B=0;insertintotmp_sSELECTx.roomid,x.userid,s,e,datediff(e,s)+1iFROM((SELECT@B:=@B+1ASid,roomid,userid,sFROM(SELECTDISTINCTroomid,userid,roomstartASsFROMu_room_logaWHERENOTEXISTS(SELECT*FROMu_room_logbWHEREa.roomid=b.roomidANDa.userid=b.useridANDa.roomstart>b.roomstartANDa.roomstart<=b.roomend))ASp)ASx,(SELECT@A:=@A+1ASid,roomid,userid,eFROM(SELECTDISTINCTroomid,userid,roomendASeFROMu_room_logaWHERENOTEXISTS(SELECT*FROMu_room_logbWHEREa.roomid=b.roomidANDa.userid=b.useridANDa.roomend>=b.roomstartANDa.roomend<b.roomend))ASo)ASy)WHEREx.id=y.idANDx.roomid=y.roomidANDx.userid=y.userid;selectmax(i)into@cfromtmp_s;insertignoreintot1(roomid,userid,s,e)selectroomid,userid,if(date(s)!=date(e)andid>1,date(s+intervalid-1date(s+intervalid-1date(e),e,date_format(s+intervalid-1'%Y-%m-%d23:59:59'))efromtmp_st1STRAIGHT_JOINnumson(nums.id<=t1.i)wherenums.id<=@c;--开始点+1,结束点-1insertintotmp_time_point(roomid,timepoint,type)selectroomid,s,1fromt1;insertintotmp_time_point(roomid,timepoint,type)selectroomid,e,-1fromt1;--计算每个点的标号insertintot2(roomid,timepoint,c)selectroomid,timepoint,fromtmp_time_pointgroupbyroomid,timepoint;--计算最小范围insertignoreintotmp_min_range(roomid,s,e)selectroomid,starttimestarttime,endtimeendtimefrom(selectif(@roomid=roomid,@d,'')asstarttime,@d:=str_to_date(timepoint,'%Y-%m-%d%H:%i:%s.%f'),@roomid:=roomid,p.roomid,str_to_date(timepoint,'%Y-%m-%d%H:%i:%s.%f')endtimefromtmp_time_pointp,(select@d:='',@roomid:=-1)varsorderbyroomid,timepoint)v4wherestarttime!=''anddate(starttime)=date(endtime);selectroomid,date(s)dt,round(second,date_format(s,'%Y-%m-%d%H:%i:%s'),date_format(e,'%Y-%m-%d%H:%i:%s')))/60)ts,max(num)cfrom(selecta.roomid,num,a.s,a.efrom(selectwhen@roomid=roomidanddate(@timepoint)=date(timepoint)then@num:=@num+prevCwhen@roomid:=roomidthen@num:=0endnum,@timepoint:=timepoint,a.*from(selectwhen@roomid=roomidthen@prevCwhen@roomid:=roomidthen@prevC:=0endprevC,@prevC:=c,b.*from(select*fromt2,(select@roomid:=-1,@timepoint:='',@num:=0,@prevC:=-1)vars)borderbyroomid,timepoint)aorderbyroomid,timepoint)cinnerjointmp_min_rangeaon(c.timepoint=a.eandc.roomid=a.roomid)wherenum>=2)dgroupbyroomid,date(s);END

耗时分析：
填充tmp_s，合并同一房间同一用户的重叠部分，耗时639毫秒
填充t1，拆分跨天的用户数据，耗时62毫秒
填充tmp_time_point,写入开始节点和结束节点的信息和权重,耗时忽略不计
填充t2,计算每个点的标号.耗时78毫秒
填充tmp_min_range,计算最小间隔范围，耗时125毫秒
小花狸合并算法并展示,耗时266毫秒.

总计时长983毫秒.

好了,这个问题不能再玩了..over,over