Extreme Optimization #1.1：IP地址到国家/地区代码的映射。

• 下载完整演示项目（含数据文件） - 451 Kb
• 下载源代码 - 15 Kb

引言

Extreme Optimization（极致优化）可以在速度和大小方面带来显著的改进。在本文中，我们将通过一个例子，展示如何利用我们对现有问题的理解来修改标准算法，从而获得显著的性能提升。

背景

我们将在 R. Reyes 撰写的文章《C# 中优化的 IP 到 ISO3166 国家/地区代码映射》的基础上进行。目标是在一个包含超过 52,000 条记录的表中，快速查找与 IP 地址对应的国家/地区代码，同时最大限度地减少内存使用。我们只关心当前的 IPv4 地址，它们由一系列 4 个字节值组成，范围在 0-255 之间。

现有解决方案

Reyes 先生引入了 PATRICIA 字典树结构（根据 Donald Knuth 的发音，读作 'try'），以高效地执行查找。我们在此不再赘述其实现细节，可在原文中找到。

极致优化

Extreme Optimization™ 从彻底理解我们正在解决的问题开始。我们将这种理解与对现有算法的深入了解相结合。

更有效地存储 IP 地址

原始算法使用 BitVector 类来存储键。键在内部表示为 Byte 数组。仅存储键的区分部分，因此许多向量实际上可能只有一字节长。但是，在隔离键的有效部分和检查匹配时，会涉及大量的位移操作。

第一个观察是，我们不需要一个通用的 BitVector 类来存储我们的数据。我们的键最多是 32 位序列。它们可以完美地放入一个 32 位无符号整数中。这将消除管理数组对象的开销。

此外，我们可以通过在每个节点中存储整个键并使用按位异或（Xor）运算符来消除过度的位移。布尔异或（互斥或）运算符在两个操作数不同时返回 true，相同则返回 false。按位异或版本比较两个数字中位置相同的位。当位相同时，在结果中为对应位分配 0，不同时分配 1。

要找到两个键的共享部分，我们将两个值进行异或。键的长度是结果中前导零的数量。我们可以通过将结果与 2 的幂进行比较来找到这个数量。对于 32 位键长度，如果结果小于 2^n，我们就知道两个键的前 32-n 位是相同的。

这里有一个例子。我们要找到两个 IP 地址的公共键长度：IP1= 207.176.130.34 和 IP2= 207.176.151.11。

IP 地址	二进制值	数值
IP1 (207.176.130.34)	11001111.10110000.10000010.00100010	411,303,936
IP2 (207.176.151.11)	11001111.10110000.10010111.00001011	411,336,704
IP1 xor IP2	00000000.00000000.00010101.00101001	5,417

结果 5417 小于 8192 = 2^13。因此，这两个 IP 地址的前 32 - 13 = 19 位是相同的。

在将一个键值与节点的子节点键值进行比较时，我们可以从父节点的键长度开始计数。

优化用于二进制键的 Patricia 字典树

其次，我们处理的是二进制数据。PATRICIA 是 Practical Algorithm To Retrieve Information Coded In Alphanumeric（用于检索编码在字母数字信息中的实用算法）的缩写。这个名称暗示 Patricia 字典树最适合字母数字数据，其中每个节点可以有许多子节点。我们问题中的键是 0 和 1 的序列。这意味着任何节点最多可以有两个子节点。一个子节点将以 0 开头的前缀。另一个将以 1 开头的前缀。

这意味着我们可以移除用于存储子节点引用的 ArrayList。我们用两个引用替换它，一个用于前缀以 0 开头的子节点，另一个用于前缀以 1 开头的子节点。如果其中一个子节点不存在，相应的引用就是 null。

ArrayList 是一个相对昂贵的数据结构，用于存储非常短的列表。除了引用类型通常的开销外，它还会为未使用的条目分配空间。消除开销和未使用空间应该会显著降低我们的内存需求。

在 trie 中查找值时，我们可以简单地使用当前键长度之后的第一个位的值来选择下一个子节点。然后我们可以快速检查我们的值是否与子节点的完整长度匹配。

进一步优化

一个 trie 可以只有一个根元素。查找的前几个步骤将用于处理 IP 地址的第一个字节或 8 位。如果我们为第一个键位的所有可能值创建单独的根，我们将消除 6 到 7 个不必要的递归步骤。通过预先选择更多的前导位，我们可以做得更好。我们将这个位数称为索引长度。

但是，我们必须小心。每个根节点跨越一定范围的 IP 地址。我们输入表中的一些条目将跨越一个涵盖多个根节点的范围。我们必须将这些条目添加到所有适用的根节点，调整范围以适应该根节点的范围。这会带来内存占用的小小代价，但速度提升非常显著。

如果我们使用至少为 1 的索引长度，我们可以使用 Int32 值作为键，而不是不符合 CLS 标准的 UInt32，而不会因使用有符号数而产生任何并发症。传递给节点的键将至少与节点的键具有相同的前导位。因此，异或操作结果的前导位将始终为零，表示一个正值。

查看代码

新项目包含三个类。

• BinaryTrie 表示一个以 32 位二进制值为键的 trie。
• BinaryTrieNode 表示 BinaryTrie 中的一个节点。
• IPCountryTable 表示一个查找表。它继承自 BinaryTrie。

BinaryTrie 有两个构造函数。第一个构造函数接受一个参数 indexLength，即用于预选择的位数。它创建 _roots 数组，其中包含根节点。默认构造函数使用索引长度 1。

Add 方法将一个键添加到 trie 中，并返回与该键对应的 BinaryTrieNode。AddInternal 方法负责实际向 trie 添加键的工作。如果给定的 index 没有根节点，它会创建一个。如果根节点存在，请求将传递给根节点，由根节点完成大部分工作。

BinaryTrieNode 表示 trie 中的一个条目。它包含以下字段：

• _key 是一个 UInt32 值，包含当前节点的键。
• _keyLength 是当前键前缀中的位数。
• _userData 指向与键关联的任何用户提供的对象。在此实例中，这将是与节点关联的国家/地区代码。
• _zero 包含对前缀以 0 开头的子节点的引用。
• _one 包含对前缀以 1 开头的子节点的引用。

BinaryTrieNode 有一个内部构造函数，用于 BinaryTrie 创建根节点。它还包含两个私有构造函数。一个创建节点的浅拷贝。另一个使用传递给 Add 方法的数据创建节点。它根据网络可用的地址数量计算键长度。

构建 trie 的大部分繁重工作都在 AddInternal() 方法中完成。我们首先计算当前节点和新条目的公共键长度。如果新键长度小于公共键长度，则新条目成为当前节点的父节点。如果匹配是完整的，即公共键长度至少等于当前节点的键长度，则新条目将被传递给子节点。使用哪个子节点取决于当前键之后的第一个位。

如果匹配不完整，当前节点将被替换为一个新节点，其键为公共键部分。它有两个子节点：(当前节点的) 副本，以及一个新条目的节点。在这两种情况下，位置 _keyLength+1 的位决定了 _zero 和 _one 插槽中的两个子节点分别放入哪个。

查找从 IPCountryTable 直接传递到正确的根 BinaryTrieNode（如果存在）。如果查找键与某个子节点键匹配，则请求将传递给该子节点。否则，我们就找到了最佳匹配。

基准测试结果

使用与原始文章相同的数据集和测试代码，我们发现以下结果。优化版本 #1 指的是 2003 年 5 月 13 日发布在此处的原始代码版本。优化版本 #1.1 指的是最新代码，包括进一步的优化。

	原始版本	优化版本 #1		优化版本 #1.1
	结果	结果	更改	结果	更改
内存使用情况	9,409 KB	2,578 KB	- 72.6%	2,963 KB	- 68.5%
加载时间	7.361s	2.864s	- 61.1%	1.858s	- 74.8%
25,000 次查找	3.475s	0.2567s	- 92.6%	0.1997s	- 94.3%
每秒查找次数	7,194	97,048	+ 1,249%	125,190	+ 1,640%

这是结果的图形表示。

可能的改进

还有进一步优化的空间吗？可能。

一个国家/地区代码会有许多节点引用它。如果我们能消除一个节点，即对于其范围内的每个 IP 地址，在结果 trie 中的最佳匹配节点与我们消除的节点的国家/地区代码相同。当节点的父节点具有相同的国家/地区代码时，就会发生这种情况。

在 trie 构建完成后，我们可以迭代地遍历所有节点，并消除不必要的节点。如果我们能消除大量节点，内存使用量将随之减少，查找速度也将相应提高。这种可能性将在本文的未来更新中探讨。

结论

两个主要目标是最大限度地减少内存使用和最大限度地提高速度。我们进一步优化了一个已经优化的解决方案，在两个方面都取得了显著的改进。我们最初将内存使用量减少了 3/4，并将查找速度提高了 13 倍以上。

通过最新版本，我们在内存占用方面稍微有所牺牲，但性能额外提升了 30%。我们还将二进制 trie 代码与 IP 查找代码分离。现在可以独立使用它。

参考文献

• Rodrigo Reyes 撰写的《C# 中优化的 IP 到 ISO3166 国家/地区代码映射》
• Wesner Moise 撰写的《Arrays UNDOCUMENTED》（数组未公开文档）
• 《Extreme Optimization™》网站。

更新

APNIC（亚太网络信息中心），它是发布本文所使用数据的四个组织之一，最近更改了其统计文件的格式，以符合其他三个组织使用的格式。数据库中的 size 字段现在包含段的总大小，而不是位数。要使用这种新格式的文件，您需要在源代码中进行更改。在调用加载 APNIC 数据文件的 LoadStatisticsFile 时，将 calculateKeyLength 参数设置为 true。