CPTrie：.NET 的有序数据结构
一种内存高效的 Patricia trie，实现了 IDictionary 并支持“查找最近键”操作。
引言
Trie 是一类树形数据结构，用于存储有序集合或映射（字典），其中树的每个节点仅存储或代表键的一部分，而不是整个键。
这里我使用了“trie”的宽松定义，因为我开发了一种特殊的 trie。我称之为“Compact Patricia Trie”或 CPTrie。与内存需求非常高的标准 trie 不同，CPTrie 的内存需求比其他集合类型低，尤其是在某些情况下，例如具有有限字母表的键（例如 ASCII 文本）。它通常比 SortedDictionary 慢，比 Dictionary 慢得多，但它可能比两者都使用更少的内存。
因此，虽然通常使用 trie 来快速构建有序列表，但会以高内存使用为代价，而 CPTrie 则提供了相反的权衡。
如果您以前从未听说过 trie，请阅读 Wikipedia 文章；从现在开始，我将假定您理解该概念。
背景
几个月前，我读到了一篇关于 Judy 数组的文章，这是一种 C 稀疏数组数据结构，它以几种方式之一组织自身，以同时保持速度和内存效率。您可以为 0 和 uint.MaxValue 之间的任何索引序列分配一个值，Judy 会将其组织成一种最多 4 层深的 trie（每层对应索引的一个字节），无论键的分布如何，它始终快速且内存高效。例如，如果您为 0 到 1000 之间的每个索引分配一个值，Judy 将生成一个类似于普通数组的数据结构，以便值紧密打包。同时，如果您使用索引集群，例如 23-70、200-210 和 500-550，其中包含一些未使用的槽，Judy 将选择一种称为“位图”的不同安排。无论如何，它都会最大限度地减少访问的处理器缓存行数量。
谢谢你，Judy...
我对 Judy 的想法如此着迷，以至于我想为 .NET 制作类似的东西，但在思考和编码了几天后，我得出的结论是，在 C# 中，我无法接近 Judy 的速度或内存效率。
例如，Judy 通常将数据存储在指针中。任何指向堆块的指针的低 2 或 3 位始终为零；因此，您可以将这些位用于与指针一起存储信息，或者您可以使用其中一位来指示指针直接保存整数。动态语言 Ruby 使用此技术在变量中存储整数。这样，一个变量可以指向一个对象，或者（如果最低位是 1）它可以直接存储一个整数，而无需堆空间。遗憾的是，这在 C# 中似乎是不可能的，即使使用不安全代码，因为垃圾回收器可能会在遇到这些非指针时崩溃。
C# 的另一个重要限制是，您不能在类中存储固定长度的 object[] 数组——您只能使用固定长度的基本类型数组。即使那样，您也必须在所有地方都加上 unsafe 关键字，这样代码在“安全”上下文中就无法使用。外部 object[] 数组的效率明显较低，因为它需要一个 4 DWORD 的头，并且可能需要额外的缓存行来访问。哦，在 .NET 中，普通对象的分配对齐无法控制，因此很难对齐到缓存行边界。
……我离开你了，去拥抱 Patricia
然后，在阅读了 Burst tries 和 Patricia tries 后，我决定也许有可能为 .NET 制作一种有用的新数据结构。此外，在将一些 C++ 代码移植到 C# 时，我感到很恼火，因为没有 .NET 等效的 map::lower_bound，我正好想解决这个问题。
介绍 CPTrie
CPTrie 结合了...
- Patricia trie 将多字节前缀存储在单个节点中的思想
- Burst trie 在不分解公共前缀的情况下将有限数量的键存储在一起的思想
- Judy 的思想，即使用多种节点类型，以非常紧凑的形式存储数据，并通过缓存友好来获得速度
我想我也可以称它为 PBJ trie。那会很美味。
我还想使用 Judy 的思想，即为不同的键密度使用不同类型的节点，但我没有找到一种有效的方法将 Judy 的“位图”和“未压缩”节点移植到 .NET，同时又要支持可变长度键。但实际上我有点跑题了。
CPTrie 本身是一个抽象基类，它仅将键视为字节数组。您想支持的每种键都需要一个派生类来将键转换为字节数组。为了将字符串存储在 CPTrie 中，我提供了 CPStringTrie 类。当您将字符串存储在 CPStringTrie 中时，字符串会先以 UTF-8 格式编码，然后再放入 trie。要存储整数键，请使用 CPIntTrie。如果您实际上想使用字节数组作为键，请使用 CPByteTrie。
如果您使用 CPStringTrie 来保存字符串，它最终可能会变成一个“稀疏”（也称为“标准”）节点（CPSNode）的树。使用 CPIntTrie 时，根据键的分布最多使用三种不同类型的节点。小型集合（无论键的分布如何）始终使用 CPSNode。
通过图解来解释 CPTrie 的结构会很有帮助。假设您运行以下代码
CPStringTrie<int> t = new CPStringTrie<int>();
t["This little piggy went to market"] = 1;
t["This little piggy stayed at home"] = 2;
t["This little piggy had roast beef"] = 3;
t["This little piggy had none"] = 4;
t["And this little piggy went"] = 5;
t["'Wee wee wee' all the way home."] = 6;
t["And then some wolf came along"] = 7;
t["and blew down two of their houses!"] = 8;
CPStringTrie 将包含两个节点，结构如下
当您添加键时，节点必须扩大自身或分裂自身（创建子节点）以腾出空间容纳新键和值。起初，它会扩大自身，但到某个时候，它会注意到一个共同的前缀并决定创建一个子节点。
请注意，trie 是排序的，但排序顺序区分大小写（大写字母在前，小写字母在后，这是 ASCII 的自然顺序）。与支持各种排序顺序的 SortedDictionary 不同，区分大小写的排序是 trie 的固有限制（有一种解决方法，但我尚未尝试过）。
与 Patricia trie 一样，CPSNode 可以在单个节点中保存键的多个字节。有点像 Burst trie，当两个键具有共同前缀时，CPSNode 不会立即创建新节点，因为将键分组到一起比分离它们更有效。但是，与 Burst trie 不同的是，CPSNode 通过创建子节点而不是创建新父节点来分裂。
细节（如果不关心请跳过）
CPSNode<T>：“标准”或“稀疏”节点
一个 CPSNode<T> 由以下几部分组成：
- 用于编码键部分的“单元”（
SCell[]）数组 - 将子节点与公共前缀关联的“子节点”（
CPNode[]）数组 - 与当前节点中终止的键（即没有子节点的键）关联的“值”（
T[]）数组
某些节点没有子节点，因此子节点数组可能为 null。同样，可能没有值；事实上，不会为 null 值分配存储空间，因此如果您想存储字符串的集合而不是字典，请将所有值设置为 null 以节省内存。
单元是使节点非常紧凑的创新部分。普通的 .NET 字符串占用大量空间，因为每个字符串都有一个 12 字节的头以及一个 2 字节的空终止符，有时还有 2 字节的填充（我认为在 32 位进程中）。此外，如果文本是英文，一半的空间会浪费在 UTF-16 的空字节上。通过将多个字符串编码到单个“单元”数组中，所有字符串只需要一个 12 字节的头，并且没有空终止符。
单元是 4 字节的组，用于编码部分（或全部）键和指向值或子节点的指针。如果 CPSNode 包含 _count 个键（或部分键），则前 _count 个单元是排序的，并描述这些键的开头。每个单元包含键的前 3 个字节（K0、K1 和 K2），因此前 _count 个单元告诉我们每个键的前三个字节。第四个字节称为 P，其作用是指向另一个单元、子节点或值，具体取决于其值。
- 子节点（如果
P < _count）；[P]是子节点数组的索引 - 另一个单元（如果
P < 222）；[P]是单元数组的索引 - 非空值（如果
P < 254），其中[253-P]是值数组的索引 - 空值（如果
P == 254）
如果 P == 255，则表示该单元是空闲的，并且它是未使用单元的双向链表的一部分。
由于 P 只有一个字节，因此 CPSNode 的大小必须相当有限。最多有 32 个值；所有键加在一起最多不能使用 222 个单元；我任意选择了 34 个 _count 的限制和 50 字节的任何单个键的长度*。单个节点中的键数量无论如何都必须严格限制，因为前 _count 个单元形成一个排序数组，而构建一个具有 N 项的排序数组需要 O(N2) 时间。先构建一个未排序数组然后对其进行排序会更快（O(N log N)），但出于各种原因，这似乎不切实际。限制也不能太低，因为随着键的数量减少，CPSNode 的内存效率会降低，因为分配了更多的对象和数组，导致更多的开销。此外，从一个节点到另一个节点的遍历可能需要额外的时间，因为处理器在等待缓存行填充时会更频繁地停顿。
* 注意：我不是说键限制为 50 字节，只是说长度超过 50 字节的键将被分解成一系列节点。
如果 P 指向一个值或子节点，键可能不会使用该单元中可用的全部三个字节。K2 的特殊值指示这种情况；例如，K2==254 表示键在只有一个字节（K0）后结束。当然，如果数字 254 碰巧是键的第三个字节，则需要特殊处理。
任何给定节点中最多可以有一个零长度键，但在某些情况下，可能会有一个零长度单元跟随一个三长度单元，其中 254 这样的特殊数字出现在键的末尾。
CPBNode<T>
由于 CPSNode 最多可以包含 34 个项，因此它可以舒适地容纳一组以字母表中每个字母开头的单词（例如，“apple”、“banana”、“coconut”、“donut”等）。但是，如果键的开头（或公共前缀之后）有超过 34 个不同的字符，则需要不同的数据结构。
我想做一些类似 Judy 的“位图节点”的事情，但我没有想出在 .NET 中实现它的有效方法。因此，我实现了一种简单的位图节点，我称之为 CPBNode。CPBNode 只是将“字节空间”划分为 8 个切片，每个切片都有一个子 CPSNode。有一个 CPSNode 用于以 0 到 31（子节点 #0）开头的键，另一个 CPSNode 用于以 32 到 63（子节点 #1）开头的键，以此类推。这样，任何子节点中永远不会有超过 32 个唯一的起始字节。当 CPBNode 被要求创建一个键，如“~foo~”时，它会观察到“~”（0x7E）在切片 #3 中，因此它将“创建”请求转发给子节点 #3。如果某些切片不需要（例如，如果没有非 ASCII 字符），则不会为未使用范围分配 CPSNode。
当项目数量少于 24 个时，CPBNode 将切换回 CPSNode。CPBNode 从不会将自身转换为 CPBitArrayLeaf。
CPBitArrayLeaf<T>
CPBitArrayLeaf 是我添加的一种新节点类型，用于提高 CPIntTrie 在检测到密集打包键（即整数序列接近在一起）时的空间效率。CPBitArrayLeaf 也是最快的节点类型。理论上，字符串 trie 也可以使用此节点类型，但仅当存在大量长度相同的字符串且仅最后一个字符不同时。
顾名思义，CPBitArrayLeaf 是一个带有位数组（称为 _flags）的叶节点。它仅支持 1 字节键，位数组为每个可能的 256 个键保留两个位。还有一个 _values（类型 T[]）数组和一个 _indices 表，用于将键映射到 _values 数组中的槽。_flags 实际上是两个 256 位数组：一个数组跟踪正在使用的键，另一个数组跟踪正在使用的 _values 中的条目，以便可以快速找到空闲槽。
如果添加的键不是 1 字节，则节点必须立即转换为 CPSNode 或 CPBNode。
CPBitArrayLeaf 的键长度固定——非空值的数量会影响其大小，但键的数量不会。因此，当 CPBitArrayLeaf 几乎满（接近 256 个键）时，它非常高效，但在几乎为空（接近 0 个键）时效率低下。
通常，当 CPSNode 填满 34 个项且每个键都是一个字节（无子节点）时，它会切换到 CPBitArrayLeaf；当项目数量少于 24 个时，CPBitArrayLeaf 会切换回来，此时这两种节点类型占用相同的内存量。但是，当键没有关联值时，CPBitArrayLeaf 更紧凑，因为 _indices 映射会产生开销。因此，如果您存储的是一个集合（所有值为 null）而不是字典，CPSNode 将在 16 个项时切换到 CPBitArrayLeaf，并在项数降至 12 个以下时切换回 CPSNode。
删除
如果您只插入节点，CPTrie 的内存效率会相当高，但删除呢？嗯，请放心，删除键和插入一样快……至少我认为是这样，但我没有为此做基准测试。但是，在删除了大部分键之后，trie 的结构可能会效率降低。
请记住，在插入过程中，节点不会急于分裂，因为多个小型节点通常不如一个大型节点有效。这是因为如果节点很小，其大小的更大一部分将用于 .NET 对象头，并且平均而言，在扫描键时必须遍历更多节点（当我们插入、删除、查找或枚举键时，键会被“扫描”）。删除键时，不会将小型节点合并成大型节点；只有当节点中的最后一个键被删除时，该小型节点才会被消除。
最坏情况并不糟糕。在最坏的情况下，在删除了一个非常大的 CPTrie 中的大多数节点后，“Patricia trie”属性可能会丢失，从而增加空间开销。但是 trie 不能像二叉搜索树那样“失衡”，因此 CPTrie 拥有平衡算法并非至关重要。CPSNode 确实会注意到其大部分单元未被使用时，在这种情况下它会切换到较小的数组。
优化 trie
您可能听说过，当您向 List<T> 添加项时，这些项会被添加到固定大小的内部数组中。当该数组已满时，List<T> 会将这些项复制到一个大小是其两倍的新数组中，然后丢弃原始数组。
CPSNode<T> 对其每个数组（_cells[]、_children[] 和 _values[]）执行类似的操作；因此，通常会存在一些未使用的数组条目，浪费空间。
CPTrie 在复制自身时可以进行自我优化，因此您可以通过调用 Clone() 然后丢弃原始 trie 版本来消除此空间。不幸的是，目前它不支持原地优化，因此当您创建克隆时，需要同时为原始 trie 及其克隆分配内存（如果 trie 非常大，这只是一个问题）。
在某些应用程序中，您会构建一个 trie，然后多次扫描它而根本不修改它。在这种情况下，您应该优化 trie。请注意，优化过程只是丢弃未使用的数组条目；它不会优化 trie 的结构（例如，来处理已删除的项目）。
我的基准测试程序显示，优化后的 CPTrie 通常会小 20% 左右。
在一个程序中（例如我的基准测试），使用大于处理器缓存的数据集，我发现优化后的 CPTrie 在查找键时速度大约快 10%。我相信这与 引用局部性 有关，原因有两个：
- 由于单元数组中的空白区域更少，一个长度大于 3 字节但位于同一单元数组中的键更有可能位于同一缓存行上。
- 优化后的 trie 节点会同时分配其三个数组。由于.NET 内存管理器倾向于将同时分配的对象放在内存的相邻位置，因此节点本身及其三个数组很可能在内存中是连续的。因此，它们共享一些缓存行，并且可以以更少的处理器停顿进行访问。
何时应该使用 trie？
在管理大量数据时，选择合适的数据结构至关重要。如果您的键不是字符串且无法表示为字节数组，那么您无论如何都无法使用 CPTrie。如果您不需要按排序顺序访问键，那么您最好使用哈希表。.NET 的 Dictionary<K,V> 是一个出色的哈希表设计，它既简单（代码量小）又快速。
如果您需要在所有键都添加到列表之后才按排序顺序访问键，那么使用标准的 Dictionary，甚至 List<KeyValuePair<K,V>> 可能仍然更好，因为这两者都比 SortedDictionary 和 CPTrie 快得多。将所有键值对添加到 Dictionary 或 List，然后（如果您使用了 Dictionary）调用 ToList() 将其转换为 List，然后使用 List<T>.Sort() 对列表进行排序。
另一方面，如果您需要在查询（取决于排序顺序）与集合修改之间进行交错，那么 SortedDictionary 和 CPTrie 就很有意义了。如果您需要不区分大小写或区分区域设置的排序字符串，您可能应该使用 SortedDictionary。
在某些情况下，您应该考虑某种并行数据结构或算法（标准的 Dictionary、SortedDictionary 和 CPTrie 都是单线程的）。
那么，何时应该使用 CPTrie？
使用 CPTrie 的一个原因是它提供了 SortedDictionary 所缺乏的四种操作：
- 反向枚举：从
GetEnumerator()获取一个枚举器，然后反复调用MovePrev()而不是MoveNext()。 - 查找最近较大的键：调用
Find()或FindAtLeast()以获取指向等于或大于所请求键的键的枚举器。 - 获取下一个键/值和获取上一个键/值：
SortedDictionary只能让您在从头开始枚举时获取下一个键。使用CPTrie，您可以从任何您想要的键开始（向后或向前）枚举。
没有理由 SortedDictionary 不能提供这些操作，但不知何故，它没有。
以下是考虑 CPTrie 的更多原因：
- 您的键有许多共同前缀。例如，一组 URL 都以少数几个前缀之一开头，例如“http://”、“http://www.”、“ftp://”、“file:///”等等。在这种情况下，
CPTrie只存储一次公共前缀，从而在大型集合中节省大量内存。在这种情况下，SortedDictionary的查找速度最差为 O(K log N)（其中 K 是键的长度，N 是集合大小），而CPTrie最多为 O(K)。 - 您的数据集非常大，您需要避免使用比物理 RAM 更多的虚拟内存。例如，如果机器有 1 GB RAM，则当您的数据结构超过该大小时，计算机将运行缓慢。在 32 位 Windows 进程中，您通常不能使用超过 2 GB 的总内存；如果您可能接近此限制，请考虑
CPTrie。在某些情况下，CPTrie可以将 trie 本身以及所有键编码到与Dictionary和SortedDictionary仅用于存储数据结构和指向键的指针相同的内存量中。前提是您不需要以字符串形式存储键的副本，您通常可以通过使用CPTrie来节省一半的内存（参见下图）。 - 您需要一个集合而不是字典，并且您没有使用 .NET 4.0（它提供了有序集合集合）。如果您使用引用类型作为
CPTrie的值类型，那么每次使用null作为键的值时，CPTrie都会节省至少 4 字节的内存。这使得CPTrie能够非常紧凑地存储集合。 - 您想存储一个高度集中的整数集合，也就是说，有很长的几乎连续的整数运行，例如 1、2、3、4、5、7、8、9、97、98、99、101、102、104 等。
CPIntTrie可以使用CPBitArrayLeaf节点高效地存储大型集群，特别是如果整数不需要关联任何值。
字符串存储的性能
我比较了 CPStringTrie 与 Dictionary 和 SortedDictionary 对三个数据集的性能：
- 来自 12dicts 的英语单词列表。
- 一个包含 200,000 个字符串的集合。每个键都是通过将两个随机英语单词与空格连接而成。
- 一个包含 1,000,000 个字符串的集合。每个键都是通过将 31 个前缀之一与一个随机英语单词连接而成，中间有一个空格。在第二次测试中，我期望
CPTrie从相对较少的前缀中获得一些好处（在速度和空间方面）。
您可以在本文开头屏幕截图的基准测试的前两行中看到第一个数据集的结果（或者，自己运行基准测试 - 确保使用 Release 版本）。第一行使用普通的非优化 CPTrie，而第二行（标记为“opt.”）显示了当 trie 被优化时的性能差异，但由于英语单词列表适合我的处理器 2 MB 缓存，所以差别不大。
速度
在首次发布此文章后，我意识到我对待 SortedDictionary 不够公平，因为我使用了默认的排序顺序。由于 CPStringTrie 按序数排序，因此 SortedDictionary 应该使用 StringComparer.Ordinal 比较器，以使比较公平。此更改使 SortedDictionary 的速度大约提高一倍，因此 CPStringTrie 对于项目数少于 200,000 的集合通常较慢，但对于非常大的集合仍然更快。
用于测量的计时器的分辨率为 10-15 毫秒，因此对第一个数据集的测试重复了 10 次以获得更准确的结果。对于较大的数据集，我只使用了 1 或 2 次重复，以使基准测试不会花费太长时间。
我只对插入和检索（“扫描”）的速度进行了基准测试。没有对枚举或删除进行基准测试。我怀疑 CPTrie 的枚举速度相对较慢，因为当您请求每个键的值时，它必须从 byte[] 转换为 string，而 Dictionary 和 StringDictionary 直接存储字符串。但是，我不认为删除会很慢。
对于后两个数据集，我进行了一系列测试来显示可变集合大小的影响。在每个数据集的第一个测试中，我将整个数据集（200,000 或 1,000,000 个项）存储在一个集合中。对于其他测试，我将数据集分割成大小为 1000、500、250 或更小的“部分”，并将每个部分放入自己的集合中。这旨在模拟管理大量数据但不是将所有数据存储在一个地方的常见应用程序——即，数据分布在许多集合中。
只有第一个数据集足够小，几乎可以放入典型的 2 MB L2 缓存。在所有其他情况下，我试图以一种会给处理器缓存带来压力的方式访问数据。在扫描键之前，它们的顺序被随机化，并且一次从每个集合中添加或检索一个键，这样缓存倾向于在检索每个键时是“冷的”。我以为这种访问模式对 CPTrie 相对友好，因为它尺寸紧凑，但这似乎无关紧要。
所以，这是结果：
这些图表显示（在我的工作站上），CPTrie 仅在集合非常大时才能胜过 StringDictionary。请注意，为了使 StringDictionary 成立，它必须使用序数排序顺序进行构造；默认排序顺序（我认为是不区分大小写且区分区域设置的）会将 StringDictionary 的速度减半。无论如何，StringDictionary 随着集合大小的增加而逐渐变慢，这很有道理，因为它使用 红黑树，每次插入或检索都需要 O(log N) 时间。
CPTrie 的插入性能更复杂。当集合为 64 个项而不是 32 个项时，插入速度突然变慢；我怀疑这是因为 trie 在超过其每节点 34 项的限制后被迫分裂成多个节点，而分裂过程有些昂贵。然而，性能从未变得更差；一个包含 200,000 个项目的集合的构造速度几乎与 1600 个包含 125 个项目的集合一样快。
CPTrie 似乎违背了我在学校学到的定律，即排序算法通常不能比 O(N log N) 更快。然而，理论上，我认为 trie 可以在 O(N * K) 时间内生成一个排序的数据集，其中 K 是（平均？）键长度，并且没有“log N”的惩罚。有没有学者能解释一下这种差异？
内存
如前所述，CPTrie 可以使用比标准集合少的内存，并且对于大型数据集尤其出色。
我在 32 位处理器上纯粹通过分析方式进行了内存测量。为了确定这些集合的内存使用量，我假设普通对象有 8 字节头，数组有 12 和 16 字节头（见此），4 字节对象对齐和标准对齐规则，然后检查了每个相关类以确定其内存需求。
对于 CPTrie，我编写了一个方法（CountMemoryUsage()）来计算确切的内存使用量；对于 Dictionary 和 SortedDictionary，我使用 Reflector 检查了实现细节以找出使用了多少内存，并编写了方法来计算内存使用量。如果您相信我的算术，SortedDictionary 的内存测量是精确的，而 Dictionary 只是近似值。Dictionary，与 List<T> 一样，使用数组，当它们扩大时，大小大约翻倍，这意味着 Dictionary 中 0% 到 50% 的条目是未使用的。无法询问 Dictionary 的当前容量，因此在我的计算中，我假设 25% 的条目是未使用的。
如果您使用的是 64 位进程，我认为 CPTrie 会相对更有优势，尽管所有类型的集合都会需要更多的内存。
因此，以下是与速度图表相对应的内存图。Trie 的测量结果针对的是非优化 trie。
这里有一个重要的“作弊”：键的内存消耗被加到了 Dictionary 和 SortedDictionary 的总内存使用量中，但没有计入 CPStringTrie。因此，虽然看起来 CPTrie 使用的内存更少，但前提是您在将键添加到 trie 后丢弃它们。如果您保留所有键以字符串形式（如基准测试确实做的那样），那么使用 CPStringTrie 就不会节省内存！
因此，考虑到关于键的规则，200,000 项的 CPStringTrie 可以比 Dictionary 少用 57% 的内存，假设每个键关联 4 字节的值。一百万项的 trie 效果更好，使用的内存少 67%。
我曾以为一百万项的 trie 会通过只有 31 个前缀来节省很多内存，但如果我使用随机单词对（图中未显示），与 Dictionary 相比，节省量仍然有健康的 65%。请注意，只有 41,238 个唯一单词，因此在一百万项的测试中仍然存在许多共同前缀。
如果您在构建完成后通过 Clone() 优化 trie，您可以节省比图表中显示的更多约 20% 的内存，并且如果您访问模式给处理器缓存带来压力，您的查询速度会快 10%（但如果您在优化后修改 trie，则会降低性能）。注意具有 64 个项目的集合的内存峰值——我相信这是因为大多数 32 项 trie 适合一个节点，而 64 项 trie 需要两个或更多节点，这不成比例地增加了开销。所有三种集合类型在每个集合中的项目很少时都需要更多内存（因为集合的总数非常多，每个集合都有一定的开销）。
请记住，在这些测试中，键是 ASCII。这有助于节省内存，因为 CPStringTrie 使用 UTF-8，而普通 UTF-16 字符串每个字符使用两个字节。但是，如果您主要存储非 ASCII 字符串，例如中文，CPStringTrie 将需要显著更多的内存（我相信一个典型的中文字符在 UTF-8 中使用 3 个字节，而在 UTF-16 中使用 2 个字节）。
CPIntTrie
我编写了一个单独的类 CPIntTrie<TValue>，用于存储从 8 位到 64 位的所有大小的整数，有符号或无符号。它包含添加各种大小整数的重载方法，并实现了两个字典接口：IDictionary<int, TValue> 和 IDictionary<long, TValue>，这应该能满足大多数用例。
为了在 CPSNode 中高效存储数据，CPIntTrie 将每个键编码为以下三种格式之一的字节：
- 3 字节格式，用于 24 位整数，范围在 -0x10000 到 0xFAFFFF 之间
- 6 字节格式，用于 41 位整数，范围在 -0xFFFFFFFFFF 到 0xFFFFFFFFFF 之间
- 9 字节格式，用于大型有符号和无符号整数
使用 3 字节的倍数来存储数字在 CPSNode 中是有意义的，因为每个节点有 3 个字节。在大集合中，只要保持排序顺序，编码方法就无关紧要，但在小集合中，这种编码尽可能紧凑。
为了保持排序顺序，所有 6 字节的负整数都需要出现在“小于”3 字节的整数之前，而所有 6 字节的正整数都需要出现在“大于”3 字节的整数之后。同样，9 字节的负整数需要最小，而 9 字节的正整数需要最大。因此，键以一种 大端序格式存储，前面有一个表示大小和长度的前缀字节。
- 0x00：9 字节的 64 位有符号整数，小于 -0xFFFFFFFFFF
- 0x01：6 字节的 41 位有符号整数，介于 -0xFFFFFFFFFF 和 -0x10000 之间
- 0x02-0xFD：3 字节的 24 位整数，介于 -0x10000 和 0xFAFFFF 之间；从该字节减去 3 可计算 24 位数字的第一个字节
- 0xFE：6 字节的 40 位无符号整数，介于 0xFB0000 和 0xFFFFFFFFFF 之间
- 0xFF：9 字节的 64 位无符号整数，大于 0xFFFFFFFFFF
原始数据类型未编码：“byte”100 和“int”100 的存储方式相同。虽然在一个集合中同时使用有符号和无符号的 64 位整数会非常罕见，但 CPTrie 允许这样做。因此，没有一个基本数据类型可以表示所有可能的键。
整数存储的性能
对于整数基准测试，我采取了与字符串基准测试不同的方法。在字符串基准测试中，我检查了 trie 的性能如何受集合大小的影响，通过重复测试并使用不同大小的“部分”划分键。我简化了整数基准测试，只测试一次大型集合，但我使用了各种键分布，认为这可能会影响 trie 的性能和空间消耗。
速度
执行摘要：CPIntTrie 通常比 SortedDictionary 慢。但是，如果键非常密集地集中，CPIntTrie 的速度更快且体积小得多。CPIntTrie 也是非常大型集合的不错选择。但是，与之前一样，Dictionary 比任何排序集合都快得多。
我进行了涉及 24 位、32 位和 64 位键的测试。我尝试了三种键分布：
- 随机：均匀分布。
- 指数：在 32 位模式下，选择一个随机数，其位数介于 15 和 32 之间，使得高位为零；这应该近似于在对数尺度上选择一个随机点。在 64 位模式下，将一个随机的 32 位数字左移最多 32 位。
- 密集：集群是彼此接近的整数组。但有多近？“密集”数据的想法有无数种变体。在我的测试中，我使用参数
(C, S, D, start)构建了随机密集键集，其中C是每个集群中的最大整数数（最小为C/2），S是集群之间的最大间隔（最小为S/2），D是集群中相邻整数之间的最大距离（最小为 1），start是系列中的第一个整数（对于 64 位集群，start设置为0x0123456789ABCDEF，对于 32 位集群，设置为0x1000000）。我在测试中为C、S和D选择了一些任意值。
数据库的 ID 列通常会出现密集数据。每个新行都会获得比上一行多一个的 ID，但随着时间的推移，一些行或相邻的行系列会被删除，在整数空间中留下小的或大的间隙。CPIntTrie 可以非常紧凑地存储这类集合。密集数据也来自各种其他来源，例如直方图。
当然，键的分布对 Dictionary 或 SortedDictionary 的性能几乎没有影响。事实证明，CPIntTrie 通常也不会受到键分布的显著影响，只是 CPIntTrie 处理密集数据更快，并且在存储集合（null 值）而不是字典时更快。
这是我机器上的一些原始数据：
|-Int Dictionary--| |-SortedDictionary-| |----CPIntTrie----|
Scenario Reps Set size Fill Scan Memory Fill Scan Memory Fill Scan Memory
-------- ---- -------- ---- ---- ------ ---- ---- ------ ---- ---- ------
1-100,000, sorted 10 100000 15ms 12ms 2.5M 128ms 58ms 2.7M 63ms 46ms 0.9M
1-100,000, random 10 100000 15ms 4ms 2.5M 132ms 62ms 2.7M 58ms 44ms 0.9M
1-100,000 w/ null vals 10 100000 15ms 6ms 2.5M 129ms 58ms 2.7M 47ms 43ms 0.0M
24-bit keys with 100K items:
Random 24-bit ints 10 100000 19ms 9ms 2.5M 134ms 66ms 2.7M 157ms 65ms 2.0M
Random set (null vals.) 10 100000 18ms 13ms 2.5M 134ms 62ms 2.7M 117ms 63ms 1.3M
Clusters(20, 100,2) 10 100000 15ms 9ms 2.5M 134ms 66ms 2.7M 101ms 60ms 2.2M
Clusters(same w/ nulls) 10 100000 18ms 9ms 2.5M 135ms 63ms 2.7M 81ms 46ms 0.2M
Clusters(20, 100,9) 10 100000 16ms 9ms 2.5M 131ms 60ms 2.7M 134ms 65ms 2.3M
Clusters(20,1000,2) 10 100000 21ms 9ms 2.5M 131ms 63ms 2.7M 126ms 70ms 1.4M
Clusters(20,1000,9) 10 100000 15ms 12ms 2.5M 132ms 55ms 2.7M 129ms 74ms 1.4M
Clusters(50, 100,2) 10 100000 15ms 10ms 2.5M 129ms 60ms 2.7M 84ms 47ms 1.6M
Clusters(50, 100,9) 10 100000 21ms 12ms 2.5M 132ms 58ms 2.7M 128ms 52ms 3.1M
Clusters(50,1000,2) 10 100000 15ms 12ms 2.5M 131ms 62ms 2.7M 137ms 62ms 1.7M
Clusters(50,1000,9) 10 100000 16ms 10ms 2.5M 128ms 58ms 2.7M 143ms 70ms 2.2M
Tests with 32-bit keys:
Random 32-bit ints 10 100000 23ms 16ms 2.5M 154ms 58ms 2.7M 175ms 96ms 2.0M
Random 32-bit ints 5 200000 49ms 43ms 5.1M 315ms 165ms 5.3M 468ms 237ms 5.1M
Random 32-bit ints 3 500000 135ms 130ms 12.7M 1051ms 530ms 13.4M 1291ms 614ms 8.5M
Random 32-bit ints 2 1000000 335ms 281ms 25.4M 2593ms 1257ms 26.7M 2390ms 1328ms 13.3M
Exponential 32-bit 10 100000 21ms 13ms 2.5M 134ms 62ms 2.7M 185ms 88ms 1.9M
Exponential 32-bit 5 200000 49ms 49ms 5.1M 321ms 162ms 5.3M 390ms 218ms 3.8M
Exponential 32-bit 3 500000 140ms 135ms 12.7M 1056ms 525ms 13.4M 1234ms 567ms 9.1M
Exponential 32-bit 2 1000000 335ms 288ms 25.4M 2671ms 1218ms 26.7M 2601ms 1218ms 17.8M
Clusters(25,25,1) 10 100000 15ms 0ms 2.5M 129ms 62ms 2.7M 81ms 62ms 1.5M
Clusters(25,30000,5) 10 100000 16ms 10ms 2.5M 134ms 60ms 2.7M 155ms 93ms 1.3M
Clusters(50,50000,5) 10 100000 16ms 12ms 2.5M 134ms 60ms 2.7M 180ms 90ms 2.0M
Clusters(75,90000,5) 10 100000 19ms 9ms 2.5M 129ms 60ms 2.7M 169ms 82ms 2.1M
Clusters(75,90000,5) 5 200000 40ms 40ms 5.1M 318ms 165ms 5.3M 368ms 205ms 4.3M
Clusters(75,90000,5) 3 500000 130ms 130ms 12.7M 1031ms 530ms 13.4M 1202ms 577ms 10.6M
Clusters(75,90000,5) 2 1000000 320ms 296ms 25.4M 2624ms 1241ms 26.7M 2562ms 1234ms 21.3M
Clusters(75,90000,5) 1 2000000 687ms 593ms 50.9M 6671ms 2796ms 53.4M 5265ms 2656ms 42.7M
Clusters(99,90000,2) 1 2000000 703ms 578ms 50.9M 6640ms 2796ms 53.4M 5328ms 3062ms 28.1M
Tests with 64-bit keys:
Clusters(25,50000,9) 10 100000 23ms 15ms 3.1M 151ms 71ms 3.1M 177ms 97ms 1.4M
Clusters(50,20000,5) 10 100000 23ms 15ms 3.1M 148ms 68ms 3.1M 179ms 91ms 2.0M
Clusters(75,1000,3) 10 100000 19ms 13ms 3.1M 144ms 71ms 3.1M 156ms 70ms 1.8M
Random 32-bit longs 10 100000 26ms 15ms 3.1M 149ms 71ms 3.1M 179ms 96ms 2.0M
Random 40-bit longs 10 100000 24ms 15ms 3.1M 174ms 78ms 3.1M 190ms 93ms 2.5M
Random 64-bit longs 10 100000 26ms 15ms 3.1M 148ms 68ms 3.1M 201ms 94ms 3.1M
Random set (null vals.) 10 100000 27ms 16ms 3.1M 144ms 71ms 3.1M 187ms 90ms 2.3M
Exponential longs 10 100000 26ms 15ms 3.1M 154ms 74ms 3.1M 210ms 112ms 2.3M
Exponential longs 5 200000 55ms 46ms 6.1M 365ms 187ms 6.1M 534ms 246ms 4.7M
Exponential longs 3 500000 156ms 135ms 15.3M 1296ms 567ms 15.3M 1406ms 697ms 11.4M
Exponential longs 2 1000000 343ms 296ms 30.5M 3218ms 1452ms 30.5M 3343ms 1531ms 22.3M
我只绘制了这些结果的 32 位部分的图表。
请注意，此图表未显示所有值为 null 的情况，这些情况速度更快，但您可以看到密集集群 (25,25,1) 比 SortedDictionary 快。
内存
与 CPStringTrie 相比，CPIntTrie 的内存节省不那么显著，但仍然很明显。下面的图表显示了 CPIntTrie 如何处理各种分布和大小的 32 位整数。
图表未显示任何 null 值的情况。如果您查看原始数据，您会发现，在所有值都设置为 null 的情况下（例如，“1-100,000 w/ null values”），所需的内存可能大大减少，特别是如果数据是密集集中的。在这种情况下，trie 在包含密集键簇的整数空间区域中更像一个位数组。在最好的情况下，每个键需要不到 4 位，因此四舍五入到最近的 0.1 MB 后总计为 0.0 MB。您可以选择是否逐个键使用值，但为了获得如此显著的内存节省，大部分数字空间只能使用 null 值。
奇怪的是，200K 随机整数内存使用量出现了一个峰值。我不确定这是为什么，但我怀疑键密度是问题所在。CPTrie 在键稀疏（使用 CPSNode）或密集（使用 CPBitArrayLeaf）时效率很高，但在某些密度下，它必须使用 CPBNode，并且由于数据是随机的，每个 CPBNode 需要 8 个 CPSNode，这会增加大量开销。
另一方面，一百万个随机数以及某些类型的密集数据的内存使用量有所下降。在一百万个随机整数的情况下，我只能假设这种键密度是一个甜蜜点，即使它不够密集而无法使用 CPBitArrayLeaf。集群 (25,25,1) 和 (99,90000,2) 可能受益于 CPBitArrayLeaf，而集群 (25,30000,5) 可能有效地利用了 CPSNode 叶节点。
结束
希望您喜欢阅读我的新数据结构。如果您找到实际应用，请告诉我！
历史
- 2010 年 3 月 30 日：添加了
CPIntTrie（和CPBitArrayLeaf），附带基准测试和测试。 - 2010 年 2 月 26 日：初始发布，包含
CPStringTrie和CPByteTrie。