Access violation

This program cause an access violation if the permutaions is greator than one million (windows) or two million (linux) , any idea what is the problem?

#include <string>
#include <iostream>
#include <algorithm>
#include <strstream>
#include <vector>

using namespace std;

unsigned long int factorial (unsigned long int a) {
     if (a < 1) return 1;
     return a * factorial(a - 1);
}

void usage (string s) {
     cout << "Usage:\n\t" << s << " string.\n";
     exit(0);
}

void unique1 (const string & s, string & unique_s) {
     unique_s.resize(s.size());
     string::iterator sp = unique_copy(s.begin(), s.end(), unique_s.begin());
     unique_s.erase(sp, unique_s.end());    
}

void randomShuffle1 (const string & s, string & shuffled_s) {
     shuffled_s = s;
     random_shuffle(shuffled_s.begin(), shuffled_s.end());
     cout << "Random shuffled: " << shuffled_s.c_str() << endl;
}

permutations1 (const string & s) {
     string sUnique;
     unique1 (s, sUnique);
     unsigned long int devideBy = 1;
     string::iterator sp;
     for (sp = sUnique.begin(); sp != sUnique.end(); sp++) {
          unsigned long int c = count(s.begin(), s.end(), *sp);
          if (c > 1) devideBy = devideBy * factorial(c);
     }
     unsigned long int permutaions = factorial(s.size()) / devideBy;
     cout << "No. of permutations = " << permutaions << endl;
}

void listPermuts(string & s, vector<string> & vec) {
     vec.clear();
     unsigned long int pos = 0;
     unsigned long int dummy = 0;
     do {
          ++pos;
          vec.push_back(s);
          if (++dummy > 300) {
               dummy = 0;
               cout << "\rProgress: " << pos;
          }
     } while (next_permutation(s.begin(), s.end()));
     cout << "\rProgress: " << pos << endl << endl;
}

int main (int argc, char * argv[]) {
     if ( argc != 2) usage (argv[0]);
     string s = argv[1];
     if (s.size() < 1) usage(argv[0]);

     sort(s.begin(), s.end());
     cout << "Sorted: " << s << endl;

     string sUnique;
     unique1 (s, sUnique);
     cout << "Unique: " << sUnique << endl;

     string sRandomShuffle;
     randomShuffle1(s, sRandomShuffle);

     permutations1(s);

     vector<string> permuts;
     listPermuts(s, permuts);
     vector<string>::iterator vsit = permuts.begin();
     while ( vsit != permuts.end()) {
          cout << *vsit << "\t";
          vsit++;
     }
     cout << endl << endl;
     return 0;
}
barzangyAsked:
Who is Participating?
 
IainHereConnect With a Mentor Commented:
The problem is memory, as you answered for yourself above.  I tried replacing the push_back with a vec.resize() to the value of 'permutations' in permutations1, and my machine wouldn't give me the required memory.

You're coming across the same thing, in the line vec.push_back(s); where more memory is grabbed for the vector (also, because the vector is being resized a lot, you're possibly fragmenting memory, which would mean you could do fewer permutations than you would be able to - it is certainly a lot slower than it could be).

There would be no solution to getting a vector of infinite length, but in this case, you could simply write the values out as they're calculated:

while (next_permutation(s.begin(), s.end())) cout << s << '\t';

If you want the values later in the program, you'll have to write them to a data file.
0
 
jhanceCommented:
My first inclination is to look at this function:

unsigned long int factorial (unsigned long int a) {
    if (a < 1) return 1;
    return a * factorial(a - 1);
}

It doesn't take a very large value of a to overflow.  Have you looked to see if there is a relationship between your problem and an overflow of a?
0
 
barzangyAuthor Commented:
I'm sure that is not the case , when I give the string "abcdefghijk" then it's not overflowed , I changed the function as follows:

unsigned long int factorial (unsigned long int a) {
     cout << " A: " << a << endl;
     unsigned long int result;
     if (a < 1) result = 1;
     else result = a * factorial(a - 1);
     assert (result >= a);    
     cout << "Result: " << result << endl;
     return result;
}

And I get the following result:

Sorted: abcdefghijk
Unique: abcdefghijk
Random shuffled: edackhijfbg
 A: 11
 A: 10
 A: 9
 A: 8
 A: 7
 A: 6
 A: 5
 A: 4
 A: 3
 A: 2
 A: 1
 A: 0
Result: 1
Result: 1
Result: 2
Result: 6
Result: 24
Result: 120
Result: 720
Result: 5040
Result: 40320
Result: 362880
Result: 3628800
Result: 39916800

No. of permutations = 39916800
.
.
.
.
.
etc


0
Cloud Class® Course: C++ 11 Fundamentals

This course will introduce you to C++ 11 and teach you about syntax fundamentals.

 
jhanceCommented:
Now I'm confused.  You said it would fail with > 1M or 2M permutations.  But you just ran an example with 39M permutations.  So it's working now?
0
 
barzangyAuthor Commented:
No it will crash later when it tries to add the strings to the vector, I think it may be a memory problem.
0
 
jhanceCommented:
Do you know what line it's crashing on?  I'm not up on unix debugging but under Windows (assuming you are using VC++) just build the DEBUG version and run under the debugger.  The problem may be obvious to you when the fault happens.
0
 
andrewschneiderCommented:
If you get an access violation with an out of heap space, isn't that a bug in the compiler generated code? new is supposed to throw an exception on out of space so you should get an unhandled exception (unless the STL implementation isn't using new) - or is using new in backward compatible mode where it returns 0.
0
 
barzangyAuthor Commented:
Indeed it is an unhandled exception that I get, the message box in the debugger says:
"Unhandled exception in algos.exe: 0xc0000005 Access Violation." this is in vc++ 6.0
But when I run the program from the explorer it performs an illegal operation and is closed by Windows.

0
 
andrewschneiderCommented:
If that is indeed a C++ exception rather than a Windoze exception you could catch it using cat (Cool, then you can either handle the memory by dumping your generated stuff to file or catch the exception std::bad_alloc. If the catch failes then it's probably a windoze exception caused by STL not handling an out-of-memory cleanly (or you not).
0
 
IainHereCommented:
Yes, you can verify that (and avoid the illegal operation) by changing to the following:

try
{
    vector<string> permuts;
    listPermuts(s, permuts);
    vector<string>::iterator vsit = permuts.begin();
    while ( vsit != permuts.end()) {
         cout << *vsit << "\t";
         vsit++;
    }
    cout << endl << endl;
}
catch (...)
{
   cout << endl << "Back to the drawing board." << endl << endl;
}

return 0;
0
 
IainHereCommented:
andrewschneider:

sorry - you hadn't posted that when I started typing.  When I ran it, the exception caught wasn't a bad_alloc - hence my catch all.
0
 
barzangyAuthor Commented:
I have changed the program to the following:

     vector<string> permuts;
     try {
          permuts = vector<string>(perms);
     }
     catch (...) {
          cout << " Exception occured.\n";
          return -1;
     }

But still I get no exception occured.

Only the program aborts and terminates with an error.
0
 
andrewschneiderCommented:
Then it's a memory problem. You need find what the stack trace is at the crash point and then try and infer what problem. As jhance says, you need to hit this with a debugger.
0
 
jhanceCommented:
Why won't you run this in the DEBUGGER?  My guess is that you'd have solved this by now.......
0
 
barzangyAuthor Commented:
The error occured inside a nasty stl header which is very comlicated.

I changed the application to a windows application (it was first a console application) the program now runs continuously but it becomes very very slow after some few millions of permutations.

I also made a system monitor picture.
it is at www.kvi.nl/~barzangy/system.jpg 
This program uses a huge ammount of memory.

How to handle such pograms? Writing in a data file will not help much I think.

<img src=http://www.kvi.nl/~barzangy/system.jpg>
0
 
andrewschneiderCommented:
If you have a huge data set which has to all be in memory at the same time then the best bit is probably lots of RAM, a 64 bit machine and rely on virtual memory.

If you can work on parts of the data set at a time then files (or other secondary storage organisational concept) do help since you can manually page parts of your data set to disk and just keep a working set in memory. Sometimes a bespoke solution here can give you less thrashing than an OS virtual memory system (but not always by any means).

In my experience (not being someone involved in large scale numerical computation) most business problems can be re-worked to process a particular rolling window of data at any one time.
0
 
IainHereCommented:
Did you include all of the remainder of the existing code in the try block?  It would be possible to initialise the vector and fail to set all of the strings.  It certainly threw up when I ran it.

>How to handle such pograms? Writing in a data file will not help much I think.

It entirely depends on why you want to store all of the permutations.  If this is only a test case, then you'd need to look at the logic of the final program.  As I mentioned, for this simple case, you can simply print out the results as they're calculated.  If you need *all* of them at a later date, then writing them to disk would be your only option.  The program I'm working on at the moment, for instance, performs (up to) millions of iterations, writing calculated values to disk, and then scans back through the data files calculating the statistics that are the final output.
0
 
calumCommented:
having quickly read this thread - if vector won't work properly you could try a linked list. it will store your data any place it can without requiring a contiguous memory space. you could try a malloc for the largest value you realistically expect to see where your limits lie ... as i;m sure you are aware once you start getting into permutations the size grows massively very very quickly. when i work with large amounts of data i tend to write to disk as iainhere suggested above.

calum
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.