【性能优化】1.3 [内存查找] 位置索引

【性能优化】1.2 [内存查找] 序号定位

1.3 位置索引

有时候我们希望查找出目标值在序表中的位置,而不是目标值本身。如果序表对被查找键无序时,就无法使用二分法来提高性能了。事先把数据按被查找键排序后可以使用二分法,但会丢失目标值在原序表的位置信息,无法完成我们的查找任务了。

比如,某个登录系统记录了一批用户的登录时间和用户 ID,按登录时间排序。现在我们想找出指定 ID 的用户登录之后有多长时间没有其它用户再登录。

如果能找到指定 ID 用户的登录记录在数据表中的位置,则只要再找出下一条记录来计算时间差,就能容易地完成任务。但原数据没有按用户 ID 排序,只能顺序查找,这会很慢。如果把数据按用户 ID 排序了,又会丢失位置信息。

使用位置索引可以解决这个问题:


A

B

1

=10000.sort(rand())

=20000.sort(rand()).to(10000)

2

=A1.new(elapse@s(now(),-B1(#)):tm,~:id,   … )

3

=A2.psort(id)

=A2(A3)

4

=B3.pselect@b(id:1234)

=A2.calc(A3(A4),tm[1]-tm)

这段代码略有点绕,需要仔细理解。

在 B3 得到针对用户 ID 有序的排列时,在 A3 保持一个 psort 返回的位置序列,这样在 A4 使用二分法查找到目标值在 B3 中的位置后,再利用 A3 计算出该目标值在原序表 A2 中的位置,然后再用定位计算就可以实现任务。查找过程(A4 和 B4)使用了一次二分查找和两次序号定位查找,整体复杂度和二分法相当,比直接在原集上做顺序查找要快得多。

【性能优化】1.4 [内存查找] 哈希索引
【性能优化】 前言及目录