【性能优化】1.3 [内存查找] 位置索引
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）使用了一次二分查找和两次序号定位查找，整体复杂度和二分法相当，比直接在原集上做顺序查找要快得多。
