1

我必须实现给定固定长度的代码 Trie。每个代码都是一个整数序列，考虑到某些模式是常见的，我决定实现一个 Trie 来存储所有代码。鉴于它们的字典顺序，我还需要遍历代码，并且我期望使用数百万（可能是数十亿）的代码。

这就是为什么我考虑将这个特定的 Trie 实现为字典，其中每个键都是给定前缀的索引。假设键 0 有一个他的前缀子项列表，对于每个子项，我将相应的条目保存在字典中...示例：如果我的第一个插入是代码 231，那么字典将如下所示：

[0]->{(2,1)}
[1]->{(3,2)}
[2]->{(1,3)}

这样，如果我的第二次插入是 243，则字典将以这种方式更新：

[0]->{(2,1)}
[1]->{(3,2),(4,3)} *Here each list is sorted using a flat_map
[2]->{(1,endMark)}
[3]->{(3,endMark)}

我的问题是我一直在为这个目的使用向量，并且因为将所有字典都保存在 contiguos 内存中可以让我在迭代它时获得更好的性能。现在，当我需要处理问题的 BIG 实例时，由于调整向量的大小，我无法处理数百万个代码（内存消耗可能高达 200GB）。现在我已经尝试了谷歌的向量稀疏散列，我的问题是，你有什么建议吗？还有其他选择吗？有没有其他方法可以使用整数作为键来提高性能？我知道我不会有任何碰撞，因为每个键都会与其他键不同。

最好的问候，昆汀

4

0 回答 0