When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

dx24816's blog

By dx24816, history, 5 years ago, In English

Hello,

Recently, I was doing Cow Run (http://www.usaco.org/index.php?page=viewproblem2&cpid=265), and I at first used the Policy Based Data Structure faster map (https://codeforces.com/blog/entry/60737), but I TLE'd on the last 4 test cases. I then switched back to using the unordered_map, and I passed all the test cases. Can anyone tell me the reason why the unordered_map was faster? I was under the impression that the PBDS map was faster. Thanks!

Code with unordered_map: https://ideone.com/Id7SZM Code using PBDS map: https://ideone.com/sA4UJG

To run this code, simply submit them in a file to the USACO website above, and use C++11.

-dx24816

  • Vote: I like it
  • +4
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it +11 Vote: I do not like it

As I mentioned in the blog post, one downside of gp_hash_table is that it's significantly more fragile to weak hash functions (due to being open addressed and using power of 2 table sizes). I can't currently submit to USACO for whatever reason..., but I did run it on the test data.

I use this hash function unsigned hash_f(unsigned x) { x = ((x >> 16) ^ x) * 0x45d9f3b; x = ((x >> 16) ^ x) * 0x45d9f3b; x = (x >> 16) ^ x; return x; } and I got 0.10 for gp_hash_table versus 0.30 for unordered_map.

https://ideone.com/ikfX3E

You can also use cc_hash_table for a hash table that's a lot more resistant to weak hash functions.