trjhtr

My teacher gave us an exercise. We have to sort as quickly as possible. The fastest one gets a reward. On my own system, I am sorting 125000 words within 1.2 seconds. On my teacher's system that is 0.6s.

In my main.cpp I wrote the following code:

#include "FileStructure.h"
#include "Value.h"

template<typename T>
T* Merge(T* firstNode, T* secondNode)

 if (!firstNode) return secondNode;
 else if (!secondNode) return firstNode;

 else if (firstNode->getText() >= secondNode->getText())
 
 firstNode->setPrev(Merge(firstNode->getPrev(), secondNode));
 return firstNode;
 
 else
 
 secondNode->setPrev(Merge(firstNode, secondNode->getPrev()));
 return secondNode;
 


template<typename T>
T* Split(T* my_node)

 if (!my_node 

template<typename T>
T* MergeSort(T* my_node)

 if (!my_node) return NULL;
 else if (!my_node->getPrev()) return my_node;
 return Merge(MergeSort(my_node), MergeSort(Split(my_node)));



int main(void)

 FileStructure f;
 Key* head = new Key();
 f.loadFile("data/gibberish.bin", *head);

 head = MergeSort(head);
 Key* tempHead = head; //values

 while (tempHead)
 
 tempHead->setValuePtr(MergeSort(tempHead->getValuePtr()));
 tempHead = tempHead->getPrev();
 
 // save sorted data into a new file called sorted.bin
 f.saveFile(*head, "sorted.bin");

 delete head;
 //newHead = NULL;

 return 0;

The key.h and value.h only have getters and setters. Key also has another method called AddValue().

This one is:

void Key::addValue(std::string word)

 if (key == word.substr(0, 2))
 
 Value *temp = valueTail;
 valueTail = new Value(word);
 valueTail->setPrev(temp);
 return;
 
 else if (prevKey)
 
 prevKey->addValue(word);
 return;
 
 prevKey = new Key();
 prevKey->setText(word.substr(0, 2));
 prevKey->valueTail = new Value(word);

All the other functions are inline functions.
As you can see it's dirty code. I removed as much as possible variables. I think it can be faster, but I don't know how.

I ran Gprof on my code:

Each sample counts as 0.01 seconds.
 % cumulative self self total 
 time seconds seconds calls us/call us/call name 
 72.73 0.24 0.24 Key::addValue(std::string)
 12.12 0.28 0.04 151883 0.26 0.26 Value* Split<Value>(Value*)
 9.09 0.31 0.03 151883 0.20 0.20 Value* Merge<Value>(Value*, Value*)
 6.06 0.33 0.02 522 38.31 38.31 Value::~Value()
 0.00 0.33 0.00 522 0.00 0.00 Key* Merge<Key>(Key*, Key*)
 0.00 0.33 0.00 522 0.00 0.00 Key* Split<Key>(Key*)

Help me out please!
Btw: I have no memory leaks, thanks to valgrind.

I had a similar contest in high school. I decided to win in every category :)

In modern architectures, linked lists are slow. See https://www.youtube.com/watch?v=YQs6IC-vgmo for example. Does it need to be a linked list? Does it need to be a merge sort in particular? I can advice more specifically if you update your post to add that info.

Even though it would not be a legal entry, you might try using a std::vector<std::string> and just calling std::sort and using that speed as a baseline!

Btw: I have no memory leaks, thanks to valgrind.

That is a heroic effort to achieve something that should normally be the case in C++. Use unique_ptr and general RAII techniques, and memory leaking in a single-threaded program is simply not an issue to worry about! That is, you are making it too hard.

Read through and bookmark the C++ Standard Guidelines. Numbers I note later are citations from this.

Use the proper #include files. You have a couple project-specific includes, but no standard library stuff; maybe you are not using anything from the library, not even language-support features? But that will change if you improve the code.

template<typename T>
T* Merge(T* firstNode, T* secondNode)

 if (!firstNode) return secondNode;
 else if (!secondNode) return firstNode;

 else if (firstNode->getText() >= secondNode->getText())
 
 firstNode->setPrev(Merge(firstNode->getPrev(), secondNode));
 return firstNode;
 
 else
 
 secondNode->setPrev(Merge(firstNode, secondNode->getPrev()));
 return secondNode;
 

So let’s see… you are taking a couple node pointers, not any kind of abstraction as the linked list as a collection? I understand if this is the kind of stuff you are learning, but it is hard to follow as it is not “normal” programming.

So far, I see some good habits. C++ (not C) style placement of the *, use of contextual conversion to bool as a truth test of the pointer, putting quick-return tests at the very top, in a compact manner … all very mature style!

The logic looks like straight functional programming style. Good for Haskell, not good for C++. I don’t think the compiler can do tail recursion elimination here. You will run out of stack space if your list is long!

Writing this as a loop rather than recursively will make it faster and avoid the size limit.

template<typename T>
T* Split(T* my_node)

 if (!my_node 

Forget that the NULL macro ever existed! Banish it from your memory. C++ has the special nullptr value.

Again, I see a good habit: declared secondNode when you were ready to initialize it.

template<typename T>
T* MergeSort(T* my_node)

 if (!my_node) return NULL;
 else if (!my_node->getPrev()) return my_node;
 return Merge(MergeSort(my_node), MergeSort(Split(my_node)));

As before, nullptr, not NULL.

It looks like you are peeling off one node at a time, not cutting the list in half. If I follow this right, you have implemented an insertion sort where you need a linear search over the list to find the insertion position, not a proper merge sort. Each item will have to compare (on average) with half of the items processed already. This is O(n²). A proper merge will compare once for each item in the shorter list, recursively sorting the half-lists first. That is O(n log n).

Now I’m sure you know that the “big O” will trump the linear speedup of any of the steps!

int main(void)

 FileStructure f;
 Key* head = new Key();
 f.loadFile("data/gibberish.bin", *head);

 head = MergeSort(head);
 Key* tempHead = head; //values

 while (tempHead)
 
 tempHead->setValuePtr(MergeSort(tempHead->getValuePtr()));
 tempHead = tempHead->getPrev();
 
 // save sorted data into a new file called sorted.bin
 f.saveFile(*head, "sorted.bin");

 delete head;
 //newHead = NULL;

 return 0;

Don’t write (void) for an empty parameter list! Stroustrup calls that “an abomination”. It is supported so that it can read C header files; but you should not write that in C++, ever.

 Key* head = new Key();

⧺C.149 — no naked new or delete.

You should probably make this a unique_ptr as a drop-in replacement without otherwise changing the architecture.

 while (tempHead)
 
 tempHead->setValuePtr(MergeSort(tempHead->getValuePtr()));
 tempHead = tempHead->getPrev();
 

I don’t understand that part. You sorted with the call to MergeSort, right? Why do you have to back up a node and sort it again? This might be a work-around for a problem with the sorting or the data structure.

Then you treat the original node, head, as the sorted list’s head? So what was the deal with tempHead?

void Key::addValue(std::string word)

 if (key == word.substr(0, 2))
 
 Value *temp = valueTail;
 valueTail = new Value(word);
 valueTail->setPrev(temp);
 return;
 
 else if (prevKey)
 
 prevKey->addValue(word);
 return;
 
 prevKey = new Key();
 prevKey->setText(word.substr(0, 2));
 prevKey->valueTail = new Value(word);

You are taking the string word by value, copying it into the function. You don’t modify word, right?

I don’t know what Value is, or why you don’t just store the std::string in your nodes.

substr is not a normal or good way to manipulate strings in the standard library. If I knew what you were trying to do, I could advise how it should naturally be done.

Good luck to you! Keep at it.

Get rid of the recursion. Transform all into loops. Look up "bottom-up mergesort", where you start by merging single nodes into sorted pairs, then merging the sorted pairs into sorted quadruples, then merging those, continuing until you're left with one -- now sorted -- list.

Using one extra head node in front of the whole list will greatly simplify your coding. For an example, see Wikipedia for "tail recursion modulo cons".