Home > Web Site Updates > CSortedArray / CSortedArrayEx v1.43

CSortedArray / CSortedArrayEx v1.43

November 7, 2010

Just to let everyone know that v1.43 of CSortedArray / CSortedArrayEx has been released. Updates for this version include:

  • Sort method now internally uses std::sort for sorting. This leads to dramatic improvements as the size of the array increases. It also means that issues with stack sizes due to recursion are now gone. Here is some before and after figures in ms for sorting an array of integers as obtained from the sample app (Note please do not compare the absolute values from one row to another as I shrunk down the number of array loops to keep the measured times reasonable as the array element size increased):
    Elements   Before (Function pointer array) Before (Functor) After (Function Pointer array) After (Functor)
    100 34 7 x2.125 6 (x1.16)
    1000 517 176 295 (x1.75) 84 (x2.09)
    10000 7896 2398 3525 (x2.23) 1098 (x2.18)
    100000 2696 529 336 (x8.03) 97 (x5.45)
    1000000 21017 3284 378 (x55) 125 (x26)
    10000000 208768 30605 899 (x232) 458 (x66)

    I believe the reason we see a dramatic improvement in performance as the array size increases is the fact that std::sort uses an introsort algorithm (which is a quicksort which switches to a heapsort when the recursion reaches a certain depth). The more expert C++ developers out there may ask why not just use the standard STL collection classes instead of the old style MFC CArray classes. In my case, many of my classes are pure MFC classes and at the time of their initial development the MFC classes were the number one choice. Now if you are writing new code it really does make sense to use the STL classes but it is still nice to have the familiarity of the MFC collection classes with the performance of their STL brethren.

  • StableSort method now internally uses std::stable_sort. Again this has lead to pretty substantial performance improvements as the size of the array increases (Again note please do not compare the absolute values from one row to another as I shrunk down the number of array loops to keep the measured times reasonable as the array element size increased):
    Elements   Before (Function pointer array) Before (Functor) After (Function Pointer array) After (Functor)
    100 249 80 246 (x1.01) 109 (x0.773)
    1000 1005 274 275 (x3.65) 120 (x2.28)
    10000 913 229 45 (x20.29) 13 (x17.61)
    50000 22587 5655 172 (x131) 74 (x76)
    100000 90484 22683 379 (x238) 154 (x147)
    300000 81606 20420 111 (x735) 48 (x425)
  • Advertisements
    Categories: Web Site Updates
    %d bloggers like this: