Блог пользователя hmrockstar

Why unordered_map is slower than map in some cases?
Автор hmrockstar, история, 8 лет назад, По-английски

Hello Everybody!

For "ICM Technex 2017 and Codeforces Round #400 (Div. 1 + Div. 2, combined)" Problem C the given n is 105 and the max possible sum is 10 5 * 10 9 i.e., 1014. For the worst case, my code's complexity is: log(1014)*n. And in worst case it will be approximately 50*105 . I was expecting that my code will get Accepted easily, coz given time limit is 2.5 sec, but its exceeding time limit on 101 test case which is 100000 2 .

Isn't it possible to execute 5*106 in 2.5 sec?

Why unordered map is taking more time in comparison with map!

Thank you very much for reading!

Link to submission: 24944382

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

»
8 лет назад, # |
← Rev. 2   Проголосовать: нравится +10 Проголосовать: не нравится

Unordered map is the problem here ...

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

    Why???? 24945968 got AC by just changing unordered to map! Why why why???

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

      Unordered structures are linear at worst. They use hash functions internally, so its O(1) in average but in case of multiple collisions the search takes O(n) operations. Regular map, on the other side, is O(log n) at worst.

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

Auto comment: topic has been updated by hmrockstar (previous revision, new revision, compare).

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

http://mirror.codeforces.com/blog/entry/21853 Arpa is the hero. :v

→ Ответить