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

Why does the time taken differ so much?
Автор RifatALmuiN, история, 6 месяцев назад, По-английски

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?

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

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

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

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

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

→ Ответить
»
6 месяцев назад, # |
← Rev. 3   Проголосовать: нравится +12 Проголосовать: не нравится

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.

→ Ответить