0

I am trying to figure out the best data structure to use for this problem. I am implementing a key value store with keys that are strings. The values get added frequently and will generally only get looked up 1 or 2 times. Initially I used an std::map, but I found the performance to be unoptimal, as the overhead of adding keys and rebalancing the red-black tree, overshadowed the decrease in time to search for a value. Currently I am using a modified single linked list. It uses a struct that contains a c string (const char *), the length in bytes, and the value stored. When I want to find a value using a key I iterate through the list and compare the size of the keys, if they match I use memcmp to check if the strings are identical. If they are identical, I return the value. I way able to achieve about 10x greater performance using this method over the std::map. I need to make it about 2x more efficient, however. Can anyone recommend a better type of data structure, for this problem?

4

4 回答 4

3

std::vector应该比链表更快地迭代并且也更快push_back()，因为大多数时候不需要内存分配。

于 2011-02-10T18:35:20.647 回答
3

如果不了解实际问题，很难找到快速的解决方案。特别是，您的数据集有多大，真实数据存储在哪里（是存储在容器中还是其他地方？）。您还需要对容器执行哪些其他操作？你需要从容器中删除元素吗？

作为对您声明需要复制密钥的其他问题之一的评论std::unordered_map......如果密钥已经存储在其他地方，我建议您使用地图，但避免复制字符串。使用指针作为键，并使用自定义比较器来取消引用并在结果中进行操作：

// Assuming that the data is stored in std::string somewhere else
struct custom_compare {
   bool operator()( std::string* lhs, std::string* rhs ) const {
      return lhs!=rhs && (lhs->size() < rhs->size() || lhs->compare( *rhs ) < 0);
   }
};
std::map< std::string*, data, custom_compare > mymap;

通过存储指针而不是实际的字符串，这将消除复制。自定义比较器基本上与您在列表中实现的比较器一样快，并且树将平衡内容，允许 O(log n) 查找。根据集合的大小（如果有很多元素），这将是对线性搜索的改进，而如果大小很小，那么线性搜索会更好。

此外，根据数据的多样性，您可能希望遵循线性搜索，但根据一些快速计算的标准划分搜索空间，同时尽可能均匀地划分集合。例如，您可以使用线性搜索，但不是保留单个列表，而是根据键长度保留不同的列表。

如果标准实际上是基于字符串的内容（字母，而不是大小），那么您正在逼近 trie 的定义。如果你得到一个已经实现的库，或者你愿意花时间这样做，那么 trie 可能是这种查找最快的容器之一，因为它将“大小”变量从数量元素到字符串的长度。

于 2011-02-10T19:24:26.713 回答
2

你有它作为你的标签之一......为什么不使用Trie？插入应该很快，由于字符重叠，内存使用率会下降，并且查找速度很快。

于 2011-02-10T18:39:12.527 回答
0

也许某种哈希表？为您的密钥使用良好的散列算法将大大加快您的搜索时间。您的插入时间会稍微变慢，但如果您的散列函数很好，希望不会很大。

于 2011-02-10T18:30:56.250 回答