hmrockstar's blog

Why unordered_map is slower than map in some cases?
By hmrockstar, history, 8 years ago, In English

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

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

»
8 years ago, # |
← Rev. 2   Vote: I like it +10 Vote: I do not like it

Unordered map is the problem here ...

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

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

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
      ← Rev. 2   Vote: I like it +4 Vote: I do not like it

      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.

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

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

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

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

→ Reply