qsort - Segmentation Fault

V

Victor Bazarov

KS said:
I'm writing some c++ code after a few years with Java and your help is
appreciated. I am getting a core dump on a call to qsort. Can you take
a look at the code and see if there are any obvious errors? (The
function main is at the bottom of the file.)
[...]

Please follow the recommendations in FAQ 5.8.

V
 
K

KS

Please follow the recommendations in FAQ 5.8.

V

Thanks. I'm using Borland C++ 5.02 on Windows and gcc on grex. Both
report the same thing. No special compiler/linker flags are used. The
message I get is a simple core dump (Segmentation fault). Its not
possible to post minimal code in this case (all parts from the
beginning to end are required for compilation and execution). The part
that causes the segmentation fault is the call to qsort (12th line in
main()).

KS
 
T

Thomas J. Gritzan

KS said:
Hello,

I'm writing some c++ code after a few years with Java and your help is
appreciated. I am getting a core dump on a call to qsort. Can you take
a look at the code and see if there are any obvious errors? (The
function main is at the bottom of the file.)

Code: http://www.grex.org/~kpp/cmultiknapsack.cpp

To run this file you will need http://www.grex.org/~kpp/orlib1.txt in
the same directory.

http://www.parashift.com/c++-faq-lite/how-to-post.html#faq-5.8

Decide if you want to write C++ or C. Mixing the two languages utilize the
worst of two worlds.

For C++: Use std containers when possible and std::sort instead of qsort().
Don't new() everything. It might be necessary in Java, but its bad practice
in C++.
 
J

Jerry Coffin

Hello,

I'm writing some c++ code after a few years with Java and your help is
appreciated. I am getting a core dump on a call to qsort. Can you take
a look at the code and see if there are any obvious errors? (The
function main is at the bottom of the file.)

I haven't tried to find the specific problem you're citing in the code.
Just at first glance, it has enough problems that I'd advise nearly a
complete rewrite. I'll cite only a few of the most obvious problems, and
leave it to you to clean it up enough that it's worth looking at in more
detail.
/* Globals */
int POPULATION = 10;
int NUMBER_OBJECTS = 100;
int NUMBER_CONSTRAINTS = 5;

Commenting that these are globals is silly -- anybody who knows enough
to read the rest at all already knows these are globals.

In C and C++, all-caps names are normally reserved for macros -- these
names are misleading. Most of these probably shouldn't exist in the
first place -- in a typical case, the number of objects, constraints,
etc. should be detected from the input data. I'd use things like:

const int population = 10;
const int number_objects = 100;
const int number_constraints = 5;
int generateRandomNumber(int min, int max)
{
int r;
double randd = ((double)rand() / ((double)(RAND_MAX)+(double)(1)));
r = (int) (randd * (double)(max-min+1)) + min;
return r;
}

This manages to be both inefficient and incorrect. Personally, my
recommendation is:

int rand_lim(int limit) {
int divisor = RAND_MAX/(limit+1);
int retval;

do {
retval = rand() / divisor;
} while (retval > limit);

return retval;
}

int GenerateRandomNumber(int lower, int upper) {
int range = abs(upper-lower);

return rand_lim(range) + min(lower, upper);
}

This avoids floating point, and produces numbers that are evenly
distributed within the specified range (assuming rand() produces an even
distribution in its range).
class KNode
{
private:
int * knapsack;
int value;
int * weights;

Members of a class are private by default so I'd skip the "private" tag.
Looking below, knapsack apparently has a fixed size, and is only
supposed to hold the values 0 and 1. If that's correct, I'd do something
like this:
typedef bitset<number_objects> knappy;

knappy knapsack;

You might also consider a vector<bool> as an alternative, but offhand
the bitset looks more suitable to me. It appears that weights does hold
actual integers, so I'd define it as:

vector said:
public:
KNode()
{
printf("\nShould Not Call Default Constructor!");
}

If you don't want this to be called, declare it private, and don't
define it. This prevent code that attempts to use it from building at
all instead of building and then giving an error message at runtime.
KNode(int * knap)
{
//printf("\nThe right constructor");
knapsack = new int [NUMBER_OBJECTS];
for(int i=0; i<NUMBER_OBJECTS; i++)
{
if(knap == 1)
{
knapsack = 1;
}
else if(knap == 0)
{
knapsack = 0;
}
else
{
printf("Invalid Knapsack passed to constructor!");
printf("i = %d, value = %d", i, knap);
exit(1);
}
}


Using the definition of knapsack from above (i.e. as a bitset), this
code becomes something like:

KNode(knappy knap) : knapsack(knap) {
calculateWeights();
calculateValue();
crossoverType = randomCrossover();
}

Your copy ctor isn't entirely clear. Do you really need to recalculate
the weights and value in it? It appears that it can simply copy those in
the existing one. If that's so, you can simply skip defining it at all,
as the one the compiler will produce will work fine (once you've defined
knapsack and weights properly). Likewise with operator=; in fact, the
one you have right now almost certainly does NOT do what you want -- it
does a shallow copy, so you end up with two objects pointing to the same
knapsack and weights rather than having two independent copies of those.
Right now, KNodes also leak memory -- you don't have a ctor for KNode,
so the memory it allocates in its ctor is never freed. Fortunately, when
you redefine its pointer members as container types, you no longer have
to worry about that.
KNode * mutate(KNode * node, double prob)
{
printf("Inside mutator\n");
int * knapsack = node->getKnapsack();
int * kk = new int[NUMBER_OBJECTS];
for(int i=0; i<NUMBER_OBJECTS; i++)
{
double rand = generateDoubleRandomNumber();
if(rand < prob)
{
// invert
if(knapsack == 1)
{
kk=0;
}
else if(knapsack == 0)
{
kk=1;
}
else
{
printf("%d\n\n", knapsack);
printf("Invalid Knapsack");
exit(1);
}
}
}

KNode * nd = new KNode(kk);
return nd;
}


Using the prior definitions, this becomes something like:

KNode mutate(Knode const &node, double prob) {
knappy kk(node.knapsack);

for (int i=0; i<node.knapsack.size(); i++) {
double random = ;
if (generateDoubleRandomNumber() < prob)
kk.flip(i);
}
return KNode(kk);
}

I'd also consider re-defining this in general though -- 'mutate' sounds
like a verb -- i.e. that when you do something like "mutate(x)' it
should change the value of 'x'. Given what it really does, create_mutant
or something like that would probably be a better name.

I'll stop here with the specifics, and instead add a few general
comments: your code shows your Java background quite clearly -- in fact,
even if a C++ compiler will accept what you write, what you have is
still really more Java than C++.

My advice would be to treat the 'new' keyword as strictly forbidden, at
least for a while, until you're most accustomed to how C++ works. Right
now, you're using dynamic allocation when it's unnecessary, and leaking
memory all over everywhere. These problems should mostly evaporate if
you start to use containers from the standard library. Along with those,
you should look into using some of the standard algorithms -- for
example, you have a number of loops that could be replaced with
algorithsm such as std::accumulate.

Getting back to your original question, the problem is almost certainly
related to your (mis-)management of memory. My immediate advice would be
to ignore the existence of qsort, and use std::sort instead. With
careful use, qsort undoubtedly CAN do what you need -- but std::sort
will almost certainly do it more easily, and as a minor bonus, will
probably run quite a bit faster as well.
 
J

Jerry Coffin

[ a couple of errors in editing...]
Right now, KNodes also leak memory -- you don't have a ctor for KNode,

That should be 'dtor' rather than ctor.

[ ... ]
KNode mutate(Knode const &node, double prob) {
knappy kk(node.knapsack);

for (int i=0; i<node.knapsack.size(); i++) {
double random = ;

And this line shouldn't be there at all. There's also no real need to
use node.knapsack.size here -- kk.size works fine:

KNode mutate(Knode const &node, double prob) {
knappy kk(node.knapsack);

for (int i=0; i<kk.size(); i++)
if (generateDoubleRandomNumber() < prob)
kk.flip(i);
return KNode(kk);
}
 
K

KS

Getting back to your original question, the problem is almost certainly
related to your (mis-)management of memory. My immediate advice would be
to ignore the existence of qsort, and use std::sort instead. With
careful use, qsort undoubtedly CAN do what you need -- but std::sort
will almost certainly do it more easily, and as a minor bonus, will
probably run quite a bit faster as well.

Thanks for the detailed critique of the code. I have now switched to
STL (vector and std::sort()) and the original problem has been solved.
(Now it is complaining about bad parsing, which I can handle).
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top