Session重叠问题学习(七)--小花狸合并算法和最后一次优化

2024-04-02 19:55

短信预约 -IT技能 免费直播动态提醒

接前文
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合并算法。

假如用户间首尾时间段没有重复的情况下,满足如下的规律
Session重叠问题学习(七)--小花狸合并算法和最后一次优化

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

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

insert into t2 (roomid,s,e)
select roomid,
s+interval startnum/1000000 second s,
e-interval endnum/1000000 second e
from (
select
roomid,
s,e,
startnum,
when @eflag=eflag then @rn:=@rn+1 when @eflag:=eflag then @rn else @rn end endnum
from (
select * from (
select when @sflag=sflag then @rn:=@rn+1 when @sflag:=sflag then @rn else @rn end startnum,roomid,s,e,sflag,eflag from
(
select * from
(
select t1.*,concat('[',roomid,'],',s) sflag,concat('[',roomid,'],',e) eflag from t1 order by roomid ,sflag
)a,(select @sflag:='',@rn:=0,@eflag:='') vars
) b
) bb order by roomid,eflag
) c
) d ;

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

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

小花狸Session合并的通用情况其实是下图所示
Session重叠问题学习(七)--小花狸合并算法和最后一次优化

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

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

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

改进的过程如下:

DELIMITER $$
CREATE DEFINER=`root`@`localhost` PROCEDURE `p`()
BEGIN
drop table if exists t1;
drop table if exists t2;
drop table if exists tmp_time_point;
drop table if exists tmp_min_range;
drop table if exists tmp_s;
CREATE temporary TABLE `t1` (
`roomid` int(11) NOT NULL DEFAULT '0',
`userid` bigint(20) NOT NULL DEFAULT '0',
`s` timestamp,
`e` timestamp,
primary key(roomid,userid,s,e)
) ENGINE=memory;
CREATE temporary TABLE `t2` (
`roomid` int(11) NOT NULL DEFAULT '0',
`timepoint` timestamp,
c int,
key(roomid,timepoint)
) ENGINE=memory;
CREATE temporary TABLE `tmp_min_range` (
`roomid` int(11) NOT NULL DEFAULT '0',
`s` timestamp,
`e` timestamp,
primary key(roomid,s,e),
key(roomid,e)
) ENGINE=memory;
create temporary table tmp_time_point(
roomid bigint,
timepoint timestamp,
type smallint,
key(roomid,timepoint)
) engine=memory;
create temporary table tmp_s(
roomid bigint,
userid bigint,
s timestamp,
e timestamp,
i int
) engine=memory;
SET @A=0;
SET @B=0;
insert into tmp_s
SELECT x.roomid,x.userid,s,e,datediff(e,s)+1 i
FROM
(
(
SELECT @B:=@B+1 AS id,roomid,userid,s
FROM (
SELECT DISTINCT roomid, userid, roomstart AS s
FROM u_room_log a
WHERE NOT EXISTS (SELECT *
FROM u_room_log b
WHERE a.roomid = b.roomid
AND a.userid = b.userid
AND a.roomstart > b.roomstart
AND a.roomstart <= b.roomend)
) AS p
) AS x,
(
SELECT @A:=@A+1 AS id,roomid,userid,e
FROM
(
SELECT DISTINCT roomid, userid, roomend AS e
FROM u_room_log a
WHERE NOT EXISTS (SELECT *
FROM u_room_log b
WHERE a.roomid = b.roomid
AND a.userid = b.userid
AND a.roomend >= b.roomstart
AND a.roomend < b.roomend)
) AS o
) AS y
)
WHERE x.id = y.id AND x.roomid = y.roomid AND x.userid = y.userid ;
select max(i) into @c from tmp_s;
insert ignore into t1(roomid,userid,s,e)
select
roomid, userid,
if(date(s)!=date(e) and id>1,date(s+interval id-1 date(s+interval id-1 date(e) ,e,date_format(s+interval id-1 '%Y-%m-%d 23:59:59')) e
from tmp_s t1 STRAIGHT_JOIN
nums on(nums.id<=t1.i)
where nums.id<=@c
;
-- 开始点+1,结束点-1
insert into tmp_time_point(roomid,timepoint,type) select roomid,s,1 from t1;
insert into tmp_time_point(roomid,timepoint,type) select roomid,e,-1 from t1;
-- 计算每个点的标号
insert into t2(roomid,timepoint,c)
select roomid,timepoint,from tmp_time_point group by roomid,timepoint;
-- 计算最小范围
insert ignore into tmp_min_range(roomid,s,e)
select roomid,starttime starttime, endtime endtime from (
select
if(@roomid=roomid,@d,'') as starttime,@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') endtime
from tmp_time_point p,(select @d:='',@roomid:=-1) vars
order by roomid,timepoint
) v4 where starttime!='' and date(starttime)=date(endtime);
select roomid,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) c from
(
select a.roomid,num,a.s,a.e from (
select when @roomid=roomid and date(@timepoint)=date(timepoint) then @num:=@num+prevC when @roomid:=roomid then @num:=0 end num,@timepoint:=timepoint ,a.* from (
select when @roomid=roomid then @prevC when @roomid:=roomid then @prevC:=0 end prevC,@prevC:=c,b.* from (
select * from t2 ,(select @roomid:=-1,@timepoint:='',@num:=0,@prevC:=-1) vars
) b order by roomid,timepoint
) a order by roomid,timepoint
) c
inner join
tmp_min_range a on( c.timepoint=a.e and c.roomid=a.roomid)
where num>=2
) d group by roomid,date(s);
END

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

总计时长983毫秒.

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

免责声明：

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的，并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据，供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

阅读原文内容投诉