low_'s blog

C++ std::map ???
By low_, 6 years ago, In English

I used std::map to solve 1029D - Concatenated Multiples.

I calculated that the time complexity for this algorithm which is about O(10*NlogN) for preprocessing and O(NlogN) for finding the answer, which makes the total complexity be around O(11*NlogN) (Submission: 42125423 ), which is close to the solution in the tutorial (which uses sorting + binary search).

But this code got TLE-d. I really don't know why. I used sorting and binary search to solve this afterwards and got accepted (42126892), with way less time than the std::map submission (429 ms compared with 2000+ ms).

My question is: How does std::map (or maybe even std::set) works? And why does it takes so long to process data if the procedures can be done in "logarithmic" complexity (as stated on https://en.cppreference.com/w/cpp/container/map )?

I think next time I should avoid using both std::set and std::map if possible...

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

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

std::map is a balanced BST(red–black tree) whitch means we need to rotate the tree to make it balanced when it's about to become unbalanced(to keep the time logarithmic) so this rotation operation is costy, so it's logarithmic time but with high constant factor. you may want to see https://en.m.wikipedia.org/wiki/Tree_rotation

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

    Thanks, now I understand why.

    Still, I find the concept of red-black tree rather abstract to me. Can you send me some source on how it works with some problems so I can work on it?

    Thanks a lot!

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

      you can find details about red-black tree here. about problems I didn't face any problem that requires to implement it myself yet.

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

I was able to solve this using std::map. 4209124

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

    Wow, nice, but it still takes about 1.6 sec, which is so close to TLE :))

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

As KyRillos_BoshRa said, this is not just a logarithm, with the logarithm multiplied by a very big hidden constant, because std::map and std::set implemented as red-black tree with active using dynamic allocation of memory and recursion calls — this is the main problem.

This is very sad. My solution works in time 1933 ms, I was lucky, you probably, don't, but it very closer to time limit and codeforces testing system incorrectly measures time.

I see that you love GCC, try to use gp_table_table<int,int> — fastest hash table in GCC. Blogpost.

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

    Thanks for the links! But next time I'd rather find a simpler solution for these kinds of problems instead of trying new stuffs.

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

check a.find(i)!=a.end() before summation to avoid adding extra element in map whenever a[i] returns 0

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

There is no problem with std::map. What causes your program TLE is this line of code: 

#define int unsigned long long

The cost of operations on 64-bit integers is so expensive, so you should avoid replacing all int's with long long's like that. Furthermore, your precalculation of powers of 10 is not so efficient, and it also may cause long long overflow (since a[i] <= 10^9 and pow10[10] = 10^10, multiplication of these two numbers will cause overflow).

You can see this submission for more details how to fix: http://codeforces.net/contest/1029/submission/42129887

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

    It's funny that this code gets 4 TLE against 6 Accepted in 10 same submissions (sub. 4, sub. 7, sub. 8, sub. 9, original picture):

    TLE

    So your optimizations helps with 60% probability

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

    Good point.

    But actually, I think the main problem lies in improving the algorithm. Using std::map can cause you way more than O(logN) for each procedure (as KyRillos_BoshRa commented above). If the algorithm is correct, it should run efficiently and its running time should be way less than the time limit, despite the fact that it is far from optimization (42126892).

    Optimization and fast I/O is fine. It can reduce your running time efficiently. But sometimes, fast I/O can still be hacked if the algorithm is not good enough.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 3   Vote: I like it +19 Vote: I do not like it

      I got 374 ms with std::map<int,int> in my solution

      Key trick is this:

      auto it = cnt[nd].find(need);
answ += it == cnt[nd].end() ? 0 : it->second;

      Against this in my previous 1933 ms submission:

      answ += cnt[nd][need];

      Why? If we call operator[](key) and map not contains this key, then map create this element and assign map[key] = 0. If we just find iterator on item a new element will not be created.

      → Reply
»
6 years ago, # |
← Rev. 5   Vote: I like it +4 Vote: I do not like it

The following is a slight update to your code which passed the required time-limit in 1028 msec using the STL function map::find() and the std::to_string() function.

42136203

Note the two nested loops updating the array of maps have been swapped, and as such it is not necessary to store the powers of 10 in an array. This also improves the spatial locality of accessing the array of maps, as each individual map is accessed only during one iteration of the outer loop.

→ Reply