List Sorting Question

**Polystyrene** · 08-27-2010

I have a program that relies on a sorted list of data structures. During program execution the list is initially sorted using list::sort however I continually need to add new unsorted data structures into the list. I initially just used the list:ush_back function to append all of the additional data structures to the end of the list and then run sort on the entire list. My question is would it be faster to make a smaller list containing the new data structures, sort it, and then merge it into the larger list. This adding new data and sorting is by far the slowest part of my program and I am looking for ways to speed it up. Any suggestions would be greatly appreciated

**GReaper** · 08-27-2010

Why don't you make a function "list::addSorted(...)" or something like that to emmediately put the element in the right position?

**GReaper** · 08-27-2010

But now that i think about it, what you're talking about isn't even a list! It's an array like STL vector.

**whiteflags** · 08-27-2010

Provided that your list is strictly ordered by < you can do sorted insertion this way:

Code:

#include <algorithm>
#include <list>

std::list<Obj>::iterator putItHere = std::lower_bound( yourList.begin( ) , yourList.end( ) , newObj );


yourList.insert( putItHere , newObj );

Ordering using a comparison function is also possible -- it's just one more argument at the end of lower_bound().

**Polystyrene** · 08-27-2010

I thought about just putting it into position immediately, but I would still have to find where to put it using a comparison function. Should that method be faster?

**GReaper** · 08-27-2010

Originally Posted by Polystyrene

I thought about just putting it into position immediately, but I would still have to find where to put it using a comparison function. Should that method be faster?

Certainly!!!

**Polystyrene** · 08-27-2010

Originally Posted by Sipher

But now that i think about it, what you're talking about isn't even a list! It's an array like STL vector.

To clarify, it is an STL list of data structures. Think of it like this, list<struct> myList. And I do use a typical comparison function in order to compare two structures when using sort.

**whiteflags** · 08-27-2010

Well it would happen in linear time, but that's faster than most sorts, including the one list uses.

Linear time means that lower_bound will take longer as the number of elements grows. In the worst case, it has to traverse to the end of the list because the new element belongs at the end of the list.

It's about as good as you can do without doing any real work.

**GReaper** · 08-27-2010

Originally Posted by Polystyrene

To clarify, it is an STL list of data structures. Think of it like this, list<struct> myList. And I do use a typical comparison function in order to compare two structures when using sort.

Oh, sorry, i confused it with Linked List

**Polystyrene** · 08-27-2010

Ok so I tried using the lower_bound function to find the iterator where it should be inserted as whiteflags suggested. However, the program becomes very slow and according to the profiler I am spending 70% of my time performing the iterator++ operator.

**whiteflags** · 08-27-2010

Maybe you should just sort exactly when you need sorted data, and not care the rest of the time. Or find a way to work with unsorted data.

**Polystyrene** · 08-27-2010

The list needs to be sorted after each set of new data is added to the list, so it is already sorting right before the sorted data is needed. If unsorted data is used, I would have to go through the list to find the smallest one which would require traversing the whole list every single time.

It appears that the lower_bound function, although it scales linearly is not very fast due to the slowness of the ++ operator on the iterator. Maybe the ++ operator is very fast when you have a list of say integers, but it seems to be really slow when you have a list of data structures.

The original question still remains. Is it faster to sort a small list and merge it into a larger already sorted larger list or append the unsorted data onto the end of the large list and then sort the large list?

**whiteflags** · 08-27-2010

The list needs to be sorted after each set of new data is added to the list, so it is already sorting right before the sorted data is needed.

The whole point is that it is faster to sort all the unsorted data once than to ensure that the list is always sorted.

The original question still remains. Is it faster to sort a small list and merge it into a larger already sorted larger list or append the unsorted data onto the end of the large list and then sort the large list?

To loosely answer your question merging two lists and getting a sorted list out of it is a sort, and would be as fast as most other sorts. The only way to know in this case is to profile both strategies that you mention.

And by the way don't kill yourself squeezing blood from a turnip. Sorting a million elements is only going to be fast enough, and still a time sink.

**Polystyrene** · 08-27-2010

Thanks for the help and input. I think you are right that there may not be much of a time difference between the two and that sort is just going to have to take as long as it takes. Since my data needs to be sorted so frequently I guess I just have to wait for it to sort.

**whiteflags** · 08-27-2010

It appears that the lower_bound function, although it scales linearly is not very fast due to the slowness of the ++ operator on the iterator. Maybe the ++ operator is very fast when you have a list of say integers, but it seems to be really slow when you have a list of data structures

By the way I wanted to point out that this does not make much sense either. Spending 70% of your time doesn't mean that increment itself is slow, it's just means that you are doing it so often. If you can think of a way to do sorted insertion without examining the list, then, yes, that would be very fast.

I honestly think you should try my second piece of advice. Sorting once means sorting after you've compiled the entire list. I also mentioned working with unsorted data. If you're just trying to pick the shortest guy of the bunch or something, you can also brute force that in linear time, after you compile the list, and that is faster than most sorts.

Thread: List Sorting Question

Thread Tools

Search Thread

Display

List Sorting Question

Similar Threads

linked list question

List Question

Linked List Help

compiler build error

Tags for this Thread