In article <11************ *********@p79g2 000cwp.googlegr oups.com>,
kn*******@gmail .com says...
>
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_CONSTRAI NTS = 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_constrai nts = 5;
int generateRandomN umber(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 GenerateRandomN umber(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_o bjectsknappy;
knappy knapsack;
You might also consider a vector<boolas 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<intweigh ts;
public:
KNode()
{
printf("\nShoul d 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_OBJECT S; i++)
{
if(knap[i] == 1)
{
knapsack[i] = 1;
}
else if(knap[i] == 0)
{
knapsack[i] = 0;
}
else
{
printf("Invalid Knapsack passed to constructor!");
printf("i = %d, value = %d", i, knap[i]);
exit(1);
}
}
Using the definition of knapsack from above (i.e. as a bitset), this
code becomes something like:
KNode(knappy knap) : knapsack(knap) {
calculateWeight s();
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_OBJECT S; i++)
{
double rand = generateDoubleR andomNumber();
if(rand < prob)
{
// invert
if(knapsack[i] == 1)
{
kk[i]=0;
}
else if(knapsack[i] == 0)
{
kk[i]=1;
}
else
{
printf("%d\n\n" , knapsack[i]);
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.knapsac k);
for (int i=0; i<node.knapsack .size(); i++) {
double random = ;
if (generateDouble RandomNumber() < 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.
--
Later,
Jerry.
The universe is a figment of its own imagination.
