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

我正在寻找一种能够非常快速搜索的二进制数据结构（树，列表）。我只会在程序的开始/结束时一次性添加/删除项目。所以它会是固定大小的，因此我并不关心插入/删除速度。基本上我正在寻找的是一种提供快速搜索并且不占用太多内存的结构。用于快速搜索的二进制数据结构

由于

数据的性质是什么？它可以排序吗？它的大小是多少？内存约束是什么？ – Haspemulator

关键类型是什么？ – Nim

Haspemulator，它大约有五个指针，我猜它可以被排序，因为每一块数据都有一个唯一的指针。它会有很多节点，平均大概在50个左右。 – slartibartfast

查找Boost C++库here中的无序集。与用于搜索的O（log n）红黑树不同，无序集合基于散列，并且平均为您提供O（1）搜索性能。

2011-08-15 15:21:07

一个有效（尽管蝇头有点混乱）算法是Red-Black tree。

内部，C++标准库使用红黑树来实现std::map - 见this question

2011-08-15 15:16:29 Nate

的std::map和哈希表都是不错的选择。他们也有建设者来缓解一次性建设。

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

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

2011-08-15 15:19:46

一个不容忽视的容器是一个已排序的std :: vector。

它绝对赢得内存消耗，特别是如果您可以预先准备（）正确的数量。

2011-08-15 15:34:49

+1。使用'lower_bound'在已排序的向量中查找元素实质上模拟了'set'的搜索行为，但“向量”的内存效率要高得多，因此查找也可能会更快，因为内存局部性。 –

只要确保执行二进制搜索以查找数据，并且如果不需要在运行时更改小数据集（50个），那么这是一个很好的答案。 –

因此，关键可以是一个简单的类型，值是一个小指针结构的五个指针。

只有50个元素开始变得足够小，以至于Big-O理论性能可能被算法或结构的固定时间开销所影响或至少可测量。

例如，一个具有线性搜索的矢量阵列由于其结构简单且内存紧张而通常以最少的十个元素最快。

我会包装容器并在其上运行实时数据。开始用STL的载体，以进入标准STL地图，升级到unordered_map，甚至尝试谷歌的密集或sparse_hash_map： http://google-sparsehash.googlecode.com/svn/trunk/doc/performance.html

2011-08-15 15:56:12 MattiasF

最快的往往是TREI /线索。我比std :: unordered_map实现了一个3到15倍的速度，他们倾向于使用更多的RAM，除非你使用了大量的元素。

2014-03-29 19:16:30 Exaeta

回答