List Sorting Question

This is a discussion on List Sorting Question within the C++ Programming forums, part of the General Programming Boards category; I have a program that relies on a sorted list of data structures. During program execution the list is initially ...

  1. #1
    Registered User
    Join Date
    Aug 2010
    Posts
    6

    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: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
    Last edited by Polystyrene; 08-27-2010 at 02:05 PM.

  2. #2
    Programming Wraith GReaper's Avatar
    Join Date
    Apr 2009
    Location
    Greece
    Posts
    1,602
    Why don't you make a function "list::addSorted(...)" or something like that to emmediately put the element in the right position?
    Devoted my life to programming...

  3. #3
    Programming Wraith GReaper's Avatar
    Join Date
    Apr 2009
    Location
    Greece
    Posts
    1,602
    But now that i think about it, what you're talking about isn't even a list! It's an array like STL vector.
    Devoted my life to programming...

  4. #4
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,526
    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().

  5. #5
    Registered User
    Join Date
    Aug 2010
    Posts
    6
    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?

  6. #6
    Programming Wraith GReaper's Avatar
    Join Date
    Apr 2009
    Location
    Greece
    Posts
    1,602
    Quote Originally Posted by Polystyrene View Post
    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!!!
    Devoted my life to programming...

  7. #7
    Registered User
    Join Date
    Aug 2010
    Posts
    6
    Quote Originally Posted by Sipher View Post
    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.

  8. #8
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,526
    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.

  9. #9
    Programming Wraith GReaper's Avatar
    Join Date
    Apr 2009
    Location
    Greece
    Posts
    1,602
    Quote Originally Posted by Polystyrene View Post
    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
    Devoted my life to programming...

  10. #10
    Registered User
    Join Date
    Aug 2010
    Posts
    6
    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.

  11. #11
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,526
    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.

  12. #12
    Registered User
    Join Date
    Aug 2010
    Posts
    6
    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?
    Last edited by Polystyrene; 08-27-2010 at 04:05 PM.

  13. #13
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,526
    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.
    Last edited by whiteflags; 08-27-2010 at 04:26 PM.

  14. #14
    Registered User
    Join Date
    Aug 2010
    Posts
    6
    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.

  15. #15
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,526
    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.

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. linked list question
    By mikeman in forum C Programming
    Replies: 1
    Last Post: 11-30-2008, 12:56 PM
  2. List Question
    By ConsulVortex in forum C++ Programming
    Replies: 3
    Last Post: 01-14-2006, 03:38 AM
  3. Linked List Help
    By CJ7Mudrover in forum C Programming
    Replies: 9
    Last Post: 03-10-2004, 09:33 PM
  4. compiler build error
    By KristTlove in forum C++ Programming
    Replies: 2
    Last Post: 11-30-2003, 09:16 AM

Tags for this Thread


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21