算法问题 : determining "user sessions"

Question

我有一个非常有趣的(至少对我而言)问题要解决(而且，不，这不是家庭作业)。它等同于:您需要确定用户在他的计算机前进行的“ session ”和“ session 开始和结束时间”。

您将获得进行任何用户交互的时间和最长不活动时间。如果两个用户输入之间耗时大于或等于不活动时间，则它们是不同 session 的一部分。

基本上我得到的输入是这样的(输入没有排序，我宁愿在确定 session 之前不对它们进行排序):

06:38
07:12
06:17
09:00
06:49
07:37
08:45
09:51
08:29

然后，比如说，有 30 分钟的不活动时间。

然后我需要找到三个 session :

[06:17...07:12]
[07:37...09:00]
[09:51...09:51]

如果不活动时间设置为 12 小时，那么我只会找到一个大 session :

[06:17...09:51]

我怎样才能简单地解决这个问题？

有一个最短的不活动有效时间，大约为 15 分钟。

我宁愿不预先排序的原因是我会得到很多数据并且只将它们存储在内存中是有问题的。但是，这些数据中的大部分应该是相同 session 的一部分(与数据量相比， session 应该相对较少，可能是几千比一 [每个 session 数千个用户输入])。

到目前为止，我正在考虑读取输入(比如 06:38)并定义一个区间 [data-max_inactivity...data+max_inactivity]，并且对于每个新输入，使用二分法 (log n) 搜索以查看它是否落在已知区间内或创建新区间。

我会为每个输入重复这个，使解决方案 n log n AFAICT。此外，好处是它不会使用太多内存，因为它只会创建间隔(并且大多数输入将落在已知间隔内)。

此外，每次如果落在已知区间内，我都必须更改区间的下限或上限，然后查看是否需要与下一个区间“合并”。例如(最长不活动时间为 30 分钟):

[06:00...07:00]  (because I got 06:30)
[06:00...07:00][07:45...08:45]   (because I later got 08:15)
[06:00...08:45] (because I just received 07:20)

我不知道描述的是否很清楚，但这就是我需要做的。

这样的问题有名字吗？你会如何解决它？

编辑

如果我打算按我计划的方式解决它，我很想知道我应该使用哪种数据结构。我需要 log n 搜索和插入/合并能力。

Answer 1

最大延迟
如果日志条目有“最大延迟”(例如，最大延迟为 2 小时，8:12 的事件将永远不会在 10:12 的事件之后列出)，您可以向前看并排序。

进行排序
或者，我会先尝试排序——至少要确保它不起作用。时间戳可以合理地存储在 8 个字节中(即使出于您的目的，您也可以将 2.5 亿放入 1 GB 中)。快速排序可能不是这里的最佳选择，因为它的局部性较低，插入排序对于几乎已排序的数据几乎是完美的(尽管它的局部性也很差)，或者，按 block 快速排序，然后通过合并合并 block sort 应该可以，即使它会增加内存需求。

压扁并征服
或者，您可以使用以下策略:

1. 将每个事件转换为“持续时间为 0 的 session ”
2. 将您的 session 列表分成 block (例如 1K 值/ block )
3. 在每个 block 中，按 session 开始排序
4. 合并所有可以合并的 session (之前已经排序可以减少你的前瞻性)。
5. 将剩余 session 的列表压缩成一个大的单个列表
6. 重复第 2 步，直到列表不再变短。
7. 对所有内容进行排序和合并

如果您的日志文件具有您的问题所暗示的那种“时间局部性”，那么单次通过就应该减少数据以允许“完整”排序。

[编辑] [本站] 1演示了一个“优化后的插入排序完成的快速排序”，它在几乎排序的数据上非常好。就像这些人一样 std::sort