RifatALmuiN's blog

Why does the time taken differ so much?
By RifatALmuiN, history, 6 months ago, In English

First one (2027 ms): 253857814
The second one (249 ms): 253859120

In my observation, both of them have a time complexity of O(n2logn2)

  • First one: I created a vector of pairs that have a size of nearly n2 and inserted all of them in a map which will take O(n2logn2) time complexity.
  • Second one: I created a vector of pairs with a similar size of nearly n2. And I then sorted it which will take O(n2logn2) time complexity.

Then why the second approach is taking so much less time?

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

»
6 months ago, # |
← Rev. 2   Vote: I like it +4 Vote: I do not like it

Map has a large constant factor, use vectors whenever you can. If you can't use vectors use unordered map with custom hash

→ Reply
»
6 months ago, # |
← Rev. 2   Vote: I like it +12 Vote: I do not like it

C++ std::sort() is giga optimized

→ Reply
»
6 months ago, # |
← Rev. 3   Vote: I like it +12 Vote: I do not like it

For maps, they will create a lot of small memory blocks, and the internal tree structure requires additional resources.

For vectors, it's just an array, it will only expand a few (logarithmic) times. The memory blocks are consecutive. And sortings itself adds much less additonal resource to compute.

I don't really use unordered maps (hash maps). I suppose that you can pass with a normal map in most times if the problem requires one. Though sometimes there are significant time improvement with hash maps.

→ Reply