Solved

Access violation

Posted on 2001-08-21
18
528 Views
Last Modified: 2010-08-05
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;
}
0
Comment
Question by:barzangy
  • 5
  • 4
  • 4
  • +2
18 Comments
 
LVL 32

Expert Comment

by:jhance
ID: 6409855
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
 

Author Comment

by:barzangy
ID: 6410066
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
 
LVL 32

Expert Comment

by:jhance
ID: 6410085
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
 

Author Comment

by:barzangy
ID: 6410102
No it will crash later when it tries to add the strings to the vector, I think it may be a memory problem.
0
 
LVL 32

Expert Comment

by:jhance
ID: 6410138
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
 
LVL 4

Accepted Solution

by:
IainHere earned 25 total points
ID: 6410691
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
 

Expert Comment

by:andrewschneider
ID: 6412728
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
 

Author Comment

by:barzangy
ID: 6412799
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
 

Expert Comment

by:andrewschneider
ID: 6412851
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
Maximize Your Threat Intelligence Reporting

Reporting is one of the most important and least talked about aspects of a world-class threat intelligence program. Here’s how to do it right.

 
LVL 4

Expert Comment

by:IainHere
ID: 6412855
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
 
LVL 4

Expert Comment

by:IainHere
ID: 6412863
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
 

Author Comment

by:barzangy
ID: 6413152
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
 

Expert Comment

by:andrewschneider
ID: 6413164
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
 
LVL 32

Expert Comment

by:jhance
ID: 6413179
Why won't you run this in the DEBUGGER?  My guess is that you'd have solved this by now.......
0
 

Author Comment

by:barzangy
ID: 6413276
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
 

Expert Comment

by:andrewschneider
ID: 6413308
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
 
LVL 4

Expert Comment

by:IainHere
ID: 6413817
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
 

Expert Comment

by:calum
ID: 6416610
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

Featured Post

How to run any project with ease

Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
- Combine task lists, docs, spreadsheets, and chat in one
- View and edit from mobile/offline
- Cut down on emails

Join & Write a Comment

In days of old, returning something by value from a function in C++ was necessarily avoided because it would, invariably, involve one or even two copies of the object being created and potentially costly calls to a copy-constructor and destructor. A…
C++ Properties One feature missing from standard C++ that you will find in many other Object Oriented Programming languages is something called a Property (http://www.experts-exchange.com/Programming/Languages/CPP/A_3912-Object-Properties-in-C.ht…
The viewer will learn how to clear a vector as well as how to detect empty vectors in C++.
The viewer will be introduced to the technique of using vectors in C++. The video will cover how to define a vector, store values in the vector and retrieve data from the values stored in the vector.

759 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

18 Experts available now in Live!

Get 1:1 Help Now