List Sorting Question

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::push_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

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

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

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

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?

Quote:

---

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

Quote:

---

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.

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.

Quote:

---

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 :D

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.

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.

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?

Quote:

---

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.

Quote:

---

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.

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.

Quote:

---

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

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.

O_o

It sounds to me like you are using the wrong tool for the job.

Can you give some more details about your use pattern? (I'm mostly interested in the number of elements you expect to add between using the sorted data, the range of the element values, and the expense of the comparison function.)

Quote:

---

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.

---

o_O

Depending on the distribution of your data, you may save a lot of time, depending on the sorting algorithm you need to use, by partially sorting the data as you go. (In effect, making a "skip list" of sorts.)

Quote:

---

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 mechanism of the iterators (for std::list<???>) aren't changed by the element type.

Quote:

---

Since my data needs to be sorted so frequently I guess I just have to wait for it to sort.

---

Yea. That screams "don't use a linked list" to me. If you are sorting more than you are adding elements, you are using the wrong data structure.

Quote:

---

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.

---

If he only needs the "shortest guy of the bunch", he only needs to store the "shortest guy of the bunch".

Soma

Quote:

---

Originally Posted by Polystyrene

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.

---

Yes I believe so, particularly when the number of items being inserted is a fair bit less than the number of items already inserted. Merging-in a sorted run being faster than merging those items in individually, is in fact the principle behind the Strand-Sort sorting algorithm.
Before I got to that sentence, this was in fact going to be my exact suggestion. This assumes a std::list is the best container for the job of course.

If your list is never allowed to have duplicates, then another option is to use a std::set instead of a std::list. The main difference being that it is always sorted. There's also multiset if you do have duplicates.

Quote:

---

Originally Posted by Polystyrene

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.

---

As it would. There is not much advantage in using lower_bound with iterators that are not random access. Its first step is to count the number of items in the range, i.e. evaluate std::distance(begin, end) which means iterating over the entire list. So it's not just that it may end up iterating over the entire list, it does explicitly iterate over the entire list before it even starts doing any comparisons. Typically even a linear search is faster than this would be. But if the comparison operator is far slower than iterating and the list is short enough, then it can be a win, but basically it was a poor suggestion.

Quote:

---

Originally Posted by whiteflags

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

---

I should clarify that. It just boils down to, don't sort the data it you don't need to access it in sorted order just yet. It does not means that it is faster to re-sort the whole thing each time. On the flipside, not all of the effort it sorting some of the data before it is needed sorted is lost, especialy if you dont throw away the information about which portion is already sorted.

Quote:

---

Originally Posted by whiteflags

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.

---

That's not the only way to know. A Big-Oh notation anaylsis shows that if the number of items being added is sufficiently less than the number of items already present, then it is faster. I've done this previously and submitted it as an optimisation to the Loki library authors some time ago for their assoc_vector class. It tends toward O(n), whereas a full sort would be O(n*logn).