c++ - 字素生成 - 时间与内存复杂度

Question

我正在编写一个程序来从文本文件生成“multimap ”数据，这些数据基本上是字素与其在文本文件中出现频率之间的映射，例如:

aaaa : 0
aaab : 0
aaac : 0
...
thel : 10
them : 250
...
zzzz : 0

基本思想是，您可以根据 multimap 数据对字符串“评分”，以测试它与文本文件语言的相似程度。评分功能必须非常快。因此，我希望通过n维数组来实现对数据的直接访问。例如:

data[n('t')][n('h')][n('e')][n('m')]

其中 n(char) 是一个对字符进行归一化的函数，例如 a -> 0、b -> 1、c -> 2 等等。无论如何，问题就在这里:26^n 变大，非常快!如果我每个元素使用 4 个字节，则不同的 n 值需要以下内存:

1. 104乙
2. 3 KB
3. 69 KB
4. 2MB
5. 45MB
6. 1GB
7. 30GB
8. 778GB

所以看起来当n > 3 时，栈内存不足，而当n > 6 时，大多数堆内存不足。理想情况下，我希望能够生成任何合理长度的 multimap 文件——最多 10 个左右。有什么想法可以实现吗？

我考虑过对数组的每个元素使用少于一个字节的可能性。我真的只需要索引 'a-z' 和一些特殊字符(空格，标点符号)，所以可能可以使用 5 位(0 - 31)。这可能吗？如果可以的话，我可能会节省 38% 的内存。您认为这会如何影响时间复杂度？

一种选择是使用散列函数而不是数组。这意味着我只在实际存在的键上使用内存，而不是频率始终为 0 的“qxzf”。内存需求会大大减少，但我担心时间复杂度会受到严重影响。你怎么看？

也许我可以使用某种树数据结构？字素适合这种表示，但同样，时间复杂度肯定会受到影响。我认为访问数据需要“n”步，而不是 1 步。

最后，我正在考虑对评分函数进行多线程处理。我宁愿不为每个线程分配数据拷贝。您认为可以将一两点与 Peterson 的算法结合使用来锁定元素吗？

提前致谢。

Answer 1

Trie 提供了良好的时空权衡。一个普通的 trie ，其中每个节点(例如前缀“iq”)都有一个子指针数组，由字符串中的下一个字符(例如'x')索引，仍然会在子节点中以空值的形式浪费空间指针数组，但您将节省空间，因为没有以该前缀为根的分支(例如“iqx”)。其他尝试通过仅存储指向存在的 child 的指针来减少空间量但增加时间复杂度(尽管不一定很多)，这需要搜索 child 指针，通常以 child 数量的对数时间。后一种类型的一些尝试将给定前缀的所有指针存储在单个节点中；其他(例如 ternary search tries )使用多个节点。

通过尝试进行查找的时间复杂度为 O(n)，但由于 n 相当小，因此实际性能可能足够快以满足您的需求。根据您的计数方式，多维数组访问本身就是 O(n)，因为查找 n 个字符的键涉及评估具有 n 个项的多项式( data[a<sub>1</sub>]...[a<sub>n</sub>] == data + sum(i=1..n, a<sub>i</sub> * 256<sup>i-1</sup>) ).

如果空间要求仍然太高，即使对于虚拟内存，那么您需要将大部分结构存储在磁盘上，例如 B+ trees allow。在这种情况下，B+ 树将提供哈希表的底层实现。这当然会造成相当大的性能损失，但一旦内存需求达到一定水平，这是不可避免的。

I thought about the possibility of using less than one byte to index each dimension of the array.

完全有可能以这种方式减少潜在数组索引的数量。除了使用专门的数据结构之外，您还可以这样做。例如，这将减少 trie 中节点的扇出，从而减少空指针的数量。

您需要一个将字符映射到数组键的函数，这只会稍微增加时间复杂度。使用表查找将导致较低的恒定时间增加和较小的空间增加(~256 字节)。

你可能还需要对样本数据和待测字符串进行预处理，过滤掉/映射无效字符(比如大写转小写)，时间复杂度与字符串长度成线性关系.

Finally, I'm considering multi-threading the scoring function.

此处的 yield 取决于评分函数的计算有多少花费在读取字素结构之外。如果在这之外花费的时间很少，那么线程将花费大部分时间等待，并且您不会看到太多性能改进。 Amdahl's law 适用于此。

根据您的评论，多线程评分函数可能不需要锁来进行只读访问。只要只读访问不改变结构本身，遍历结构的所有状态都完全包含在读取函数中，读取函数调用的任何函数(例如哈希函数)都是线程安全的并且整个结构适合可用内存，那么如果多个线程同时从树中读取，就不会有冲突。

如果您使用磁盘支持的方法(例如使用 B+ 树)，则最后一个要求将不成立。在这种情况下，您可能需要锁定处理磁盘 block 的代码以防止抖动。