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

A faster way to clear your arrays, vectors and structures in general in C++!
Автор pikamonstruosa, 17 месяцев назад, По-английски

Hello guys, today I will do a tutorial on how to clean a vector, structure or something else in c++ really fast.

Naive Approach

-A newbie may see this problem and try to solve it in linear time, for that we could just use the resources the C++ libraries offer us. In this particular case, the function clear() would do it. However, it is an $$$ O(length) $$$ function and considering N can be very big, until $$$ 10^9 $$$, for an example, it cannot solve every problem of this type.

Smart Approach

-A more experienced coder, like Errichto, will see this problem and immediately think about the smart approach. This approch consists of doing the following:

Code

  • Boom!, the complexity fell from ~$$$O(N)$$$ to ~$$$O(1)$$$. On my machine clearing vector of size $$$10⁸$$$ with the dumb approach took $$$0,789s$$$ and with the smart approach it took $$$0,438s$$$. Thus, in the next time you need to clear a lot of vectors, use the smart approach, your code will be much faster.

  • P.S: this idea can easily be expanded for other structures, just substitute the 'vector' in the code for the structure you want and make the necessary changes to it.

Co-authors: tourist, Um_nik, Errichto.

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

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

defnotmee, you need to see this amazing trick

→ Ответить
»
17 месяцев назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

Amazing tricks! No idea why this blog is downvoted ??? T_T ???

This works because we don't actually free the underlying memory, we just exchange the memory handled by the vector we use with a new (empty) vector. And when our program terminates, the time the OS take to free the memory isn't counted toward our execution time.

Most of the time this is fine, we will have enough memory for the whole test case anyway, however most of the time we don't need to get the extra time either. Use at your own risk.

→ Ответить
  • »
    »
    17 месяцев назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    Right?? Well, this is a silly trick and has little to no use, but it acually works lol.

    → Ответить
  • »
    »
    17 месяцев назад, # ^ |
    ← Rev. 4   Проголосовать: нравится +13 Проголосовать: не нравится

    I might not be taking your sarcasm, but if it's not the case, I argue that the trick is absolutely useless.

    The memory should be freed anyways. In case you are using this aux vector trick, it will be freed at the time the aux's destructor is called. This is counted toward the execution time, so you save time in one place to spend it in another.

    Moreover, the constant factors for memory use are so much weird, that I wouldn't argue anything without testing. The blog author states, that swapping vector of size 1e8 halves (not divides by 1e8, halves!) the execution time. I don't know, what code did he use for testing, but this one

    UPD: the following part is changed, the previous version of the code worked not as intended.

    Spoiler

    shows that the printed times are basically the same (for different N and K combinations) for (1) being commented out versus for (2) being commented out. (The times printed with cout should not count time for aux's destructor to be called, you can ignore them — I actually used CF's messages from customtest)

    Therefore, I would be really surprised, if anyone could show a real example, where one benefits from using the trick — I think that this is the case where the most straightforward way is the fatest.

    → Ответить
    • »
      »
      »
      17 месяцев назад, # ^ |
        Проголосовать: нравится +10 Проголосовать: не нравится

      I did a bit of trolling.

      But to be fair, I'm not so sure about this topic, because it depend on lots of things. Theoretically, you're totally right, there's no different where you free the memory.

      In practice, it can be argued that when the vector is freed by the dtor (after main), the system free all the memory at once, so it can do it more efficiently.

      But it can also be argued that if you are actually going to do things with the vector (i.e. emplace/push back), then .clear() is superior because you don't pay for the vector growth unless the max size actually increase.

      → Ответить
»
17 месяцев назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

So you create a useless std::vector<std::vector<int>> to save all the std::vector that you ever used?

Dont you think it is silly lol

By the way, clear() is O(1), but not O(len) I remember.

→ Ответить