Want to win a PS4? Go Premium and enter to win our High-Tech Treats giveaway. Enter to Win

x
?
Solved

Access violation

Posted on 2001-08-21
18
Medium Priority
?
546 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
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 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
VIDEO: THE CONCERTO CLOUD FOR HEALTHCARE

Modern healthcare requires a modern cloud. View this brief video to understand how the Concerto Cloud for Healthcare can help your organization.

 

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 100 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
 
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

Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Often, when implementing a feature, you won't know how certain events should be handled at the point where they occur and you'd rather defer to the user of your function or class. For example, a XML parser will extract a tag from the source code, wh…
IntroductionThis article is the second in a three part article series on the Visual Studio 2008 Debugger.  It provides tips in setting and using breakpoints. If not familiar with this debugger, you can find a basic introduction in the EE article loc…
The viewer will learn how to pass data into a function in C++. This is one step further in using functions. Instead of only printing text onto the console, the function will be able to perform calculations with argumentents given by the user.
The viewer will learn how to use the return statement in functions in C++. The video will also teach the user how to pass data to a function and have the function return data back for further processing.
Suggested Courses

636 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