PRESS_F_2_PAY_RESPECT's blog

Unordered Map vs Ordered Map
By PRESS_F_2_PAY_RESPECT, history, 5 years ago, In English

Hello guys!

In yesterday's round Codeforces Round 617 (Div. 3), in question 1296C - Очередной идущий робот, I submitted this solution using map which took 61ms to pass: 70273184. Today, I thought of submitting the same solution using unordered map, which I later found out doesn't have a hash function for pairs, so I copied the hash function from GeeksForGeeks and then submitted the solution which took 187ms to pass: 70355416.

Can somebody tell me why is unordered map working slower than map for this problem ?

Thanks.

  • Vote: I like it
  • -20
  • Vote: I do not like it

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

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

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

That hash function may not be very good. It will have some collisions: often (x+1,y) and (x,y+1) will have same hashes. Try different hash functions.

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

It's just due to weak hash function.Your solution using another hash function which i usually use for pairs when max value of my pair is <= 2e9 took just 46ms.

→ Reply