树或其他数据结构最有效地查找“最近的搜索”
树或其他数据结构最有效地查找“最近的搜索”
提问于 2014-05-23 12:35:25
我以为我现在正在寻找的东西有一种树算法，但我忘了它的名字，谷歌也没有帮上忙。
我正在寻找一种算法，它对数据具有最佳的查找性能。特征：-每次查找都会很成功。因此，所有查找的键都存在(可能有一些遗漏，但这些键将被视为“错误配置”，这种丢失的发生可以忽略不计)--很有可能(为此优化了数据集)随后也会出现相同的查找--例如，键123可能有一百万次查找，在之间可能有一个键456的单一查找，然后再对123进行数百万次查找。然后，查找可能具有相同键的下一组，以此类推。
当然我可以用哈希算法。但是，为了达到给定的目的，我记得有一个搜索优化树，它以这样的方式优化查找，以至于最近的查找都位于树的最顶端。因此，可能会有树的第一个节点直接命中O(1)，而不需要哈希函数或散列存储模块。
我正在寻找这个算法来实现移动设备上图形渲染的原始性能。
回答 2
Stack Overflow用户
回答已采纳
发布于 2014-05-23 12:44:54
也许是splay tree。
显示树是一种自调整的二进制搜索树，它具有最近访问的元素可以快速再次访问的附加属性。
但是哈希表应该是O(1)，所以您不应该期望一个表的性能明显优于另一个哈希表。
Stack Overflow用户
发布于 2014-05-23 13:08:50
我建议对这项工作使用哈希表。为了加快后续的搜索速度，您可以在数组中缓存最近访问的K元素。如果K很小(< 20左右)，则该数组中的线性搜索将非常快，因为它可以停留在L1缓存中。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/23829440
复制相关文章
相似问题
腾讯云开发者
