假设我们每天有大约 1e10
行日志文件,每行包含:ID 号(长度小于 15 位的整数(、登录时间和注销时间。某些 ID 可能会多次登录和注销。
问题1:
如何统计已登录的ID总数?(我们不应该计算每个ID两次或更多(
我试图在这里使用哈希表,但我发现我们应该获得的内存可能太大了。
问题2:
计算在线用户人口最多的时间。
我认为我们可以将一天中的时间分成 86400 秒,然后对于日志文件的每一行,在在线间隔中每秒增加 1。或者,也许我可以按登录时间对日志文件进行排序?
你可以在 *nix shell 中做到这一点。
-
cut -f1 logname.log | sort | uniq | wc -l
-
cut -f2 logname.log | sort | uniq -c | sort -r
为了使问题 2 有意义:您可能必须记录 2 件事:用户登录和用户注销。两个不同的活动以及用户 ID。如果此列表按活动(登录或注销完成(的时间排序。您只需使用名为currentusers的计数器进行扫描:每次登录添加1,每次注销添加-1。该数量(当前用户(达到的最大值是您感兴趣的值,您可能还对跟踪它发生的时间感兴趣。
对于问题 1,忘记C++并使用 *nix 工具。 假设日志文件以空格分隔,则给定日志中的唯一登录名数由下式计算:
$ awk '{print $1}' foo.log | sort | uniq | wc -l
Gnu排序,将愉快地排序大于内存的文件。 以下是每件作品正在做的事情:
- awk 正在提取第一个以空格分隔的列(ID 号(。
- sort正在对这些ID号进行排序,因为Uniq需要排序输入。
- UNIQ 仅返回 UNIQ 编号。
- WC 打印行数,这将是 UNIQ 编号的数量。
-
使用段树存储连续 ID 的间隔。扫描日志以查找所有登录事件。要插入 id,请首先搜索包含 id 的段:如果存在,则 id 是重复的。如果它不搜索 id 之后或之前的段。如果存在,请根据需要删除它们并合并新 ID,然后插入新段。如果它们不存在,请将 id 作为 1 个元素的段插入。
插入所有 id 后,通过对树中所有段的基数求和来计算它们的数量。
-
假设:
- 给定的 ID 在任何给定时间只能登录一次,
- 事件按时间顺序存储(这是日志通常的样子(
扫描日志并保留当前登录用户数的计数器
c
,以及找到的最大m
数以及关联的时间t
。对于每个登录,递增c
,对于每个注销,递减它。在每一步更新m
并t
m
是否低于c
。
对于 1,您可以尝试一次处理足够小以适合内存的文件片段。即代替
countUnique([1, 2, ... 1000000])
尝试
countUnique([1, 2, ... 1000]) +
countUnique([1001, 1002, ... 2000]) +
countUnique([2001, 2002, ...]) + ... + countUnique([999000, 999001, ... 1000000])
2 有点棘手。将工作划分为可管理的间隔(如您所建议的一秒(是一个好主意。对于每一秒,使用以下检查(伪代码(查找该秒内登录的人数:
def loggedIn(loginTime, logoutTime, currentTimeInterval):
return user is logged in during currentTimeInterval
将 loggedIn 应用于所有 86400 秒,然后最大化 86400 个用户计数的列表,以查找在线用户群体最大的时间。