Блог пользователя Infinite.Loop

Solution with unordered_map giving TLE gets accepted with ordered_map
Автор Infinite.Loop, история, 4 года назад, По-английски

This is my solution when I used unordered_map.

This is my solution when I used ordered_map.

It is seen that unordered_map performs better than ordered_map so how can TLE get resolved with ordered_map but not with unordered_map???

  • Проголосовать: нравится
  • -18
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

The hashing is not perfect and with specific test cases, every find, insert etc. works in O(n) instead of O(1). Refer to this for more detail.

→ Ответить
  • »
    »
    4 года назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    But here all keys are ints and not int64_t/long longs, so their hashes do not (should not?) collide, so what's the real reason?

    → Ответить
    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +10 Проголосовать: не нравится

      https://codeforces.me/blog/entry/62393 this might help??

      → Ответить
    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +12 Проголосовать: не нравится

      If you look at the TLE testcase, it's pretty obvious what's going on: The input consists of exactly the multiples of 53201. They have different hashes, but these hashes all get mapped into the same bucket when the unordered map reaches the right size. Only the latter is needed for the bad worst-case performance of unordered_map to occur.

      → Ответить
      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        yes, thank you, we figured this out in another thread too, I forgot about the % bucket_count part

        → Ответить
      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        so should we avoid using unordered_map in contests and stick to map or use some custom hash with unordered_map like this.

        → Ответить
        • »
          »
          »
          »
          »
          4 года назад, # ^ |
          ← Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

          Using unordered_map with default hash on Codeforces is just begging to get hacked or fail system tests. What you do instead is up to you. Options include:

          1. Using (ordered) map: This takes no effort to set up and is fast enough most of the time (with obvious exceptions).
          2. Using unordered_map with a randomized custom hash function. This is OK and not very inconvenient to set up even without any pre-written code.
          3. Using a hand-rolled or library policy-based hash table, with a randomized custom hash function. This will give by far the best runtime performance.
          → Ответить
»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится 
| map             | unordered_map

Ordering | increasing order | no ordering | (by default) |

Implementation | Self balancing BST | Hash Table | like Red-Black Tree |

search time | log(n) | O(1) -> Average | | O(n) -> Worst Case

Insertion time | log(n) + Rebalance | Same as search

Deletion time | log(n) + Rebalance | Same as search

so the answer of your problem is in worse case unordered_map uses O(n) for each insertion .So your insertion in the testcase no 12 will take upto O(n^2) in your unordered map ,but it will take only O(nlog(n)) in map.

→ Ответить