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

Question

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

经过一番研究后，我发现大多数人认为Trie将是满足我需求的最佳数据结构。更准确地说是基数树（Patricia Trie）。使用这种数据结构也可以很好地实现自动完成。

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

Answer 1

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

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

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

如果您还可以使用二进制搜索vector来维护排序- 您可以从对数搜索时间和良好的缓存行为中受益。

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

Answer 2

尝试是最好的，因为它们提供快速搜索、插入和删除。