溫馨提示×

溫馨提示×

您好，登錄后才能下訂單哦！

密碼登錄×
登錄注冊×
其他方式登錄
點擊 登錄注冊 即表示同意《億速云用戶服務(wù)條款》

Session重疊問題學(xué)習(xí)(七)--小花貍合并算法和最后一次優(yōu)化

發(fā)布時間：2020-08-13 19:33:53 來源：ITPUB博客 閱讀：183 作者：壹頁書 欄目：MySQL數(shù)據(jù)庫
接前文
Session重疊問題學(xué)習(xí)(二)，這是問題和需求的描述，執(zhí)行時間90秒
http://blog.itpub.net/29254281/viewspace-2150229/

Session重疊問題學(xué)習(xí)(三)--優(yōu)化，一次優(yōu)化后,執(zhí)行時間25秒
http://blog.itpub.net/29254281/viewspace-2150259/

Session重疊問題學(xué)習(xí)(四)--再優(yōu)化，二次優(yōu)化后,執(zhí)行時間10秒
http://blog.itpub.net/29254281/viewspace-2150297/

Session重疊問題學(xué)習(xí)(五)--最優(yōu)化，三次優(yōu)化后,執(zhí)行時間1.6秒
http://blog.itpub.net/29254281/viewspace-2150339/

Session重疊問題學(xué)習(xí)(六)--極致優(yōu)化，四次優(yōu)化后,執(zhí)行時間1250-1300毫秒
http://blog.itpub.net/29254281/viewspace-2150364/


這是對這個問題的算法總結(jié)和最后一次優(yōu)化.
經(jīng)過這次優(yōu)化,在我的電腦上(SSD硬盤,機械硬盤還是沒有這么快),運行時間是980毫秒左右.真正意義上的秒出.并且我確實覺得是優(yōu)無可優(yōu)了。

之所以能從10秒的版本,跳躍優(yōu)化到1.6s,1.3s的版本.是因為采用了小花貍Session合并算法。

假如用戶間首尾時間段沒有重復(fù)的情況下,滿足如下的規(guī)律
Session重疊問題學(xué)習(xí)(七)--小花貍合并算法和最后一次優(yōu)化

但是該規(guī)律僅僅存在于用戶首尾時間段不重合的情況.
比如A用戶上線時間是 10點至11點整,而用戶B上線時間是11點整到12點.
因為11點整這個時刻,用戶A和B重合了,所以這個算法就不能生效了.

所以當(dāng)時取巧,如果重合了,就增加或者減去一個很小的時間
s+interval startnum/1000000 second s,      
e-interval endnum/1000000 second e

  1. insert into t2 (roomid,s,e)      
  2. select roomid,      
  3. s+interval startnum/1000000 second s,      
  4. e-interval endnum/1000000 second e      
  5.  from (      
  6.     select       
  7.     roomid,      
  8.     s,e,      
  9.     startnum,      
  10.     when @eflag=eflag then @rn:=@rn+1 when @eflag:=eflag then @rn else @rn end endnum      
  11.     from (      
  12.         select * from (      
  13.             select when @sflag=sflag then @rn:=@rn+1 when @sflag:=sflag then @rn else @rn end startnum,roomid,s,e,sflag,eflag from      
  14.             (      
  15.                 select * from       
  16.                 (      
  17.                     select t1.*,concat('[',roomid,'],',s) sflag,concat('[',roomid,'],',e) eflag from t1 order by roomid ,sflag      
  18.                 )a,(select @sflag:='',@rn:=0,@eflag:='') vars      
  19.             ) b        
  20.         ) bb order by roomid,eflag      
  21.     ) c      
  22. ) d ;  

但是這樣引入一個問題,就是有誤差.誤差只能縮小卻不能消除.
這也是為什么1.3s和1.6s版本使用timestamp(6)的原因,就是為了縮小誤差.

但是經(jīng)過反復(fù)的思考,之前發(fā)現(xiàn)的規(guī)律其實是一個特例.

小花貍Session合并的通用情況其實是下圖所示
Session重疊問題學(xué)習(xí)(七)--小花貍合并算法和最后一次優(yōu)化

先給每個點標號. 
每個點,如果是開始點則+1,結(jié)束點則-1.
以圖中左側(cè)第二點為例,該點是四個點的重合,其中有一個結(jié)束點（-1）三個開始點（+3）,所以該點標號是2.

然后從左到右計算,
最左點是0加上該點標號,作為右側(cè)點的最大在線人數(shù).
其他點的最大在線人數(shù) 都是左側(cè)點的最大在線人數(shù)加上標號.

最后查詢最大在線人數(shù)大于等于2的時間段,匯總即可。

改進的過程如下:

  1. DELIMITER $$  
  2.   
  3. CREATE DEFINER=`root`@`localhost` PROCEDURE `p`()  
  4. BEGIN        
  5.     drop table if exists t1;        
  6.     drop table if exists t2;      
  7.     drop table if exists tmp_time_point;        
  8.     drop table if exists tmp_min_range;      
  9.     drop table if exists tmp_s;    
  10.     CREATE temporary TABLE `t1` (        
  11.       `roomid` int(11) NOT NULL DEFAULT '0',        
  12.       `userid` bigint(20) NOT NULL DEFAULT '0',        
  13.       `s` timestamp,        
  14.       `e` timestamp,    
  15.        primary key(roomid,userid,s,e)    
  16.     ) ENGINE=memory;        
  17.       
  18.    CREATE temporary TABLE `t2` (        
  19.       `roomid` int(11) NOT NULL DEFAULT '0',        
  20.       `timepoint` timestamp,        
  21.         c int,  
  22.         key(roomid,timepoint)  
  23.     ) ENGINE=memory;        
  24.       
  25.     CREATE temporary TABLE `tmp_min_range` (        
  26.       `roomid` int(11) NOT NULL DEFAULT '0',        
  27.       `s` timestamp,        
  28.       `e` timestamp,        
  29.       primary key(roomid,s,e),    
  30.       key(roomid,e)    
  31.     ) ENGINE=memory;        
  32.       
  33.     create temporary table tmp_time_point(        
  34.             roomid bigint,        
  35.             timepoint timestamp,        
  36.             type smallint,      
  37.             key(roomid,timepoint)        
  38.     ) engine=memory;        
  39.         
  40.     create temporary table tmp_s(    
  41.         roomid bigint,    
  42.         userid bigint,    
  43.         s timestamp,    
  44.         e timestamp,    
  45.         i int    
  46.     ) engine=memory;    
  47.         
  48. SET @A=0;        
  49. SET @B=0;        
  50.     
  51. insert into tmp_s    
  52.     SELECT x.roomid,x.userid,s,e,datediff(e,s)+1 i     
  53.     FROM       
  54.     (      
  55.         (      
  56.             SELECT @B:=@B+1 AS id,roomid,userid,s        
  57.             FROM (        
  58.                 SELECT DISTINCT roomid, userid, roomstart AS s            
  59.                 FROM u_room_log a            
  60.                 WHERE NOT EXISTS (SELECT *            
  61.                     FROM u_room_log b            
  62.                     WHERE a.roomid = b.roomid            
  63.                         AND a.userid = b.userid            
  64.                         AND a.roomstart > b.roomstart            
  65.                         AND a.roomstart <= b.roomend)      
  66.             ) AS p      
  67.         ) AS x,        
  68.         (      
  69.             SELECT @A:=@A+1 AS id,roomid,userid,e        
  70.             FROM       
  71.             (        
  72.                 SELECT DISTINCT roomid, userid, roomend AS e            
  73.                 FROM u_room_log a            
  74.                 WHERE NOT EXISTS (SELECT *            
  75.                     FROM u_room_log b            
  76.                     WHERE a.roomid = b.roomid            
  77.                         AND a.userid = b.userid            
  78.                         AND a.roomend >= b.roomstart            
  79.                         AND a.roomend < b.roomend)        
  80.             ) AS o      
  81.         ) AS y        
  82.     )       
  83.     WHERE x.id = y.id AND x.roomid = y.roomid AND x.userid = y.userid   ;       
  84.     
  85. select max(i) into @c from tmp_s;    
  86.         
  87. insert ignore into t1(roomid,userid,s,e)      
  88. select           
  89. roomid,  userid,          
  90. 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          
  91. from tmp_s t1 STRAIGHT_JOIN        
  92. nums on(nums.id<=t1.i)    
  93. where nums.id<=@c    
  94.        
  95. ;          
  96.       
  97.     -- 開始點+1,結(jié)束點-1  
  98.     insert into tmp_time_point(roomid,timepoint,type) select roomid,s,1 from t1;      
  99.     insert into tmp_time_point(roomid,timepoint,type) select roomid,e,-1 from t1;   
  100.   
  101.     -- 計算每個點的標號  
  102.     insert into t2(roomid,timepoint,c)   
  103.     select roomid,timepoint,from tmp_time_point group by  roomid,timepoint;  
  104.   
  105.     -- 計算最小范圍  
  106.     insert ignore into tmp_min_range(roomid,s,e)      
  107.                 select   roomid,starttime  starttime, endtime  endtime from (        
  108.                     select         
  109.                     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        
  110.                     from tmp_time_point p,(select @d:='',@roomid:=-1) vars        
  111.                     order by roomid,timepoint        
  112.                 ) v4 where starttime!='' and date(starttime)=date(endtime);      
  113.          
  114.   
  115.     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   
  116.     (  
  117.         select a.roomid,num,a.s,a.e from (  
  118.             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 (  
  119.                 select when @roomid=roomid then @prevC  when @roomid:=roomid then @prevC:=0 end prevC,@prevC:=c,b.* from (  
  120.                     select * from t2 ,(select @roomid:=-1,@timepoint:='',@num:=0,@prevC:=-1) vars  
  121.                 ) b order by roomid,timepoint  
  122.             ) a order by roomid,timepoint  
  123.         ) c   
  124.         inner join       
  125.                 tmp_min_range a on( c.timepoint=a.e and c.roomid=a.roomid)    
  126.         where num>=2  
  127.     ) d  group by roomid,date(s);       
  128.       
  129. END  

耗時分析：
填充tmp_s，合并同一房間同一用戶的重疊部分，耗時639毫秒
填充t1，拆分跨天的用戶數(shù)據(jù)，耗時62毫秒
填充tmp_time_point,寫入開始節(jié)點和結(jié)束節(jié)點的信息和權(quán)重,耗時忽略不計
填充t2,計算每個點的標號.耗時78毫秒
填充tmp_min_range,計算最小間隔范圍，耗時125毫秒
小花貍合并算法并展示,耗時266毫秒.

總計時長983毫秒.

好了,這個問題不能再玩了..over,over
向AI問一下細節(jié)

免責(zé)聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點不代表本網(wǎng)站立場，如果涉及侵權(quán)請聯(lián)系站長郵箱：is@yisu.com進行舉報，并提供相關(guān)證據(jù)，一經(jīng)查實，將立刻刪除涉嫌侵權(quán)內(nèi)容。

AI
助
手