logo标签列表

用于快速搜索的二进制数据结构

c++linked-listhashtablebinary-tree
3
我正在寻找一种二进制数据结构（树、列表）以实现非常快速的搜索。我只会在程序的开头/结尾添加/删除所有项目。因此，它将是固定大小的，因此我并不真正关心插入/删除的速度。基本上我需要的是一种提供快速搜索且并不使用太多内存的结构。
谢谢。
你的数据的性质是什么？它是否可以排序？它的大小是多少，记忆限制有什么？ - Haspemulator
Hasp模拟器，大约有五个指针，我猜它可以排序，因为每个数据片段都有一个唯一的指针。它将有许多节点，平均可能约50个。 - slartibartfast
@myrkos，所以你需要搜索50个整数，还是搜索包含5个指针的结构体的50个实例？ - Haspemulator
6个回答
6

在Boost C++库中查找无序集合，请点击这里。与红黑树的O(log n)搜索相比，无序集合基于哈希，平均而言提供了O(1)的搜索性能。

4

有一个容器不容忽视，那就是排序过的std::vector。

它在内存消耗方面绝对占优势，特别是如果你能提前使用reserve()函数正确地预留出足够的空间。

使用 lower_bound 在已排序的向量中查找元素本质上模拟了 set 的搜索行为，但是 vector 更加内存高效，因此由于内存局部性，查找可能会更快。 - Kerrek SB
确保使用二分查找来查找数据，如果你不需要在运行时更改数据且数据集较小（大约50个数据），则这是一个很好的答案。 - Mooing Duck
2

因此，键可以是简单类型，而值是由五个指针组成的较小结构。

当元素数量仅有50个时，由于算法或结构的固定时间开销，大O理论性能可能会变得相对较小或至少可测量受到影响。

例如，一个具有线性搜索的数组向量通常是最快的，因为它具有简单的结构和紧凑的内存，适用于少于十个元素的情况。

我建议封装容器并在其上运行实际数据进行计时。从STL的vector开始，继续使用标准STL map，升级到unordered_map，甚至尝试Google的dense或sparse_hash_map： http://google-sparsehash.googlecode.com/svn/trunk/doc/performance.html

0

最快的数据结构往往是trie/前缀树。我实现了一个比std::unordered_map快3到15倍的trie，但它们倾向于使用更多的内存，除非你使用大量元素。

0

一种高效（尽管有点令人困惑）的算法是红黑树。

在内部，C++标准库使用红黑树来实现std::map - 参见这个问题

0

std::map 和哈希映射是不错的选择。它们也有构造函数以简化一次性构建。

哈希映射将键数据放入返回数组索引的函数中。这可能比std::map慢，但只有分析才能说明。

我的偏好是std::map，因为它通常实现为一种二叉树类型。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接