c++ - 基数树 (Patricia Trie) 是一种高效的手机通讯录数据结构吗

Question

我一直在考虑用 C++ 实现地址簿。由于它是为移动应用程序开发的，地址簿应该使用尽可能少的内存，而且用户应该仍然能够按名称快速搜索或排序联系人(我知道的悖论)。

经过一番研究后，我发现大多数人建议 Trie将是最适合我需要的数据结构。更准确地说是 radix tree (帕特里夏·特里)。使用此数据结构也非常适合实现自动完成功能。

是否有其他可行的解决方案，或者如果我开始使用这个想法进行编码是否可以？

Answer 1

当心小集合的尝试。尽管它们确实提供了良好的渐近行为，但它们在时间和空间上的隐藏常数可能太大。

特别是，尝试往往具有较差的缓存性能，这应该是小型集合的主要问题。

假设您的数据相对较小 [<10,000 个条目]，std::vector 可以提供良好的缓存性能，这可能会比大小因素产生更大的影响。因此，即使它的搜索时间渐近地高于 trie 或 std::set，实际上 - 它可能比两者都更好，这要归功于良好的缓存行为。

如果您还可以使用 binary search 维护 vector 排序- 您可以同时受益于对数搜索时间和良好的缓存行为。

(*)此答案假定将部署应用程序的硬件具有 CPU-Cache .