决定何时使用哈希 table
Deciding when to use a hash table
我正在解决具有以下要求的竞争性编程问题：
我必须维护一个唯一的 2d 点列表 (x,y)，唯一点的数量将少于 500。
我的想法是将它们存储在散列 table 中（C++ 无序集是特定的），每次出现一个节点时，我都会查找 table，如果该节点还没有我会插入它。
我也知道 我不会进行超过 500 次查找。
所以我看到一些解决方案只是简单地搜索一个数组（未排序）并在插入之前检查节点是否已经存在。
我的问题是有什么合理的方法可以猜测我什么时候应该使用散列 table 而不是手动搜索键而不必对它们进行基准测试？
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 and C++ standard containers 并且知道运气好哈希 table 访问是 O(1)
如果散列 table 代码（或一些平衡树代码，例如使用 std::map - 假设键上有一个简单的顺序）更具可读性，出于可读性原因我更喜欢它一个人。
否则，考虑到 approximate timing for various operations on a PC. BTW, the entire http:///norvig.com/21-days.html 页面值得一读，您可能会做出一些猜测。
基本上，内存访问比 CPU 中的其他所有内容都慢得多。 CPU cache 非常重要。需要从 DRAM 模块获取数据的缓存故障的典型内存访问比某些基本算术运算或机器指令（例如，在寄存器中添加两个整数）慢数百倍。
实际上，只要您的数据很小（例如少于一千个元素），这并不重要，因为在那种情况下它很可能位于二级缓存中。
在数组中搜索（线性）非常快（因为缓存非常友好），最多可达数千个（小）元素。
IIRC，Herb Sutter 在一些视频中提到甚至 插入 向量中的元素实际上 - 但不直观地 - 更快（考虑到移动所需的时间切片）而不是将其插入到一些平衡树（或者可能是其他容器，例如哈希 table），最多包含几千个小元素的容器大小。这是典型的 tablet、台式机或服务器微处理器，具有数兆字节缓存。 YMMV.
如果您真的那么在乎，就无法避免基准测试。
请注意，500 对整数可能适合 L1 缓存！
您可以使用 Big O Complexity 来粗略估计性能。对于Hash Table，最坏情况下查找一个元素的时间复杂度在O(1)和O(n)之间。这意味着，在最好的情况下，您的访问时间与地图中的元素数量无关，但在最坏的情况下，它是线性的，取决于您的哈希大小 table.
二叉树的搜索复杂度保证为 O(nlog(n))。这意味着，搜索元素总是取决于数组的大小，但在最坏的情况下它比散列更快 table.
您可以在这个方便的网站上查找一些 Big O Complexities：http://bigocheatsheet.com/
我的经验法则是假设处理器每秒可以处理 10^9 次操作。
在您的例子中只有 500 个条目。最多为 O(N^2) 的算法可能是安全的。通过使用像 vector 这样的连续数据结构，您可以利用快速缓存命中。此外，哈希函数有时在常量方面可能会很昂贵。但是，如果您的数据大小为 10^6，则安全复杂度总共可能仅为 O(N)。在这种情况下，您可能需要考虑 O(1) hashmap 进行一次查找。
我正在解决具有以下要求的竞争性编程问题：
我必须维护一个唯一的 2d 点列表 (x,y)，唯一点的数量将少于 500。
我的想法是将它们存储在散列 table 中（C++ 无序集是特定的），每次出现一个节点时，我都会查找 table，如果该节点还没有我会插入它。
我也知道 我不会进行超过 500 次查找。 所以我看到一些解决方案只是简单地搜索一个数组（未排序）并在插入之前检查节点是否已经存在。
我的问题是有什么合理的方法可以猜测我什么时候应该使用散列 table 而不是手动搜索键而不必对它们进行基准测试？
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 and C++ standard containers 并且知道运气好哈希 table 访问是 O(1)
如果散列 table 代码（或一些平衡树代码，例如使用 std::map - 假设键上有一个简单的顺序）更具可读性，出于可读性原因我更喜欢它一个人。
否则，考虑到 approximate timing for various operations on a PC. BTW, the entire http:///norvig.com/21-days.html 页面值得一读，您可能会做出一些猜测。
基本上，内存访问比 CPU 中的其他所有内容都慢得多。 CPU cache 非常重要。需要从 DRAM 模块获取数据的缓存故障的典型内存访问比某些基本算术运算或机器指令（例如，在寄存器中添加两个整数）慢数百倍。
实际上，只要您的数据很小（例如少于一千个元素），这并不重要，因为在那种情况下它很可能位于二级缓存中。
在数组中搜索（线性）非常快（因为缓存非常友好），最多可达数千个（小）元素。
IIRC，Herb Sutter 在一些视频中提到甚至 插入 向量中的元素实际上 - 但不直观地 - 更快（考虑到移动所需的时间切片）而不是将其插入到一些平衡树（或者可能是其他容器，例如哈希 table），最多包含几千个小元素的容器大小。这是典型的 tablet、台式机或服务器微处理器，具有数兆字节缓存。 YMMV.
如果您真的那么在乎，就无法避免基准测试。
请注意，500 对整数可能适合 L1 缓存！
您可以使用 Big O Complexity 来粗略估计性能。对于Hash Table，最坏情况下查找一个元素的时间复杂度在O(1)和O(n)之间。这意味着，在最好的情况下，您的访问时间与地图中的元素数量无关，但在最坏的情况下，它是线性的，取决于您的哈希大小 table.
二叉树的搜索复杂度保证为 O(nlog(n))。这意味着，搜索元素总是取决于数组的大小，但在最坏的情况下它比散列更快 table.
您可以在这个方便的网站上查找一些 Big O Complexities：http://bigocheatsheet.com/
我的经验法则是假设处理器每秒可以处理 10^9 次操作。
在您的例子中只有 500 个条目。最多为 O(N^2) 的算法可能是安全的。通过使用像 vector 这样的连续数据结构，您可以利用快速缓存命中。此外，哈希函数有时在常量方面可能会很昂贵。但是，如果您的数据大小为 10^6，则安全复杂度总共可能仅为 O(N)。在这种情况下，您可能需要考虑 O(1) hashmap 进行一次查找。