【性能优化】1.1 [内存查找] 二分法

【性能优化】 前言及目录

1.1 二分法

内存中的序表 T 有字段 K,给定查找值k,找出 T 中字段 K 取值为 k 的记录,字段 K 称为被查找键,找到的记录称为目标值目标记录

常规的顺序查找将依次遍历比对 T 的每个成员,如果 T 中有 N 条记录,则平均比对次数是 N/2,复杂度为 O(N)。如果 T 恰好对 K 有序(序列 T.(K) 或 T.(-K) 是递增列),则可以使用二分法

进一步介绍算法之前先说明一下:本书讨论的大部分算法对于序表和排列都通用,甚至对序列也有效。但有时使用某种术语来描述会相对方便,理解原理的读者能自行推广到其它类似的场景。在应用这些算法时并不用严格遵守书中描述的前提和场景,而是要理解原理后再确认面临的场景是否适应该算法,有时还要对算法进行少量改造。

二分法是常见算法,以 T.(K) 升序为例,基本逻辑如下:


A

B

C

1

=1

=T.len()


2

for

=(A1+B1)\2

=T(B2)

3


if   k==C2.K

return   C2

4


else   if k>C2.K

>A1=B2+1

5


else

>B1=B2-1

6


if   A1>B1

return   null

用 k 与 T 的位置居中的成员对比,如果不相等,则根据比对大小排除掉一半成员,在剩下一半成员构成的子集中继续执行此动作,直到找到目标值或者剩下子集为空为止。因为每次能排除掉一半成员,所以最多只要比对 log2N 次就可以找到目标值(或确认找不到),复杂度为 O(logN),在 N 较大时就会比顺序查找有非常明显的优势。在 N 较小时,因为二分法的过程相对复杂,反而可能比顺序查找更慢。通常 N>=8 时,二分法就会有优势。

如果 T.(K) 有重复值,目标值则可能有多个,使用二分法在找到一个目标值后还要再向前向后连续比对更多记录。当平均重复次数为 M 时,每次查找将平均多做 M 次比对,总复杂度是 O(logN+M)。通常只是偶而有重复值,即满足 M≪log2N,复杂度仍然可以认为是 O(logN)。如果重复值较多,则分析复杂度时就不能忽略 M。无论有无重复值,顺序查找的复杂度始终是 O(N)。有重复值时二分法的复杂度一般仍然更低,但实践中要更大的 N 才会比顺序查找有优势。

SPL 提供有二分法选项,可以直接使用:


A

B

1

=10000.new(string(~,"00000"):id,   ~\3:K).keys(id)

2

=A1.find@b("01234")


3

=A1.select@b(K:1234)

=A1.select@b(K-1234)

4

=A1.pselect@b(K:3210)

=A1.pselect@b(K-3210)

find@b 针对主键,找到一个就返回。select@b 则会按有重复值的情况处理,pselect@b 缺省只返回一个,但会去寻找第 1 个,也要考虑重复值。

需要注意的是,select@b 和 pselect@b 的参数中不能使用常规逻辑表达式,而要使用冒号分隔符或者返回数值的表达式,因为逻辑表达式只能计算出 true,false 值,无法决定不相等时下一步的二分方向;数值表达式为 0 表示找到,<0 和 >0 则用于指明下一步的二分方向。

读者可以自己用 SPL 对比二分法与顺序查找的性能差异。

还需要提醒的是,使用二分法要求事先有序。排序是个很慢的动作,不能为了临时使用一次二分法查找而先排序,那只会更慢得多。通常我们要在某个序表中多次查找,这时候就可以对序表先做一次排序,之后的多次查找即可获得更优良的性能。

【性能优化】1.2 [内存查找] 序号定位
【性能优化】 前言及目录