代码之家 › 专栏 › 技术社区 › NoozNooz42

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

language-agnostic algorithm

11

NoozNooz42 · 技术社区 · 16 年前

我有一个真正有趣的(至少对我来说)问题要解决(而且,不,这不是家庭作业)。它相当于:您需要确定用户在其计算机前所打开的“会话”和“会话开始和结束时间”。

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

基本上,我得到的输入是这样的(输入没有排序,我宁愿在确定会话之前不排序):

比如说,30分钟的不活动期。

然后我需要找三个疗程:

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

如果不活动的时间设置为12小时,那么我会找到一个大的会话:

[06:17...09:51]

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

至少有15分钟的不活动有效期。

我不想事先分类的原因是我会得到一个许多而仅仅将数据存储在内存中是有问题的。但是,这些数据中的大部分应属于同一会话(与数据量相比,会话相对较少,可能类似于数千到1[每会话数千个用户输入])。

到目前为止,我正在考虑读取一个输入(比如06:38)并定义一个时间间隔[数据最大值不活动…数据+最大值不活动],对于每个新输入,使用二分法( 原木 )搜索以查看它是否属于已知间隔或创建新间隔。

我会对每一个输入重复这个步骤,从而得出解决方案 n log n AFITEC。而且,好的是,它不会使用太多的内存,因为它只会创建间隔(并且大多数输入将落在一个已知的间隔中)。

而且,每次如果落在一个已知的区间内,我都必须改变区间的下限或上限,然后看看是否需要与下一个区间“合并”。例如(最多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)

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

这样的问题有名字吗?你怎么解决这个问题?

编辑

我很想知道如果我计划以我计划的方式解决它,我应该使用哪种数据结构。我需要两者原木搜索和插入/合并功能。

4 回复 | 直到 16 年前

1

2

Heinrich Apfelmus 16 年前

你要的是 在线算法 即可以为每个新的输入时间增量计算一组新会话的会话。

关于选择 数据结构 对于当前会话集,可以使用平衡二进制搜索树。每个会话由一对表示 (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] 在我的伪代码中。

2

3

peterchen 16 年前

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

做排序
或者,我首先尝试排序——至少要确保它不起作用。时间戳可以合理地存储在8个字节中(4即使出于您的目的,您也可以将2.5亿字节放入一个千兆字节中)。快速排序可能不是这里的最佳选择,因为它的位置较低,插入排序几乎适合几乎排序的数据(尽管它的位置也不好),或者,快速按块排序,然后用合并排序合并块应该可以,即使它增加了内存需求。

壁球和征服
或者,您可以使用以下策略:

将每个事件转换为“持续时间为0的会话”
将会话列表拆分为块(例如1K值/块)
在每个块中,按会话开始排序
合并所有无法合并的会话(以前排序后可以减少前瞻性)。
将剩余会话的列表压缩为一个大列表
重复步骤2,直到列表不再变短。
全部排序并合并

如果您的日志文件具有您的问题所建议的“时间位置”,那么单次传递就应该减少数据以允许“完整”排序。

[ 编辑 [这个网站] 1 演示了“插入排序完成的优化快速排序”,这对几乎排序的数据非常好。这家伙也一样,std::sort

3

1

h2stein 16 年前

我不知道您的问题的名称或您找到的解决方案的名称。但你的解决方案(或多或少)是我提出的解决方案。我认为这是解决那种问题的最好办法。

如果您的数据至少有点有序,那么考虑到这种排序,您可能会找到更好的解决方案。例如,您的数据可以按日期而不是按时间排序。然后,将各个日期分开。

4

1

Jérémie 16 年前

使用间隔搜索树的解决方案似乎足够有效。

您不必说您提供的数据是否(仅由时间戳组成,没有日期 )是您正在处理的实际数据。如果是这样,考虑每天只有24*60=1440分钟。因为这是一个相对较小的值,所以创建一个位向量(打包或不打包——并不重要)就好像它可以提供一个既高效又简单的解决方案。

位向量(一旦填充)将能够:

回答问题“在时间t时是否发现用户?”在O(1)中,如果您决定只在输入数据上显示相应的时间时将向量的字段设置为真(我们可以称此方法为“保守加法”),或者
回答问题“T时会话是否处于活动状态?”在O(1)中,但是使用一个更大的常量,如果您决定将向量的一个字段设置为真(如果会话当时处于活动状态),我的意思是,当您添加时间t时,您还将下面的29个字段设置为真。

我要注意的是,通过使用保守的加法,您不会将自己限制为30分钟的会话间隔:实际上,您可以随时在线更改此值,因为结构不推断任何信息,而只是存储/查看状态记录的一种实用方法。