2

假设我们1e10每天大约有几行日志文件，每行包含：一个 ID 号（长度小于 15 位的整数）、一个登录时间和一个注销时间。某些 ID 可能会多次登录和注销。

问题一：

如何统计已登录的ID总数？（每个ID不要统计两次或更多）

我在这里尝试使用哈希表，但我发现我们应该获得的内存可能很大。

问题 2：

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

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

4

5 回答 5

6

您可以在 *nix shell 中执行此操作。

  1. cut -f1 logname.log | sort | uniq | wc -l
  2. cut -f2 logname.log | sort | uniq -c | sort -r
于 2013-04-14T06:48:25.870 回答
1

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

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

Gnu sort，会很乐意对大于内存的文件进行排序。以下是每件作品的作用：

  • awk正在提取第一个以空格分隔的列（ID 号）。
  • sort正在对这些 ID 号进行排序，因为uniq需要排序的输入。
  • uniq只返回 uniq 数字。
  • wc打印行数，这将是 uniq 数字的数量。
于 2013-04-14T06:49:42.967 回答
1

要使问题 2 有意义：您可能必须记录两件事：用户登录和用户注销。两个不同的活动以及用户 ID。如果此列表按活动的时间排序（登录或注销完成）。您只需使用名为 currentusers 的计数器进行扫描：每次登录时添加 1，每次注销时添加 -1。数量（当前用户）达到的最大值是您感兴趣的值，您可能还会对跟踪它发生的时间感兴趣。

于 2013-04-14T07:00:57.193 回答
0

  1. 使用分段树来存储连续 id 的间隔。扫描所有登录事件的日志。要插入 id，首先搜索包含该 id 的段：如果存在，则该 id 是重复的。如果它不搜索 id 之后或之前的段。如果它们存在，则删除它们并根据需要合并新的 id，然后插入新的段。如果它们不存在，则将 id 作为 1 个元素的段插入。

    插入所有 id 后，通过对树中所有段的基数求和来计算它们的数量。

  2. 假如说：

    • 给定的 id 在任何给定时间只能登录一次，
    • 事件按时间顺序存储（通常是日志）

    扫描日志并保留c当前登录用户数的计数器，以及m 找到的最大用户数和相关时间t。对于每次登录，递增c，对于每次注销，递减它。在每一步更新m，t如果m低于c.

于 2013-04-14T08:30:19.500 回答
0

对于 1，您可以尝试一次使用小到足以放入内存的文件片段。即代替

countUnique([1, 2, ... 1000000])

尝试

countUnique([1, 2, ... 1000]) + 
countUnique([1001, 1002, ... 2000]) + 
countUnique([2001, 2002, ...]) + ... + countUnique([999000, 999001, ... 1000000])

2有点棘手。将工作划分为可管理的间隔（如您所建议的那样）是一个好主意。对于每一秒，使用以下检查（伪代码）查找在 taht 秒内登录的人数：

def loggedIn(loginTime, logoutTime, currentTimeInterval):
    return user is logged in during currentTimeInterval

将loginIn应用于所有86400秒，然后最大化86400用户计数列表，找到在线用户数量最大的时间。

于 2013-04-14T06:48:57.433 回答