276
10
近的点。因为
k-d
树的矩形区域是基于输入点集合创建的,因此这类检查是非常必要的。
在一棵不平衡的
k-d
树中,这种检查可能会达到
O
(
n
)
的总
费用,因此正确处理输入集合
至关重要。
示例解决方案有两个方面的性能提升。首先,对比都是发生在“原始的
raw
)”
double
型数组之间,每个数组均代表了一个点。其次,
DimensionalNode
中的
shorter
方法被
用于确定两个
d
维点之间的距离是否小于当前计算出的最短距离。该方法在部分计算出
的欧几里得距离超过当前最小值时会立即退出。
假定初始的
k
-
d
树是平衡树,那么搜索在递归调用的过程中可以很方便地舍去树中半数
的点。虽然有的时候两次递归调用是必的,但这只发生在计算出的最短距离刚好大于
穿过结点的切分线时。在这种情况下,我们需要继续搜索切分线两边的区域来找出最近
的点。
10.5.4 算法分析
k
-
d
树最初被构建为平衡
k
-
d
树,每层的切分线源自该层剩余点的中位元素。找到目标
查询的父结点需要
O
(log
n
)
的时间,这可以通过假想点被插入
k
-
d
树中时遍历而得。但是,
算法可能会需要进行两次递归调用:一次用于遍历上方的子结点;另一次用于遍历下
方的子结点
如果两次递归的调用过于频繁,算法的性能会退化到
O
(
n
)
,因此有必要了解这种情况
发生的频率。只有当目标点到树结点中的点的垂直距离
dp
小于计算出的最小距离时
多次调用才会发生。随着维度的增加,将会有越来越多的点满足这些条件。
10-1
给出了一些实证说明这种情况发生的频率。表中的平衡
k
-
d
树由单位正方形内
随机生成的
n
个二维点构建而成,
n
的范围在
4~131 072
对于单位正方形内的一个随机点,
共有
50
次的最近点查询,表
10-1
记录了两次递归调用发生的平均次数(即
dp
<
min
[0]
且问题中的结点同时拥有上方子结点和下方子结点)与单次递归调用的对比。
10
-
1
:两次递归调用与单次递归调用比率
n
/
d
=
2
d
=
2
d
=
10
d
=
10
# 递归 # 两次递归 # 递归 # 两次递归
4 1.96 0.52 1.02 0.98
8 3.16 1.16 1.08 2.96
16 4.38 1.78 1.2 6.98
32 5.84 2.34 1.62 14.96
64 7.58 2.38 5.74 29.02
空间树结构
277
空间树结构
10
-
1
:两次递归调用与单次递归调用比率(续)
n
/
d
=
2
d
=
2
d
=
10
d
=
10
# 递归 # 两次递归 # 递归 # 两次递归
128 9.86 2.98 9.32 57.84
256 10.14 2.66 23.04 114.8
512 12.28 2.36 53.82 221.22
1,024 14.76 3.42 123.18 403.86
2,048 16.9 4.02 293.04 771.84
4,096 15.72 2.28 527.8 1214.1
8,192 16.4 2.6 1010.86 2017.28
16,384 18.02 2.92 1743.34 3421.32
32,768 20.04 3.32 2858.84 4659.74
65,536 21.62 3.64 3378.14 5757.46
131,072 22.56 2.88 5875.54 8342.68
从这些随机数据可以看出,对于二维情况,两次递归调用的次数是
0.3*log(
n
)
,这个数
字在
10
维时(
1000
倍增加)攀升
342
*
log(
n
)
。值得注意的是,两个估价函数都满足
O
(log
n
)
但是,当维度
d
增加到和
n
“足够近”的时候会发生什么呢?
10-7
中的数据图可知
随着
d
的增加,两次递归调用的次数会逼近
n
/2
。事实上,随着
d
的增加,单次递归调
用的次数符合正态分布,均值非常接近于
log(
n
)
最终所有递归调用都是双向变化的。
这个发现对于最近邻查询的性能而言,意味着随着
d
趋近
log(
n
)
,使用
k-d
树得到的性
能回报会越来越小,直到和
O
(
n
)
差不多,这是因为两次递归调用的次数停留在了
n
/2
特定的输入数据集会迫使
最近邻算法
甚至在二维情况下都很难工作。例如,
10-1
中的输入点稍作修改,假设这
n
个点互不相同且分布在半径
r
大于
1
的圆周上,最近邻
查询的点则仍位于单位正方形的内部。当
n
= 131 072
时,单次递归调用的次数攀升至
235.8
次,将近
10
倍,两次递归调用的次数则增加到了
932.78
200
倍的增加!)因此,
对于给定的输入集合上的特定查询,最近邻查询会退化到最坏的
O
(
n
)
性能。图
10-8
示为
64
个点组成一个圆时,
k
-d
树的恶化情况。
我们也可以对比一下使用
k
-
d
树的最近邻算法与直接的穷举
O
(
n
)
算法的性能。对于给定
大小
n
131 072
个点的数据集合,执行
128
次随机查询,问当输入集合的维度
d
多大时,
穷举法才会比
最近邻算法
的实现更优呢?
278
10
o
ࠦۨڦ൧઄ူໜጣ
e
ሺ׊ڇْڿࡃۙᆩڦْຕ
ڇْڿࡃۙᆩڦْຕ
e
ྺྼ܈
e
ྺྼ܈
ଇْڿࡃۙᆩڦْຕ
o
ࠦۨڦ൧઄ူໜጣ
e
ሺ׊ଇْڿࡃۙᆩڦْຕ
10-7:随着
n
d
的增加,两次递归调用的次数曲线
我们执行了
100
次实验,去掉最好和最坏的结果,取剩余
98
实验结果的平均值
果如图
10-9
所示当维度为
11
或者更高时,穷举算法的最近邻算法实现超越了
k
-
d
版本的最近邻算法。这个特定的拐点依赖于代码执行所在的机器硬件
n
d
的值以及
输入集合中点的分布。我们并没有在这个拐点上分析构建
k
-
d
树的费用,因为这个费用
可以被分摊到所有查询上。
10-9
的结果表明:与使用穷举法相比,随着维度的增加,使用
k
-
d
树获得的性能改进
会降低。等式中的决定性因素并不是构建
k
-
d
树的费用,而主要是待插入
k
-
d
树中的点
的个数(也不是维度的数量)。对于较大一些的数据集合,节省的费用是显而易见的。
另外一个使性能退化的因素是维度
d
——
计算两个
d
点的欧几里距离是
O
(
d
)
的操
作,虽然也可以将其视作一个常数时间操作,但每次计算无疑会需要更多的时间。
空间树结构
279
空间树结构
10-8:环形数据集导致低效的
k
-
d
ሞ242!183߲ۅฉኴႜ239ْፌৎତֱკڦႠీ
ኴႜ้क़0nt
๼෇ຕ਍ڦྼ܈
ࠓॺ
l
.
e
໇໭
l
.
e
൬ਉ໇໭
10-9:比较
k
-
d
树与穷举算法实现
为了最大化
k-d
树的查询性能,树必须保持平衡。例
10-2
使用了大家熟知的技巧构建了
一棵平衡
k-d
树,它在每一个坐标维度上使用递归进行迭代。简单说,该技巧会选择
点集中的中位元素来代表结点,将低于中位元素的点插入
下方
的子树中,并将高于中位
元素的点插入
上方
的子树中。以下代码适用于任意维度。
10-2
:递归构建一棵平衡
k-d
public class KDFactory {
280
10
private static Comparator<IMultiPoint> comparators[];
//
使用点的
median
方法递归构建
KD
树。
public static KDTree generate (IMultiPoint []points) {
if (points.length == 0) { return null; }
//
将中位元素作为根结点
int maxD = points[0].dimensionality();
KDTree tree = new KDTree(maxD);
//
构建用于比较点的第
i
维的维度比较器。
comparators = new Comparator[maxD+1];
for (int i=1;i<=maxD;i++){
comparators[i] = new DimensionalComparator(i);
}
tree.setRoot (generate (1, maxD, points, 0, points.length-1));
return tree;
}
//
points[left, right]
中生成
d
(1 <= d <= maxD)
结点
private static DimensionalNode generate (int d, int maxD,
IMultiPoint points[],
int left, int right) {
//
优先处理简单的情况。
if (right < left) { return null; }
if (right == left) { return new DimensionalNode (d, points[left]); }
//
数组
[left, right]
进行排序,选择第
m
个元素为中位元素,
//
保证在其之前的元素将都小于等于该中位元素,尽管这些元素并未排序。
//
类似地,保证在其之后的元素将都大于等于该中位元素,尽管也是没有排序的。
int m = 1+(right-left)/2;
Selection.select (points, m, left, right, comparators[d]);
//
将该维度的中位点作为父结点
DimensionalNode dm = new DimensionalNode (d, points[left+m-1]);
//
更新到下个维度,或重置维度为
1
if(++d>maxD){d=1;}
//
递归计算左子树和右子树,即
n
维中所谓的“下方”和“上方”。
dm.setBelow (maxD, generate (d, maxD, points, left, left+m-2));
dm.setAbove (maxD, generate (d, maxD, points, left+m, right));
return dm;
}
}
选择操作曾在第
4
章中介绍过。在平均情况下它可以
O
(
n
)
的时间内递归地选择第
k
的元素。不过在最坏情况下,其性能会退化到
O
(
n
2
)

Get 算法技术手册(原书第2 版) now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.