Thread: std::sort with memory?

  1. #1
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,229

    std::sort with memory?

    Hi,
    Just wondering that, is there a version of std::sort in the STL that has memory (assuming std::sort doesn't)? The elements that I want to sort have relatively expensive operator<. Or do I have to make it myself? (eg, assign some kind of heuristic values to elements prior to calling std::sort, and sort base on that heuristic value instead)

    Thanks

  2. #2
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Ireland
    Posts
    8,446
    Quote Originally Posted by cyberfish View Post
    eg, assign some kind of heuristic values to elements prior to calling std::sort, and sort base on that heuristic value instead
    Yes. This would be a good solution, if you can afford it (the heuristics could itself be too heavy on your constructor, assuming that's where you would be calculating it).

    Another option I can think of is doing the heuristics within the sort operation itself. You create a function that does the calculation and feed it to std::sort through its version that takes a predicate.

    Others may come with even better solutions I'm sure
    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

  3. #3
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,229
    Thanks for your reply
    Another option I can think of is doing the heuristics within the sort operation itself. You create a member function that does the calculation and feed it to std::sort through it's version with a predicate.
    That is what I had in mind, but was hoping for an easier alternative =).

  4. #4
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Ireland
    Posts
    8,446
    Well, assuming you can't avoid an expensive operator< without some kind of heuristics, then that is probably the simplest way.

    When you mention "memory", I'm not sure what you mean though. If you want a sort operation that will first look somewhere if that operation was performed before and use those results instead, then I don't think you have anything on the standard library that does that directly.

    How to do it though depends on exactly what is that you are trying to sort.
    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

  5. #5
    and the hat of sweating
    Join Date
    Aug 2007
    Location
    Toronto, ON
    Posts
    3,545
    I'm not sure what you mean by "is there a version of std::sort in the STL that has memory"? Memory for what?
    Also, if sorting is expensive, one thing you might want to ask yourself is if you actually need to sort the entire range, or if one of the other types of sort would do the job. See "Use the right STL sort algorithm"

  6. #6
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,229
    I'm not sure what you mean by "is there a version of std::sort in the STL that has memory"? Memory for what?
    Memory as in something like this -
    if a < b and b < c, a < c will never be called. I want to keep the number of calls to my operator< to a minimum.

    Thanks for the link, I will certainly look into that.

  7. #7
    The larch
    Join Date
    May 2006
    Posts
    3,573
    I can't think how that would be achieved.

    Perhaps tell us what the objects represent, and think if there's a way to make the comparison operator less expensive.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  8. #8
    Registered User
    Join Date
    Sep 2006
    Posts
    835
    The sort criterion for std::sort must be a strict weak ordering - see

    http://en.wikipedia.org/wiki/Strict_weak_ordering

    so in particular it must be transitive. Therefore you can expect the implementation to take advantage of that. (If it wasn't transitive, you wouldn't be able to sort the elements anyway - if a<b, b<c, and c<a, there would be no way to sort the 3 elements.)

  9. #9
    The larch
    Join Date
    May 2006
    Posts
    3,573
    Yes, but to establish this ordering, the sort algorithm will do a lot more comparisons than n/2.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  10. #10
    Registered User
    Join Date
    Sep 2006
    Posts
    835
    Quote Originally Posted by anon View Post
    Yes, but to establish this ordering, the sort algorithm will do a lot more comparisons than n/2.
    To establish the ordering, ANY comparison sort will require O(N log N) comparisons, and std::sort is an efficient comparison sort implementation. The only way to do better is if one can do a non-comparison sort instead - see

    http://en.wikipedia.org/wiki/Comparison_sort

    Edit: I should have said O(N log N) worst-case - one might get lucky and be able to do it in O(N) in a particular case (for example if the elements are already sorted).
    Last edited by robatino; 02-21-2008 at 05:04 PM.

  11. #11
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Ireland
    Posts
    8,446
    Trying to beat the current sort algorithms doesn't seem like a productive idea, unless these were sequences with just a limited scope of possible values. If the op operator< is inadequate for any of the available algorithms, heuristics will handle the problem in a more timely fashion, I seem to believe.
    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

  12. #12
    and the hat of sweating
    Join Date
    Aug 2007
    Location
    Toronto, ON
    Posts
    3,545
    You could always switch to an associative container. Then the objects would always stay sorted...

  13. #13
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Just post your comparison operator. If its as bad as you make it out to be then I could pretty much guarantee some of us here could speed it up by many orders of magnitude.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  14. #14
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,229
    Thanks for your offer, really appreciated it. However, it is quite complicated as I am sorting a list of chess moves generated by my chess engine during its search in the order of likelihood to be a good move. The comparison operator does things like static exchange evaluation (count pieces from both sides attacking on the destination square to estimate material gain/lose), history heuristic (how many times has a move been proven useful in other parts of the search tree), and other minor criterias. Therefore, I think it would be too context-dependent for anyone to help just by looking at that function alone.

    Thanks

  15. #15
    Hurry Slowly vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,788
    It makes me wonder - do you need a sort or do you need just find a best move?
    All problems in computer science can be solved by another level of indirection,
    except for the problem of too many layers of indirection.
    – David J. Wheeler

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. available memory from task manager
    By George2 in forum Tech Board
    Replies: 10
    Last Post: 01-18-2008, 02:32 AM
  2. Replies: 4
    Last Post: 01-13-2008, 02:14 AM
  3. Question regarding Memory Leak
    By clegs in forum C++ Programming
    Replies: 29
    Last Post: 12-07-2007, 01:57 AM
  4. Memory problem with Borland C 3.1
    By AZ1699 in forum C Programming
    Replies: 16
    Last Post: 11-16-2007, 11:22 AM
  5. Shared Memory - shmget questions
    By hendler in forum C Programming
    Replies: 1
    Last Post: 11-29-2005, 02:15 AM