Can i reduce memory use in this c++ code?

Question

#include <bits/stdc++.h>
using namespace std;

int n;

vector<bool> used;
 vector<int> order, comp;

void dfs1 (int v,const vector<vector<int>>& g) {
used[v] = true;
for (size_t i=0; i<g[v].size(); ++i) {
    int to = g[v][i];
    if (!used[to])
        dfs1 (to,g);
}
order.push_back (v);
}

void dfs2 (int v, int cl,const vector<vector<int>>& gt) {
comp[v] = cl;
for (size_t i=0; i<gt[v].size(); ++i) {
    int to = gt[v][i];
    if (comp[to] == -1)
        dfs2 (to, cl,gt);
}
}

  int main() {
  int q1,q3;
  cin>>q1>>n>>q3;

  n*=2;
  vector < vector<int> > g(n), gt(n);
  vector< vector< int> > adj(q1+5);
    int o,oo;
  for(int i=0;i<q3;i++){
         cin>>o>>oo;
         if(oo<0){
           oo+=1;
           adj[o].push_back((oo*-1)*2+1);   
         } else{

           oo-=1;
              adj[o].push_back(oo*2);

         }

  }   

  for(int i=1;i<=q1;i++){

       for(int j=0;j<adj[i].size();j++){
            for(int k=0;k<adj[i].size();k++){

                    if(j!=k){
                   g[adj[i][j]^1].push_back(adj[i][k]);
                        gt[adj[i][k]].push_back(adj[i][j]^1);
                       }
              } }
              }  



     used.assign (n+1, false);
 for (int i=0; i<n; ++i)
    if (!used[i])
        dfs1 (i,g);

comp.assign (n+1, -1);
for (int i=0, j=0; i<n; ++i) {
    int v = order[n-i-1];
    if (comp[v] == -1)
        dfs2 (v, j++,gt);
}

for (int i=0; i<n; ++i)
    if (comp[i] == comp[i^1]) {
 cout<<-1;
        return 0;
    }
vector<int> answ;

for (int i=0; i<n; i+=2) {
    int ans = comp[i] > comp[i^1] ? i : i^1;
      if(ans%2==0){
        ans/=2;

        ans++;
              answ.push_back(ans);

  }
}
cout<<answ.size()<<endl;
for(int i=0;i<answ.size();i++){
cout<<answ[i]<<endl;
}



 }

This is code which solves problem connected with 2SAT. When entering value n=200 000 this code exceeds memory limit which is 512 mB. What tricks i can use to reduice memory use? I have already tried assigning vectors g and gt in main code, and then in dfs and dfs2 functions I put g and gt but that gave me time limit issue. How i can optimise this code?

512 MB is all the memory you have? What system are you working on? — PaulMcKenzie, Nov 18 '18 at 09:21
[Why should I not #include ?](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h?lq=1) — Jesper Juhl, Nov 18 '18 at 09:23
A few points unrelated to your problem: [Don't include ``](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h); Avoid global variables; Use descriptive function and variable names; Descriptive comments are missing; The indentation is inconsistent; You don't do bounds-checking; The use of the ternary expression makes your code even more unreadable. — Some programmer dude, Nov 18 '18 at 09:23
Questions about optimizing working code might bei asked on https://codereview.stackexchange.com — bummi, Nov 18 '18 at 09:23
Make sure you are compiling with optimization enabled. If reducing memory use is paramount (and you are using gcc) then experiment with `-Os` which optimizes for size rather than speed (`-O2`/-O3`). Also, using Link Time Optimization `-flto` can sometimes give some size savings. — Jesper Juhl, Nov 18 '18 at 09:28
@bummi But before posting there the OP must be absolute certain that the program really works. — Some programmer dude, Nov 18 '18 at 09:37
you keep all intermediate values in memory. You could try to calculate only the next element of the answer, print it, then calculate the next element. In that way maybe you can turn some of the vectors into flat numbers — 463035818_is_not_an_ai, Nov 18 '18 at 09:40
The first attempt to minimize memory should be to work at algorithm level, not code level. Difficult to understand it from your code. Could you describe simply the algorithm you are using? — Damien, Nov 18 '18 at 09:54
You create two big arrays g and gt. You then use g only, then gt only. These two processes seem independent. You can gain memory by deleting g before creating gt and using it. — Damien, Nov 18 '18 at 10:18

score 0 · Answer 1 · answered Nov 18 '18 at 09:40

You are not using g and gt at the same time. So clear g and reserve gt after that. ( comp.assign (n+1, -1); before this line )

Same with used and comp.

used and adj are not used at the same time. Clear adj before line used.assign (n+1, false);

Try using adj as a C style vector( int** ) and another vector for the individual sizes.

Can i reduce memory use in this c++ code?

1 Answers1