Neo's Blog

不抽象就无法深入思考
不还原就看不到本来面目!

0%

常见系统设计题系列-在线人数统计

问题:
求一个论坛的在线人数,假设有一个论坛,其注册ID有两亿个,每个ID从登陆到退出会向一个日志文件中记下登陆时间和退出时间,要求写一个算法统计一天中论坛的用户在线分布,取样粒度为秒。
回答:

方法1:
将所有的事件(包括每个ID的登陆,退出) 按照时间排序;
如果登陆则+1, 登出则-1

方法2:
如果无序怎么办?需要先把所有的事件从磁盘读出来,然后把结果记录下来。

一天总共有3600*24=86400秒。

定义一个长度为86400的整数数组intdelta[86400],每个整数对应这一秒的人数变化值,可能为正也可能为负。开始时将数组元素都初始化为0。

然后依次读入每个用户的登录时间和退出时间,将与登录时间对应的整数值加1,将与退出时间对应的整数值减1。

这样处理一遍后数组中存储了每秒中的人数变化情况。

定义另外一个长度为86400的整数数组intonline_num[86400],每个整数对应这一秒的论坛在线人数。

假设一天开始时论坛在线人数为0,则第1秒的人数online_num[0]=delta[0]。第n+1秒的人数online_num[n]=online_num[n-1]+delta[n]。

这样我们就获得了一天中任意时间的在线人数。

你的支持是我坚持的最大动力!