4个版本
| 0.1.3 | 2022年10月5日 |
|---|---|
| 0.1.2 | 2022年9月28日 |
| 0.1.1 | 2022年9月27日 |
| 0.1.0 | 2022年9月27日 |
#795 in 数据结构
31KB
229 行
字级并行性
在开发如x-fast trie等专用整数数据结构时有用的位级算法
概述
算术和逻辑运算在所有实际目的上都是常数时间。这些操作在整个字上操作。（字是单个内存段的大小。这个crate，假设字大小为64。有关计算机内存的更深入讨论，请参阅此笔记）。例如，将两个64位数字相加需要常数时间。
这个库中算法背后的中心思想是这样的
- 如果你有一堆小整数——每个都小于64位，例如一些字节，我们可以将许多它们打包到一个单个的64位整数中。
- 然后我们可以将这个打包的整数作为一个单一的数字来操作。例如，我们可以将8个字节大小的数字放入一个单词中。
- 通过在打包的整数上操作，我们实际上在并行地操作8个不同的整数。
这就是所谓的world level parallelism。
算法
实现的算法包括
查找整数的top(k)位
第一个过程非常简单。目标是，给定一个数字x和长度k，以O(1)提取x的前k位。执行此操作的程序在实现x-fast trie时将非常有用。
SardineCan结构
假设我们希望在B-Tree中维护一组小型整数。并且假设我们还想利用这样一个事实，即我们可以将这些整数中的许多放入一个更大的整数中。我们如何设计这样的B-Tree的单个节点呢？
请记住，一个阶为 b 的B树是一种多路搜索树，其中每个节点都是一个必须包含在 b - 1 和 2b - 1 个键之间的桶。此外，每个节点比它包含的键的数量多一个子节点。也就是说，每个节点必须有 b 到 2b 个子节点。B树上的操作依赖于一个键操作：node.rank(x)。这个操作通过单个节点（已排序）的键进行搜索，要么返回 x 在节点中的位置，要么返回我们需要下降到以完成当前操作的子节点的索引。在普通的B树中，node.rank(x) 是使用二分搜索实现的，因此它需要 O(lg b) 的时间。然而，如果我们的键是小的整数，我们可以在 O(1) 时间内执行 node.rank(x)。
SardineCan 实现了一个专门用于存储小整数的B树节点。
O(1) 最高有效位：四个俄罗斯人MSB
当我们谈论一个数的最高有效位时，我们通常指的是最高位设置的位置的0索引。请注意，这比简单地找到只有 msb 被设置的数的数更一般。例如，MSB(010010001) 是 7 而不是 128。
找到这个索引的最简单方法是通过对要求数的位进行线性扫描，同时保持到目前为止看到的位数。这个方案运行在 O(lg n) 的时间复杂度，其中 n 是我们的函数可能操作的最大的数。
/// A procedure for finding the index of the most significant
/// bit in time linear to the number of bits used
/// to represent the value.
fn get_msb_idx_of(query: u64) -> u8 {
for i in (0..64).rev() {
if query & (1 << i) != 0 {
return i;
}
}
panic!("MSB(0) is undefined")
}
我们可以使用位级二分搜索改进线性扫描程序。这可以将运行时间降低到 O(lg lg n)。然而，当我们知道我们将执行许多 msb 查询时，我们使用查找表来计算这个值。使用这种方法，我们能够在常数 O(1) 时间内找到最高位设置的位置，尽管这需要额外的预处理步骤来构建查找表。
我们可以使用位级并行性，在常数时间内找到最高有效位的索引，而不使用查找表。