我正在解决具有以下要求的竞争性编程问题:
我必须维护一个唯一的 2d 点列表 (x,y)，唯一点的数量将少于 500。
我的想法是将它们存储在一个哈希表中(特定于 C++ 无序集)，每次出现一个节点时，我都会查找该表，如果该节点不存在，我会插入它。
我也知道我不会进行超过 500 次查找。 所以我看到一些解决方案只是简单地搜索一个数组(未排序)并在插入之前检查节点是否已经存在。
我的问题是有什么合理的方法可以猜测我什么时候应该使用哈希表而不是手动搜索键而不用对它们进行基准测试？
最佳答案
My question is is there any reasonable way to guess when should i use a hash table over a manual search over keys without having to benchmark them?
我猜您熟悉基本算法 & time complexity和 C++ standard containers并且知道幸运的哈希表访问是 O(1)
如果哈希表代码(或一些平衡树代码，例如使用 std::map - 假设键上有一个简单的顺序)更具可读性，出于可读性原因我更喜欢它一个人。
否则，您可能会根据 approximate timing for various operations on a PC 做出一些猜测.顺便说一句，整个http:///norvig.com/21-days.html页面值得一读。
基本上，内存访问比 CPU 中的其他所有内容都慢得多。 CPU cache非常重要。需要从 DRAM 模块获取数据的具有缓存故障的典型内存访问比某些基本算术运算或机器指令(例如，在寄存器中添加两个整数)慢数百倍。
在实践中，这并不重要，只要您的数据很小(例如少于一千个元素)，因为在这种情况下它很可能位于二级缓存中。
在数组中搜索(线性)非常快(因为缓存非常友好)，最多可达数千个(小)元素。
IIRC，Herb Sutter在一些视频中提到，即使插入一个元素到 vector 中实际上比将它插入到一些平衡树(或可能是其他容器)中更快(但不直观)(考虑到移动切片所需的时间) ，例如哈希表)，最多包含几千个小元素的容器大小。这是典型的平板电脑、台式机或服务器微处理器，具有数兆字节的高速缓存。 YMMV.
如果您真的那么在意，就无法避免基准测试。
请注意，500 对整数可能适合 L1 缓存!
关于c++ - 决定何时使用哈希表，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/40102590/