tyr0Whiz's blog

MLE with vectors, but arrays work fine
By tyr0Whiz, history, 2 years ago, In English

I was solving this problem when I implemented it using vectors (this solution) I got MLE(Memory Limit Exceeded) and when I declared a global array in this solution I got AC. I even tried to declare vectors globally but still MLE. Does anyone know what is problem with using vectors here

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

»
2 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Every vector allocates memory dynamically, means it has to contain a pointer. Also, it should also remember how many elements are in the array. So, even if the vector's size is only 2 it actually uses way more memory than that.

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

    I think it should also hold allocated size that may differ from the number of elements, so that it knows when to reallocate memory when more elements are pushed.

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

    Thanks a lot

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

Just in addition to djm's answer: you could run this code in Custom Invocations and see, that each vector in that compiler has at least size of 24 bytes (8 bytes to store pointer, 8 bytes to store allocated size, 8 bytes to store actual size + n bytes of allocated content), and your vector at least 5000 * 5000 * 24 / 1024 / 1024 ~ 572 Mb. In C++ ofc there is no difference where to declare vector (globally or locally, memory consumption will be the same).

#include <iostream>
#include <vector>

using namespace std;

int main() {
    vector<short int> v(2);
    cout << sizeof(v) << endl;
}
→ Reply
»
2 years ago, # |
← Rev. 3   Vote: I like it +10 Vote: I do not like it

The vector use "Double size" method to expand the number of elements. So when you expand it to 2x10^5 elements its actual size will be more than 3x10^5, which is MLE verdict.

About Double size method: you got an vector of 5 elements, actual size is 5 slots, when you append new elements, it create new vector (5x2=10 slots in actual size, then COPY data from old vector which has 5 elements) with 5 empty slots, you add new element, we have vector of 10 slots, 6 elements, you add more elements, it will be doubled to 20, 40, 80 and so on...

More about it: Why vector size got doubled

Sorry for my bad English though, I did my best.

Edit: For those of you may ask: why don't we expand just 1 slot? — The answer is to save the time we use to copy data from old vector to the expanded vector.

→ Reply