CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Page 2 of 2 FirstFirst 12
Results 16 to 22 of 22

Thread: replace with sort algorithm

  1. #16
    Join Date
    May 2015
    Posts
    355

    Re: replace with sort algorithm

    Yes, looks like this is getting more complicated than i thought. (Basically with one array it was simpler to change to std:sort, but second array was added very recently, it gets complicated )

    So just exploring, so as you suggested it may not add value.

    Thanks a lot again for the inputs and help, i sometimes was going in wrong way (like extracting indices) and correcting me..

  2. #17
    Join Date
    May 2015
    Posts
    355

    Re: replace with sort algorithm

    Again,, thanks a lot kaud for the improved solution and help

  3. #18
    Join Date
    Feb 2017
    Posts
    579

    Re: replace with sort algorithm

    Quote Originally Posted by pdk5 View Post
    (Basically with one array it was simpler to change to std:sort, but second array was added very recently, it gets complicated )
    If the problem is that you want to co-sort the second array with the first, one way is to introduce a temporary std::vector of std:: pair.

    In each std:: pair you combine a PiInfo object with its corresponding MiInfo object. Then the std::vector is sorted according to order you want for PiInfo. Finally the records of the now sorted std:: pairs are copied back into the original arrays.

    This solution involves extra copying but copying is O(N) whereas sorting is O(N*logN) so the complexity stays the same. And maybe you can recover some of the copying overhead by selecting the parallel execution policy for std::sort.
    Last edited by wolle; November 12th, 2020 at 02:31 AM.

  4. #19
    Join Date
    May 2015
    Posts
    355

    Re: replace with sort algorithm

    thanks a lot wolle for the comments. Btw as our arrays are huge, so copying may become bottleneck for the performance. And also these structures are not very direct, they are hidden inside lot of templates , so bit messy to do those changes

  5. #20
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    7,319

    Re: replace with sort algorithm

    our arrays are huge
    The code you have will probably give the best performance. In 'simplifying' this, you are likely to have an impact on performance. In these sort of cases, I'd be thinking about performance over 'readability'.
    All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!

    C++17 Compiler: Microsoft VS2019 (16.8.2)

  6. #21
    Join Date
    May 2015
    Posts
    355

    Re: replace with sort algorithm

    Thanks kaud

  7. #22
    Join Date
    Feb 2017
    Posts
    579

    Re: replace with sort algorithm

    Quote Originally Posted by pdk5 View Post
    Btw as our arrays are huge, so copying may become bottleneck for the performance. And also these structures are not very direct, they are hidden inside lot of templates , so bit messy to do those changes
    Well, what I can see from the code in #1 you are copying already as part of the sorting process (swapping of records),

    Code:
    				{
    					PiInfo tmp = pIIInfo[(size_t)i];
    					pIIInfo[(size_t)i] = pIIInfo[(size_t)j];
    					pIIInfo[(size_t)j] = tmp;
    
    					if (pMInfo != nullptr)
    					{
    						MiInfo multi = pMInfo[(size_t)i];
    						pMInfo[(size_t)i] = pMInfo[(size_t)j];
    						pMInfo[(size_t)j] = multi;
    					}
    				}
    If this is the copying we are talking about and the problem is the co-sorting of pIIInfo and pMInfo and speed is inportant then I would suggest the following.

    First copy pIIInfo and pMInfo to two temporary std::vectors. Next fill an std:: vector<int> (the index vector) with integers from 0 up to the number of records - 1. Then sort the index vector based on the records of pIIInfo. Finally copy the temporary vectors back to pIIInfo and pMInfo according to the sorted index vector.

    Most of the copying and sorting, if not all of it, can be done in parallel by making use of the parallel_policy on containers. Furthermore the sorting swaps just integers and not pIIInfo and pMInfo records as before which should make it faster (especially if the records are large of course).

    This should be just a few lines of code using standard containers and standard sorting. The cost of swapping in the sort has been minimized and everything is done in parallel. It should be pretty fast. And finally who knows whether the current sort algorithm implementation is any good? It's hard to get Quicksort right even for an expert.
    Last edited by wolle; November 13th, 2020 at 05:02 PM.

Page 2 of 2 FirstFirst 12

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width




On-Demand Webinars (sponsored)