Noo*_*z42 11 language-agnostic algorithm
我有一个非常有趣(至少对我来说)的问题需要解决(而且,不,它不是功课).它等同于:您需要确定用户在他的计算机前面的"会话"和"会话开始和结束时间".
您可以获得进行任何用户交互的时间以及最长的不活动时间.如果在两个用户输入之间经过的时间大于或等于不活动时间,则它们是不同会话的一部分.
基本上我得到的输入是这样的(输入没有排序,我宁愿在确定会话之前不对它们进行排序):
06:38
07:12
06:17
09:00
06:49
07:37
08:45
09:51
08:29
而且,比如说,一段时间不活动30分钟.
然后我需要找到三个会话:
[06:17...07:12]
[07:37...09:00]
[09:51...09:51]
如果不活动时间设置为12小时,那么我只会找到一个重要的会话:
[06:17...09:51]
我怎么能简单地解决这个问题？
有一个最短的有效不活动时间,大约15分钟.
我之前不想排序的原因是我会获得大量数据并且只将它们存储在内存中会有问题.但是,大多数这些数据应该是相同会话的一部分(与数据量相比,会话数量相对较少,可能是每次会话数千比1 [数千个用户输入]).
到目前为止,我正在考虑读取输入(例如06:38)并定义间隔[data-max_inactivity ... data + max_inactivity],并且对于每个新输入,使用二分法(log n)搜索来查看它是否下降在已知间隔或创建新间隔.
我会为每个输入重复此操作,使解决方案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搜索和插入/合并功能.
您需要一种在线算法，即可以为每个新输入时间增量计算一组新会话的算法。
关于当前会话集的数据结构的选择，可以使用平衡二叉搜索树。(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]