Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > qsort - Segmentation Fault

Reply
Thread Tools

qsort - Segmentation Fault

 
 
KS
Guest
Posts: n/a
 
      08-14-2006

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.

KS

 
Reply With Quote
 
 
 
 
Victor Bazarov
Guest
Posts: n/a
 
      08-14-2006
KS wrote:
> 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
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask


 
Reply With Quote
 
 
 
 
KS
Guest
Posts: n/a
 
      08-14-2006

> 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

 
Reply With Quote
 
Thomas J. Gritzan
Guest
Posts: n/a
 
      08-14-2006
KS schrieb:
> 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-lit...t.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++.

--
Thomas
 
Reply With Quote
 
Jerry Coffin
Guest
Posts: n/a
 
      08-14-2006
In article <(E-Mail Removed). com>,
http://www.velocityreviews.com/forums/(E-Mail Removed) 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_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<int> weights;

> 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[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) {
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[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.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.

--
Later,
Jerry.

The universe is a figment of its own imagination.
 
Reply With Quote
 
Jerry Coffin
Guest
Posts: n/a
 
      08-14-2006
In article <(E-Mail Removed)>,
(E-Mail Removed) says...

[ 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);
}

--
Later,
Jerry.

The universe is a figment of its own imagination.
 
Reply With Quote
 
KS
Guest
Posts: n/a
 
      08-15-2006

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


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).

 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Segmentation fault using Firefox 15.0.2 Keith Lee Firefox 3 04-29-2006 05:45 PM
Xerces on Solaris - Segmentation fault ldvmbs@gmail.com XML 0 05-16-2005 07:21 AM
Xerces XML Parser Segmentation fault with Java Pud XML 0 11-06-2003 05:07 PM
Intel Xeon + Linux + IBM sdk 1.3.1 - getting Segmentation fault Alex Hunsley Java 17 11-06-2003 12:12 AM
Re: segmentation fault exception handling Ivan Vecerina C++ 0 06-29-2003 10:56 PM



Advertisments