乾学院 50 号会员
9 回帖  •  1,729 浏览  • 
     ...

【性能优化】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 只能针对主键，所以要先建立主键（keys(id)），主键不会重复，find@b 只找到一个就返回，不考虑重复值。select@b 不要求建立主键，它会按有重复值的情况处理，pselect@b 也会考虑重复值，但缺省只返回一个，它会去寻找第 1 个。

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

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

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

二分法还可以支持区间查找，即查找出被查找键值落在某个连续区间的记录：

A

B

1

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

2

=A1.select@b(between(K,123:1234))

3

=A1.pselect@b(between(K,321:3210))

被查找键对小于区间左边限时，between 将返回 -1，大于区间右边界时返回 1，在区间内则返回 0，正好符合 select@b 和 pselect@b 的要求。

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