我必须实现给定固定长度的代码 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)。现在我已经尝试了谷歌的向量稀疏散列,我的问题是,你有什么建议吗?还有其他选择吗?有没有其他方法可以使用整数作为键来提高性能?我知道我不会有任何碰撞,因为每个键都会与其他键不同。
最好的问候,昆汀