Make run faster?

[Hellmath01]

Hello, this program is using merg sort to sort a very complicated data file. This program works beautifully up 100,000 events. ( each event contains lots of information). However, when i go up to 1 million. It seems not to work. I let it run for 36 hours once and... nothing. Is there a way to allocate more memory to this program? or make it run faster?

#include <stdio.h>
#include <iostream>
#include <fstream>
#include <math.h>
#include <string.h>

using namespace std;
class list_trackNode
{
public:
list_trackNode() {next=NULL; prev=NULL;}

double x, y, z, KinE, dE;
list_trackNode *next, *prev;



};
class list_node
{
public:
list_node() {next=NULL; prev=NULL; trackData=NULL;}
// list_node() {partType="\0"; next=NULL; prev=NULL;}
char partType[11];
int Nsteps;
list_node *next, *prev;
list_node *sort(list_node *list, int Nele);
list_trackNode *trackData;



};


list_node * list_node::sort(list_node *list, int Nele) {

list_node *bhalf, *mergStart = NULL, *mergEnd = NULL;
list_node *ahalf, *temp = NULL;
int i =0, j = 0;

//cout << "In sort at top." << endl;

if( Nele > 1) //divide the list in half and sort each half through recursive calls to 'sort'
{
bhalf = list;

//set the pointer 2half to the 2nd half of the list
for(i =0; i < ceil(Nele/2); i++)
{
bhalf = bhalf->next;

}

//cout << "Calling ahalf sort with " << ceil(Nele/2) << " elements. " << list->n << " is the first." << endl;
ahalf = sort( list, ceil(Nele/2));
//cout << "Done with ahalf sort." << ahalf->n << endl;

//cout << "Calling bhalf sort with " << Nele-ceil(Nele/2) << " elements. " << bhalf->n << " is the first." << endl;

bhalf = sort( bhalf, Nele-ceil(Nele/2));
//cout << "Done with bhalf sort." << bhalf->n << endl;


}
else
{
//there is only 1 element in this list, return its pointer doing nothing.
//cout << "Only 1 element in list and it is " << list->partType << "." << endl;
return list;
}

//print out the lists and their pointers.
/* for(i = 0; i < ceil(Nele/2); i++) {
if (ahalf != NULL) {
cout << "ahalf " << i << " is " << ahalf->n << ".";
if(ahalf->next != NULL) {
cout << " next is " << (ahalf->next)->n;
}
else {
cout << " next is NULL" << endl;
}
if(ahalf->prev != NULL) {
cout << " and prev is " << (ahalf->prev)->n << "." << endl;
}
else {
cout << " and prev is NULL." << endl;
}
}
else {
cout << "ahalf is NULL." << endl;
}
}

for(i = 0; i < Nele - ceil(Nele/2); i++) {
if (bhalf != NULL) {
cout << "bhalf " << i << " is " << bhalf->n << ".";
if(bhalf->next != NULL) {
cout << " next is " << (bhalf->next)->n;
}
else {
cout << " next is NULL" << endl;
}
if(bhalf->prev != NULL) {
cout << " and prev is " << (bhalf->prev)->n << "." << endl;
}
else {
cout << " and prev is NULL." << endl;
}
}
else {
cout << "bhalf is NULL." << endl;
}
}
*/
//Finish with Diagnostic couts.

//merge the 1st and 2nd half of the lists.
i=0; j = 0;
//cout << "entering the Merge!!" << endl;
while(i < ceil(Nele/2) && j < Nele - ceil(Nele/2))
{
// if(ahalf->partType <= bhalf->partType) // something like strcmp
if(strcmp(ahalf->partType, bhalf->partType) <=0) // something like strcmp
{
// cout << ahalf->partType << " is less than " << bhalf->partType << endl;
if(mergStart == NULL) {
mergStart = ahalf;
mergEnd = ahalf;
if( bhalf->prev == NULL) {
ahalf->prev = NULL;} // want to delete
//add an if that checks if bhalf->prev is NULL, if so, make ahalf-> prev NULL;
}
else {
ahalf->prev = mergEnd;
mergEnd->next = ahalf;
mergEnd = ahalf;
}
ahalf = ahalf->next;
i++;
// cout << "Done with adding ahalf element." << endl;

}

else{
// cout << ahalf->partType << " is greater than " << bhalf->partType << endl;
if(mergStart == NULL) {
mergStart = bhalf;
mergEnd = bhalf;
if(ahalf->prev == NULL) {
bhalf->prev = NULL;
}// want to delete
//add an if that checks if ahalf->prev is NULL, if so, make bhalf-> prev NULL;
}
else {
bhalf->prev = mergEnd;
mergEnd->next = bhalf;
mergEnd = bhalf;
}
bhalf = bhalf->next;
j++;
// cout << "Done with adding bhalf element." << endl;
}
}

if(i < ceil(Nele/2)){

ahalf->prev = mergEnd;
mergEnd->next = ahalf;
// cout << "After Merge, adding " << (mergEnd->next)->partType << " to the list from ahalf." << endl;
}
else{
bhalf->prev =mergEnd;
mergEnd->next = bhalf;
// cout << "After Merge, adding " << (mergEnd->next)->partType << " to the list from bhalf." << endl;
}
//set the last node's next pointer to NULL.
temp = mergStart;
for (i = 0; i < Nele-1; i++) { temp = temp->next; }
temp->next = NULL;
//completed the merge

//print the merged list
temp = mergStart;
for(i = 0; i < Nele; i++) {
if (temp != NULL) {
// cout << "list element " << i << " is " << temp->partType<< ".";
if(temp->next != NULL) {
// cout << " next is " << (temp->next)->partType;
}
else {
// cout << " next is NULL" << endl;
}
if(temp->prev != NULL) {
// cout << " and prev is " << (temp->prev)->partType << "." << endl;
}
else {
// cout << " and prev is NULL." << endl;
}
}
else {
// cout << "mergStart is NULL." << endl;
}
temp=temp->next;
}

return mergStart;


}

int main()

[Hippogriff]

Edit your post to use [ code] [ /code] tags so we can read it easily.

Guessing this is some sort of assignment otherwise you will have a hard time beating std::sort.

[helios]

Merge sort isn't appropriate to sort sequences with large elements, since every element needs to be copied a logarithmic number of times.

[ne555]

¿copy? you just need to adjust pointers.

[helios]

Oh, it's a linked list. Never mind, then.

[Hellmath01]

here is an edit version. formatting still came out weird. oh well.


#include <stdio.h>
#include <iostream>
#include <fstream>
#include <math.h>
#include <string.h>

using namespace std;
class list_trackNode
{
public:
list_trackNode() {next=NULL; prev=NULL;}

double x, y, z, KinE, dE;
list_trackNode *next, *prev;



};
class list_node
{
public:
list_node() {next=NULL; prev=NULL; trackData=NULL;}
// list_node() {partType="\0"; next=NULL; prev=NULL;}
char partType[11];
int Nsteps;
list_node *next, *prev;
list_node *sort(list_node *list, int Nele);
list_trackNode *trackData;



};


list_node * list_node::sort(list_node *list, int Nele) {

list_node *bhalf, *mergStart = NULL, *mergEnd = NULL;
list_node *ahalf, *temp = NULL;
int i =0, j = 0;

//cout << "In sort at top." << endl;

if( Nele > 1) //divide the list in half and sort each half through recursive calls to 'sort'
{
bhalf = list;

//set the pointer 2half to the 2nd half of the list
for(i =0; i < ceil(Nele/2); i++)
{
bhalf = bhalf->next;

}

//cout << "Calling ahalf sort with " << ceil(Nele/2) << " elements. " << list->n << " is the first." << endl;
ahalf = sort( list, ceil(Nele/2));
//cout << "Done with ahalf sort." << ahalf->n << endl;

//cout << "Calling bhalf sort with " << Nele-ceil(Nele/2) << " elements. " << bhalf->n << " is the first." << endl;

bhalf = sort( bhalf, Nele-ceil(Nele/2));
//cout << "Done with bhalf sort." << bhalf->n << endl;


}
else
{
//there is only 1 element in this list, return its pointer doing nothing.
//cout << "Only 1 element in list and it is " << list->partType << "." << endl;
return list;
}

//print out the lists and their pointers.
/* for(i = 0; i < ceil(Nele/2); i++) {
if (ahalf != NULL) {
cout << "ahalf " << i << " is " << ahalf->n << ".";
if(ahalf->next != NULL) {
cout << " next is " << (ahalf->next)->n;
}
else {
cout << " next is NULL" << endl;
}
if(ahalf->prev != NULL) {
cout << " and prev is " << (ahalf->prev)->n << "." << endl;
}
else {
cout << " and prev is NULL." << endl;
}
}
else {
cout << "ahalf is NULL." << endl;
}
}

for(i = 0; i < Nele - ceil(Nele/2); i++) {
if (bhalf != NULL) {
cout << "bhalf " << i << " is " << bhalf->n << ".";
if(bhalf->next != NULL) {
cout << " next is " << (bhalf->next)->n;
}
else {
cout << " next is NULL" << endl;
}
if(bhalf->prev != NULL) {
cout << " and prev is " << (bhalf->prev)->n << "." << endl;
}
else {
cout << " and prev is NULL." << endl;
}
}
else {
cout << "bhalf is NULL." << endl;
}
}
*/
//Finish with Diagnostic couts.

//merge the 1st and 2nd half of the lists.
i=0; j = 0;
//cout << "entering the Merge!!" << endl;
while(i < ceil(Nele/2) && j < Nele - ceil(Nele/2))
{
// if(ahalf->partType <= bhalf->partType) // something like strcmp
if(strcmp(ahalf->partType, bhalf->partType) <=0) // something like strcmp
{
// cout << ahalf->partType << " is less than " << bhalf->partType << endl;
if(mergStart == NULL) {
mergStart = ahalf;
mergEnd = ahalf;
if( bhalf->prev == NULL) {
ahalf->prev = NULL;} // want to delete
//add an if that checks if bhalf->prev is NULL, if so, make ahalf-> prev NULL;
}
else {
ahalf->prev = mergEnd;
mergEnd->next = ahalf;
mergEnd = ahalf;
}
ahalf = ahalf->next;
i++;
// cout << "Done with adding ahalf element." << endl;

}

else{
// cout << ahalf->partType << " is greater than " << bhalf->partType << endl;
if(mergStart == NULL) {
mergStart = bhalf;
mergEnd = bhalf;
if(ahalf->prev == NULL) {
bhalf->prev = NULL;
}// want to delete
//add an if that checks if ahalf->prev is NULL, if so, make bhalf-> prev NULL;
}
else {
bhalf->prev = mergEnd;
mergEnd->next = bhalf;
mergEnd = bhalf;
}
bhalf = bhalf->next;
j++;
// cout << "Done with adding bhalf element." << endl;
}
}

if(i < ceil(Nele/2)){

ahalf->prev = mergEnd;
mergEnd->next = ahalf;
// cout << "After Merge, adding " << (mergEnd->next)->partType << " to the list from ahalf." << endl;
}
else{
bhalf->prev =mergEnd;
mergEnd->next = bhalf;
// cout << "After Merge, adding " << (mergEnd->next)->partType << " to the list from bhalf." << endl;
}
//set the last node's next pointer to NULL.
temp = mergStart;
for (i = 0; i < Nele-1; i++) { temp = temp->next; }
temp->next = NULL;
//completed the merge

//print the merged list
temp = mergStart;
for(i = 0; i < Nele; i++) {
if (temp != NULL) {
// cout << "list element " << i << " is " << temp->partType<< ".";
if(temp->next != NULL) {
// cout << " next is " << (temp->next)->partType;
}
else {
// cout << " next is NULL" << endl;
}
if(temp->prev != NULL) {
// cout << " and prev is " << (temp->prev)->partType << "." << endl;
}
else {
// cout << " and prev is NULL." << endl;
}
}
else {
// cout << "mergStart is NULL." << endl;
}
temp=temp->next;
}

return mergStart;


}

int main()

[dhayden]

When posting, please put code in code tags. Highlight the code and click the <> button to the right of the edit window. Here is your code with the debugging stuff removed, indented and tagged. See more comments below.

#include <stdio.h>
#include <iostream>
#include <fstream>
#include <math.h>
#include <string.h>

using namespace std;
class list_trackNode
{
  public:
    list_trackNode()
    {
	next = NULL;
	prev = NULL;
    }

    double x, y, z, KinE, dE;
    list_trackNode *next, *prev;

};
class list_node
{
  public:
    list_node()
    {
	next = NULL;
	prev = NULL;
	trackData = NULL;
    }
// list_node() {partType="\0"; next=NULL; prev=NULL;}
    char partType[11];
    int Nsteps;
    list_node *next, *prev;
    list_node *sort(list_node * list, int Nele);
    list_trackNode *trackData;

};

list_node *
list_node::sort(list_node * list, int Nele)
{

    list_node *bhalf, *mergStart = NULL, *mergEnd = NULL;
    list_node *ahalf, *temp = NULL;
    int i = 0, j = 0;

    if (Nele > 1)				 //divide the list in half and sort each half through recursive calls to 'sort'
    {
	bhalf = list;

	//set the pointer 2half to the 2nd half of the list
	for (i = 0; i < ceil(Nele / 2); i++) {
	    bhalf = bhalf->next;

	}

	ahalf = sort(list, ceil(Nele / 2));
	bhalf = sort(bhalf, Nele - ceil(Nele / 2));

    } else {
	//there is only 1 element in this list, return its pointer doing nothing.
	return list;
    }

    //Finish with Diagnostic couts.

    //merge the 1st and 2nd half of the lists.
    i = 0;
    j = 0;
    while (i < ceil(Nele / 2) && j < Nele - ceil(Nele / 2)) {
	if (strcmp(ahalf->partType, bhalf->partType) <= 0)	// something like strcmp
	{
	    if (mergStart == NULL) {
		mergStart = ahalf;
		mergEnd = ahalf;
		if (bhalf->prev == NULL) {
		    ahalf->prev = NULL;
		}				 // want to delete
	    } else {
		ahalf->prev = mergEnd;
		mergEnd->next = ahalf;
		mergEnd = ahalf;
	    }
	    ahalf = ahalf->next;
	    i++;

	}

	else {
	    if (mergStart == NULL) {
		mergStart = bhalf;
		mergEnd = bhalf;
		if (ahalf->prev == NULL) {
		    bhalf->prev = NULL;
		}				 // want to delete
	    } else {
		bhalf->prev = mergEnd;
		mergEnd->next = bhalf;
		mergEnd = bhalf;
	    }
	    bhalf = bhalf->next;
	    j++;
	}
    }

    if (i < ceil(Nele / 2)) {

	ahalf->prev = mergEnd;
	mergEnd->next = ahalf;
    } else {
	bhalf->prev = mergEnd;
	mergEnd->next = bhalf;
    }

    //set the last node's next pointer to NULL.
    temp = mergStart;
    for (i = 0; i < Nele - 1; i++) {
	temp = temp->next;
    }
    temp->next = NULL;

//completed the merge

    temp = mergStart;
    for (i = 0; i < Nele; i++) {
	if (temp != NULL) {
	    if (temp->next != NULL) {
	    } else {
	    }
	    if (temp->prev != NULL) {
	    } else {
	    }
	} else {
	}
	temp = temp->next;
    }

    return mergStart;

}

Lines 52 & 70: Although the compiler might optimize it out, you precompute the sizes here rather than calling ceil() each time through the list.

Line 76: Why does bhalf->prev matter?
Line 93: Why does ahalf->prev matter?
LInes 117-119. You are looping through all nel elements again. Why not start at MergeEnd and go only as far as necessary? You can compute the right number of elements to add in lines 106-113

Lines 124-136: You're going through the list again, even though you don't print out anything. Consider ifdef'ing this whole thing out.

General: When you exit the loop, MergeStart->prev points to who-knows-where.