CODEWITHSUNDEEP
c++
DGounaris
DGounaris

Reputation: 182

c++ program unable to execute while reading more than 500000 integers

I have a project in which I have to store some values and return some results based on them. The results and stored values are all integers. I have made every variable a long long int so that it will definitely fit the numbers (the array could be as long as 1000000). While I get totally normal values on up to 400000 numbers stored and I get them in low time (0.25 seconds), on 500000 the program just fails to execute. If my antivirus is on, it will even delete the executable file once I try to build or run it. On build though, the program itself will not show any syntax errors. Any ideas?

Code below:

#include <iostream>
#include <fstream>
using namespace std;
int main() {
  ifstream TextIn;
  ofstream TextOut;
  long long int N, i=1, sum=0;
  TextIn.open("share.in", ios::in);
  TextIn >> N;
  long long int A[N];

  for (i=1; i<=N; i++) {
    TextIn >> A[i];
    sum=sum+A[i];
  }

  TextIn.close();
  long long int sum1c2=0, sum1c1=0;
  i=0;

  do {
    i=i+1;
    sum1c1=sum1c1+A[i];
  } while ((sum1c1<=2+sum/3) && (i<N-2));

  sum1c2=sum1c1-A[i];
  long long int sum2c1c1=0, sum2c1c2=0, sum2c2c1=0, sum2c2c2=0, j=i-1;

  do {
    j=j+1;
    sum2c1c1=sum2c1c1+A[j];
  } while ((sum2c1c1<=2+sum/3) && (j<N-1));

  sum2c1c2=sum2c1c1-A[j];
  j=i;

  do {
    j=j+1;
    sum2c2c1=sum2c2c1+A[j];
  } while ((sum2c2c1<=2+sum/3) && (j<N-1));

  sum2c2c2=sum2c2c1-A[j];
  long long int sum3c1, sum3c2, sum3c3, sum3c4;
  sum3c1=sum-sum1c1-sum2c2c1;
  sum3c2=sum-sum1c1-sum2c2c2;
  sum3c3=sum-sum1c2-sum2c1c1;
  sum3c4=sum-sum1c2-sum2c1c2;
  long long int max1=0, max2=0, max3=0, max4=0;

  if (sum1c1>sum2c2c1) {
    if (sum1c1>sum3c1){
      max1=sum1c1;
    } else {
      max1=sum3c1;
    }
  } else {
    if (sum2c2c1>sum3c1) {
      max1=sum2c2c1;
    } else {
      max1=sum3c1;
    }
  }
  if (sum1c1>sum2c2c2) {
    if (sum1c1>sum3c2) {
      max2=sum1c1;
    } else {
      max2=sum3c2;
    }
  } else {
    if (sum2c2c2>sum3c2) {
      max2=sum2c2c2;
    } else {
      max2=sum3c2;
    }
  }
  if (sum1c2>sum2c1c1) {
    if (sum1c2>sum3c3) {
      max3=sum1c2;
    } else {
      max3=sum3c3;
    }
  } else {
    if (sum2c1c1>sum3c3) {
      max3=sum2c1c1;
    } else {
      max3=sum3c3;
    }
  }
  if (sum1c2>sum2c1c2) {
    if (sum1c2>sum3c4) {
      max4=sum1c2;
    } else {
      max4=sum3c4;
    }
  } else {
    if (sum2c1c2>sum3c4) {
      max4=sum2c1c2;
    } else {
      max4=sum3c4;
    }
  }

  long long int final_max;
  if (max1<=max2 && max1<=max3 && max1<=max4) {
    final_max = max1;
  } else if (max2<=max1 && max2<=max3 && max2<=max4) {
    final_max = max2;
  } else if (max3<=max1 && max3<=max2 && max3<=max4) {
    final_max = max3;
  } else {
    final_max = max4;
  }

  TextOut.open("share.out", ios::out);
  TextOut << final_max;
  TextOut.close();
  return 0;

}

Upvotes: 0

Views: 448

Answers (3)

tom
tom

Reputation: 354

Without having looked at your code I would say that 500000 integers is a very large number. Lets assume 8 bytes per integer(Which I believe is the minimum size of a long long).

500000*8 == 4000000 bytes or 4 megabytes, which is probably close to, if not, the size of your program's stack.

Solution: try using heap memory if you are going to be storing that amount of data.

Although this may not be the problem, especially if the antivirus flags it up(Which seems very strange to me). And if this was the case your program would segfault.

Upvotes: 0

PaulMcKenzie
PaulMcKenzie

Reputation: 35454

Creating arrays in C++ using runtime values as the number of entries in the array is not legal C++. Some compilers can do this using an extension, but it still means that the code is using non-standard C++ syntax.

To get around this issue, plus more than likely solve your problem, use std::vector instead of arrays:

TextIn >> N;
std::vector<long long int> A(N);

The second issue is that you have at least one memory overwrite in your program:

for (i=1;i<=N;i++)
{
    TextIn >> A[i];
    sum=sum+A[i];
}

Arrays are indexed in C++ start from 0, not 1 and go to n-1, where n is the total number of entries. So the loop above should be:

for (i=0;i <N; i++)
{
    TextIn >> A[i];
    sum=sum+A[i];
}

Upvotes: 1

Cory Kramer
Cory Kramer

Reputation: 117951

You cannot declare an array with runtime size on the stack without using a compiler extension. So long long int A[N]; is illegal.

That being said with a 500000 element array, you are likely to hit a stack overflow. You should instead do something like

TextIn >> N;
std::vector<long long int> A(N);
for (long long int i = 1; i < N; ++i)
{
    TextIn >> A[i];
    sum += A[i];
}
TextIn.close();

The reason this will help is that even though the vector A is declared on the stack, the underlying memory is allocated from the heap, which has much more memory available than the stack.

Upvotes: 4

Related Questions