balbit's blog

Why is hashing so slow?

By balbit, history, 5 years ago, In English

Hello, Codeforces.

I tried to use hashing to solve 1129C - Morse Code. However, I kept getting the TLE verdict. My time complexity should be O(k * m^2) (where k is the longest string to be tested, or 4) while the editorial's solution has time complexity O(k * m^2 + m^2 * log m).

I've tried many optimizations, such as using 2^64 as a base, switching between unordered_map and map, tweaking the multiplied prime, and even adding huge strings of pragmas. Pre-doing all the hashes gave me an MLE.

Here is a link to one of my many failed submissions : 58709459. Please help!

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

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

I was able to squeeze it using self-written unordered map. Standard one is very slow and not able to perform 9*10^6 operations in two seconds. 58835699

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Is it because it hashes the input value, or because the unordered_map expands itself when it gets too large?

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      That's just because of the slow nature of the unordered map. At least, there is different data structure implemented, mine is linear, while standard uses buckets as far as I know.

      → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

AC with unordered_set: 50590417

→ Reply
»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

seen.max_load_factor(0.7); => AC

→ Reply