Форсаж для стандартного sort из Visual C++ 6.0

Где-то на форумах мне попадались жалобы на медленность работы стандартного sort из Visual C++ 6.0. Но вот довелось столкнуться с этим лично. Выяснилось, что если в сортируемом массиве есть много одинаковых элементов, то sort начинает очень сильно тормозить. Уж не знаю, то ли это недостаток алгоритма, то ли глюк реализации.

Удалось мне придумать, как обойти этот недостаток и форсировать работу sort. Может это и изобретение велосипеда, но зато трехколесного Все иллюстрирует пример:

Код (Text):

1. #include "stdafx.h"
2. #include <stdlib.h>
3. #include <time.h>
4.  
5. #define SIZE 400000
6.  
7. int n[SIZE]; int m[SIZE]; int xc=0;
8.  
9. int compare_my( int *x, int *y )
10. {  
11.     int i= *x-*y;
12.     if(i>0) return(1);
13.     if(i<0) return(-1);
14.     xc++; return( ((xc&1)<<1)-1);
15. }  
16.  
17. int compare( int *x, int *y ) {return(*x-*y);}
18.  
19. main()
20. {int i; clock_t start, finish;
21.  
22.     for(i=0;i<SIZE;i++) m[i]=n[i]=rand()/(RAND_MAX/16); // 0<= m,n < 16
23.  
24.     start = clock();
25.     qsort( n, SIZE, sizeof(int), compare_my );
26.     finish = clock(); double duration = (double)(finish - start) / CLOCKS_PER_SEC;
27.     printf( "Sorting with hint. Execution time= %2.2f seconds\n", duration );
28.  
29.     start = clock();
30.     qsort( &m[0], SIZE, sizeof(int), compare );
31.     finish = clock(); duration = (double)(finish - start) / CLOCKS_PER_SEC;
32.     printf( "Standart sorting. Execution time= %2.2f seconds\n", duration );
33.  
34.     for(i=0;i<SIZE;i++) if(m[i]!=n[i]) { printf("Results are different!\n"); exit(1);}
35.     printf("Results identical!\n");
36.  
37. getchar();
38. }

Вывод программы:
Sorting with hint. Execution time= 0.11 seconds
Standart sorting. Execution time= 14.69 seconds
Results identical!

В сотню раз быстрее сортируется. А при больших SIZE ускорение работы еще значительнее.

P.S. Интересно, а под другими компиляторами этот трюк поможет?

 

power1# g++ -v
Using built-in specs.
Target: i386-undermydesk-freebsd
Configured with: FreeBSD/i386 system compiler
Thread model: posix
gcc version 4.2.1 20070719 [FreeBSD]


power1# g++ qsort.cpp
power1# ./a.out
Sorting with hint. Execution time= 0.09 seconds
Standart sorting. Execution time= 0.02 seconds
Results identical!

 

MSVC8.0:
Sorting with hint. Execution time= 0.22 seconds
Standart sorting. Execution time= 0.06 seconds
Std C++ sorting. Execution time= 0.01 seconds
Results identical!

MSVC6.0:
Sorting with hint. Execution time= 0.22 seconds
Standart sorting. Execution time= 57.89 seconds
Std C++ sorting. Execution time= 0.05 seconds
Results identical!

Почти наверняка это неудачный алгоритм сортировки в старой RTL
На современных компиляторах этой проблемы нет
А вообще лучше использовать std::sort из стандартной библиотеки С++ т.к. тогда компилятор может инлайнить функцию сравнения.
ЗЫ: что же это за такой кривой VC6, где sort требует int (__cdecl *)(int *,int *) вместо int (__cdecl *)(const void *,const void *) ?
Исходники:

Код (Text):

1. #include <stdlib.h>
2. #include <stdio.h>
3. #include <time.h>
4. #include <algorithm>
5.  
6. #define SIZE 800000
7.  
8. int n[SIZE]; int m[SIZE];int k[SIZE]; int xc=0;
9.  
10. int compare_my(  void *x, const void *y )
11. {  
12.     int i= *(int *)x-*(int *)y;
13.     if(i>0) return(1);
14.     if(i<0) return(-1);
15.     xc++; return( ((xc&1)<<1)-1);
16. }  
17.  
18. int compare( const void *x, const void *y ) {return(*(int *)x-*(int *)y);}
19.  
20. void main()
21. {int i; clock_t start, finish;
22.  
23.     for(i=0;i<SIZE;i++) m[i]=n[i]=k[i]=rand()/(RAND_MAX/16);    // 0<= m,n < 16
24.  
25.     start = clock();
26.     qsort( n, SIZE, sizeof(int), compare_my );
27.     finish = clock(); double duration = (double)(finish - start) / CLOCKS_PER_SEC;
28.     printf( "Sorting with hint. Execution time= %2.2f seconds\n", duration );
29.  
30.     start = clock();
31.     qsort( m, SIZE, sizeof(int), compare );
32.     finish = clock(); duration = (double)(finish - start) / CLOCKS_PER_SEC;
33.     printf( "Standart sorting. Execution time= %2.2f seconds\n", duration );
34.  
35.     start = clock();
36.     std::sort(k, k + SIZE);
37.     finish = clock(); duration = (double)(finish - start) / CLOCKS_PER_SEC;
38.     printf( "Std C++ sorting. Execution time= %2.2f seconds\n", duration );
39.  
40.     for(i=0;i<SIZE;i++) if(m[i]!=n[i]) { printf("Results are different!\n"); exit(1);}
41.     for(i=0;i<SIZE;i++) if(m[i]!=k[i]) { printf("Results are different!\n"); exit(1);}
42.     printf("Results identical!\n");
43.  
44. getchar();
45. }