算法问题：确定“用户会话”

我有一个真正有趣的（至少对我来说）问题来解决（而且，不，它不是家庭作业）。这相当于这样：您需要确定用户在他的计算机前面的“会话”和“会话开始和结束时间”。算法问题：确定“用户会话”

您会得到任何用户交互的时间和最长不活动时间。如果时间大于或等于两个用户输入之间的非活动时间段，则它们是不同会话的一部分。

基本上输入我得到此（输入未经排序而我宁愿没有确定会议之前他们排序）：

，并说，经过一段时间的闲置30分钟。

然后我需要找到三节：

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

如果不活动的周期为12小时，然后我只希望找到一个大的会议：

[06:17...09:51]

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

有一个不活动的最小有效期限，大约15分钟。

我宁愿不事先排序的原因是我会得到一个lot的数据，只将它们存储在内存中是有问题的。然而，这些数据中的大部分应该是同一会话的一部分（与数据量相比，会话相对较少，可能大约为数千到1（每个会话的用户输入数千）]。

到目前为止，我想读一个输入（比如06:38），并定义区间[数据max_inactivity ...数据+ 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)

我不知道，如果描述非常清楚，但是这是我需要做的。

这样的问题是否有名字？你将如何去解决它？

编辑

我在知道，如果我打算解决这个问题，我计划的方式，我应该使用哪种类型的数据结构非常感兴趣。我需要日志n搜索和插入/合并能力。

来源

2010-08-02 NoozNooz42

你如何到达交互日期未被排序的情况？你不接受他们？ – 2010-08-02 11:36:04

我很想知道您的活动时间戳可能会在给定的用户会话中乱序出现。对于特定的用户，是否会实际报告13:00，14:00，13:30？ – sarnold 2010-08-02 11:38:13

他们“几乎按顺序”到达，但它仍然没有秩序：它不在我的控制之下。我正在解析包含输入的文本文件（我没有生成文本文件），它们由几个来源生成，并且绝对不会被排序。 – NoozNooz42 2010-08-02 11:42:12

您在询问在线算法，即可以为每个新输入时间递增计算一组新的会话的算法。

关于选择数据结构对于当前会话集，可以使用平衡二叉搜索树。每个会话由开始时间和结束时间的一对(start,end)表示。搜索树的节点按其start时间排序。由于您的会话间隔至少为max_inactivity，即没有两个会话重叠，这将确保end时间也是有序的。换句话说，按开始时间排序已经连续排列了会议。

这里有一些用于插入的伪代码。为了符号方便，我们假设sessions是一个数组，尽管它实际上是一个二叉搜索树。

insert(time,sessions) = do 
    i <- find index such that 
     sessions[i].start <= time && time < session[i+1].start 

    if (sessions[i].start + max_inactivity >= time) 
     merge time into session[i] 
    else if (time >= sessions[i+1].start - max_inactivity) 
     merge time into sessions[i+1] 
    else 
     insert (time,time) into sessions 

    if (session[i] and session[i+1] overlap) 
     merge session[i] and session[i+1]

的merge操作可以通过删除和插入元件成二进制搜索树来实现。

该算法将花费时间O（n log m），其中m是会话的最大数量，您认为这相当小。

当然，根据编程语言，实现平衡二叉搜索树并非易事。这里的关键是你必须按照键来分割树，而不是每个现成的库都支持这个操作。对于Java，我会使用TreeSet<E>类;如上所述，元素类型E是由开始和结束时间给出的单个会话。它的floor()和ceiling()方法将在我的伪代码中检索我用sessions[i]和sessions[i+1]表示的会话。

来源

2010-08-02 16:49:06

非常感谢您的回答。我不知道术语*“在线算法”*这非常有趣。我可能会在Java中实现这个问题的解决方案:) – NoozNooz42 2010-08-02 18:30:42

我已经浏览了Java API文档，您可能想要使用'TreeSet'类。编辑我的答案。 – 2010-08-02 20:15:48

我不知道您的问题的名称或您找到的解决方案的名称。但是你的解决方案（或多或少）是我提出的解决方案。我认为这是解决这类问题的最佳方案。

如果您的数据至少有点排序，您可以通过考虑此排序找到一个稍微好一点的解决方案。例如。您的数据可以按日期排序，但不能按时间排序。然后，你会分开个别日期。

来源

2010-08-02 11:45:24 h2stein

最大延迟
如果日志条目有一个“最大延迟”（例如，2小时的最大延迟，一个8:12的事件将永远不会被一个10:12活动结束后上市），你可以看看提前和排序。

做排序
另外，我第一次尝试排序 - 至少，以确保它不工作。一个时间戳可以合理地存储在8个字节中（即使为了您的目的，也可以将250百万字节放入千兆字节）。 Quicksort在这里可能不是最好的选择，因为它具有较低的局部性，插入排序对于几乎排序的数据来说几乎是完美的（尽管它也具有不良的局部性），或者快速排序块，然后将块与合并尽管会增加内存需求，但应该尽可能做。

壁球和征服
或者，您可以使用以下策略：

变换每个事件为
一个“持续时间0的会话”分裂您的会话列表成块（例如1K值/块）
在每个块内，按会话开始排序
合并所有会话，可以合并（已排序之前允许您减少您的外观头）。
将剩余会话的列表压缩到一个大的单个列表中
重复步骤2，直到列表没有变短。
排序和合并在所有

如果你的日志文件具有一种“时间局部性”的你的问题建议，已经是单次应减少的数据，让“全”之类的。

[编辑] [本网站] 1演示了这几乎排序的数据相当不错“与插入排序完成优化的快速排序”。正如这个家伙std ::排序

来源

2010-08-02 12:30:35 peterchen

您使用区间搜索树的解决方案听起来像它会足够高效。

您不会说您提供的数据（仅包含时间戳记日期）是否是您正在处理的实际数据。如果是这样，考虑一天只有24 * 60 = 1440分钟。由于这是一个相对较小的值，因此创建一个位向量（包装与否）并不重要，它会提供一个高效且简单的解决方案。

的位向量（一次填充的）将能够任一的：“具有用户已经在时刻T看见”

应答所述查询在O（1）中，如果您决定只在输入数据中出现相应的时间（我们可以称之为“保守加法”）时才将矢量字段设置为真，或者
回答查询“在T时间会议活动吗？”在O（1）中也是如此，但是常数较大时，如果您决定在该时间会话处于活动状态时将向量的字段设置为true，则表示当您添加时间T时，将以下29个字段设置为true。

我想指出，通过使用附加保守，你不限制自己到30分钟的会议间隔：的确，你可以随时在线修改这个值，因为结构不推断任何信息，但仅仅是存储/查看存在记录的实用方式。

来源

2010-08-02 14:39:34

算法问题：确定“用户会话”

回答

相关问题