海量数据分析

Question

假设我们每天都有大约1e10行的日志文件，每一行都包含: ID号(小于15位数的整数)、登录时间和注销时间。一些ID可以登录和注销几次。

问题1

如何计算已登录的ID总数？(每个ID不应计数两次或更多)

我试图在这里使用一个哈希表，但我发现我们应该获得的内存可能太大了。

问题2

计算在线用户人数最多的时间。

我想我们可以把一天的时间分成86400秒，然后对每一行日志文件，在在线时间间隔内每秒钟增加1秒钟。或者我可以根据登录时间对日志文件进行排序？

Answer 1

1. 使用段树存储连续ids的间隔。扫描日志以查找所有登录事件。要插入一个id，首先搜索一个包含id的段:如果它存在，则该id是重复的。如果它不搜索位于id后面或之前的段。如果它们存在，则删除它们并根据需要合并新id，并插入新段。如果它们不存在，则将id作为1元素的段插入。 一旦插入了所有in，通过对树中所有段的基数之和来计数它们的数量。
2. 假设：

- a given id may be logged in only once at any given time,
- events are stored in chronological order (that's what logs are normally) 

扫描日志并保存当前登录用户数量的计数器c，以及找到的最大m数以及相关的时间t。对于每个登录，增量c，对于每次注销，它都会减少。在每个步骤中，如果m和t低于c，则更新m和c。

Answer 2

你可以用*nix外壳来做。

1. cut -f1 logname.log | sort | uniq | wc -l
2. cut -f2 logname.log | sort | uniq -c | sort -r

Answer 3

对于问题1，忘记C++并使用*nix工具。假设日志文件是分隔空间的，那么给定日志中的唯一登录数由以下方法计算：

$ awk '{print $1}' foo.log | sort | uniq | wc -l

Gnu排序，将高兴排序文件大于内存。以下是每一件作品所做的事情：

• awk正在提取第一个空格分隔的列( ID号)。
• 排序是对这些ID号进行排序，因为uniq需要排序输入。
• uniq只返回uniq数字。
• wc打印行数，这将是uniq数字的数目。