【性能优化】1.2 [内存查找] 序号定位
1.2 序号定位
有时被查找键的取值正好是目标值在序表中的序号（即位置），或者很容易通过查找值计算出目标值的序号，这时可以使用序号定位方法。
A |
|
1 |
=10000.new(~:id, …) |
2 |
=A1(1234) |
3 |
=10000.new(string(10000+~-1):id, … ) |
4 |
=A3(int("12345")-10000+1) |
5 |
=10000.new(date(1999,12,31)+~):dt, …) |
6 |
=A5(now()-date(1999,12,31)) |
7 |
=A5.groups(month@y(dt):ym; … ) |
8 |
=month&y(now()) |
9 |
=A7((A8\100-2000)*12+A8%100) |
A1 的 id 字段本身就是序号值，直接可以用查找值作为位置找到目标值。A3 的 id 字段也是连续数值转成的字串，查找时要倒算出序号。序号定位经常用于日期相关的查找，日期或月份通常是连续值，容易通过某种运算和序号对应上。A5 的 dt 字段是有序的日期，距离起始日期的天数就是目标值的序号。A7 则是以年月作为序号，计算会稍复杂一些。
使用序号定位不需要进行任何比对，计算序号只要做一次，这种查找的复杂度为 O(1)。
上面的 A5 或 A7 中，我们在生成数据时保证了每个序号都有对应的日期，但实际的业务数据中很可能有空缺的日期，这样再使用序号定位就会错位了。
A |
|
1 |
=10000.new(date(2000,1,1)+rand(10000)):dt, … ) |
2 |
=A1.groups(dt; …) |
3 |
=A2(now()-date(1999,12,31)) |
4 |
=A2.align@b(10000,dt-date(1999,12,31)) |
5 |
=A4(now()-date(1999,12,31)) |
A1 生成的日期不能保证覆盖相应时段的每个日期，这样 A2 就可能有缺失的日期，A3 再用序号定位就可能出错了，返回的数据不一定是今天的。A4 中使用 align 做了对齐之后，就可以保证某个日期的记录一定落在对应的序号位置上了，A5 就可以用序号定位来查找了。对于缺失的日期，align 会填一个 null 在对应的位置，这样，如果查找值对应的目标值不存在，就会返回 null，也可以用来判断是否能找到目标值。align 的 @b 选项表示对齐时将使用二分法来查找位置，这样实现对齐动作也会更快一点。
和前面讲过的排序类似，对齐相对于序号定位也是个更慢的动作，不能为了某次临时查找而做对齐再用序号定位。要反复多次查找才能先做对齐，使之后的查找获得高性能。
把查找记录按序号对齐后就可以使用高效的序号定位方法，似乎只要我们能找出一个把查找值计算成序号的办法就行了。
当然不是。比如中国公民的身份证号，由一串数字构成，本身就可以理解成一个自然数，天然是一种序号，但我们并不能把身份证号按自然数对齐再使用序号定位来查找。
序号定位要求一个长度不小于最大序号的序列来存储所有待查找记录和用于填补空缺的 null 值，如果直接把身份证号转换成自然数，其序号范围会大到当前计算机内存无法承受的地步（1017，身份证号共 18 位，最后一位校验不算），要填入 null 的序号数量远远多于有记录的序号。这种时候就无法直接使用序号定位了。
