11

可能であれば、次のクイックソートを改善するにはどうすればよいですか（パフォーマンスに関して）。助言がありますか？ 

void main()
    {
      quick(a,0,n-1);
    }

    void quick(int a[],int lower,int upper)
    {
       int loc;
       if(lower<upper)
       {
        loc=partition(a,lower,upper);
        quick(a,lower,loc-1);
        quick(a,loc+1,upper);

       }
    }

    /* Return type: int
      Parameters passed: Unsorted array and its lower and upper bounds */

    int partition(int a[],int lower,int upper)
    {
      int pivot,i,j,temp;
      pivot=a[lower];
      i=lower+1;
      j=upper;
      while(i<j)
        {
            while((i<upper)&&(a[i]<=pivot))
            i++;
            while((a[j]>pivot))
            j--;
            if(i<j)
                {
                    temp=a[i];
                    a[i]=a[j];
                    a[j]=temp;
                }

        }//end while

        if(pivot>a[j])
        {
             temp=a[j];
             a[j]=a[lower];
             a[lower]=temp;
        }

         return(j);

}//end partition
4

14 に答える 14

24

クイックソート アルゴリズムは簡単に並列化できます。使用するコアが複数ある場合は、かなりの速度向上が見られる可能性があります。データセットの大きさにもよりますが、他のどの最適化よりも簡単に高速化できます。ただし、プロセッサが 1 つしかない場合や、データ セットが比較的小さい場合は、速度はあまり向上しません。

これが可能であれば、もっと詳しく説明できます。

于 2009-11-17T10:18:35.297 に答える
19
  1. より良いピボットを選択してください。median-of-three では、3 つの (ランダムな) 要素を選択し、中央値要素としてピボットを選択します
  2. length(a[]) < M (実際には M = 9 を選択) の場合、並べ替えを停止します。qsort() が終了したら、およそ M * N = O(N) かかる挿入ソートを適用します。これにより、divide-et-impera 再帰ツリーのリーフに近い多くの関数呼び出しが回避されます。
于 2009-11-06T15:25:05.923 に答える
17

最初の提案は、再帰呼び出しの 1 つを反復に置き換えることです。そして、再帰のために手動で実装されたスタックではなく、実際の反復を意味します。quickつまり、 fromに対して 2 つの「新しい」呼び出しを行う代わりに、現在の呼び出しをquick「リサイクル」して再帰の 1 つのブランチを処理し、再帰的に呼び出して別のブランチを処理します。quickquick

ここで、短いパーティションに対して常に実際の再帰呼び出しを行う(そして長いパーティションに対して反復を使用する) ことを確認すると、最悪の場合でも再帰の深さが決して超えないことが保証されlog Nます。中央値を選択します。

qsortこれはすべて、GCC 標準ライブラリに付属するアルゴリズムで実装されています。ソースを見てください。役に立つはずです。

おおよそ、上記の提案に従うより実用的な実装は次のようになります。

void quick(int a[], int lower, int upper)
{
  while (lower < upper)
  {
    int loc = partition(a, lower, upper);
    if (loc - lower < upper - loc)
    { /* Lower part is shorter... */
      quick(a, lower, loc - 1); /* ...process it recursively... */
      lower = loc + 1; /* ...and process the upper part on the next iteration */
    }
    else
    { /* Upper part is shorter... */
      quick(a, loc + 1, upper); /* ...process it recursively... */
      upper = loc - 1; /* ...and process the lower part on the next iteration */
    }
  }
}

もちろん、これは単なるアイデアのスケッチです。未検証。繰り返しますが、同じ考え方について GCC の実装を見てください。また、残りの再帰呼び出しを「手動」再帰に置き換えますが、実際には必要ありません。

于 2009-11-06T16:54:01.267 に答える
10

ループレスアルゴリズムを使用して小さなブロック（<5要素）を並べ替えると、パフォーマンスが向上する場合があります。5つの要素のループレスソートアルゴリズムを作成する方法の例を1つだけ見つけました： http：//wiki.tcl.tk/4118

このアイデアは、Cの2、3、4、5要素のループレスソートアルゴリズムを生成するために使用できます。

編集：私は1セットのデータでそれを試しました、そして私は質問のコードと比較して87％の実行時間を測定しました。<20ブロックで挿入ソートを使用すると、同じデータセットで92％になりました。この測定値は代表的なものではありませんが、これがクイックソートコードを改善する方法であることを示している可能性があります。

編集：このサンプルコードは、2〜6個の要素のループレスソート関数を書き出します。

#include <stdio.h>

#define OUT(i,fmt,...)  printf("%*.s"fmt"\n",i,"",##__VA_ARGS__);

#define IF( a,b, i, block1, block2 ) \
  OUT(i,"if(t[%i]>t[%i]){",a,b) block1 OUT(i,"}else{") block2 OUT(i,"}")

#define AB2(i,a,b)         IF(a,b,i,P2(i+2,b,a),P2(i+2,a,b))
#define  P2(i,a,b)         print_perm(i,2,(int[2]){a,b});

#define AB3(i,a,b,c)       IF(a,b,i,BC3(i+2,b,a,c),BC3(i+2,a,b,c))
#define AC3(i,a,b,c)       IF(a,c,i, P3(i+2,c,a,b), P3(i+2,a,c,b))
#define BC3(i,a,b,c)       IF(b,c,i,AC3(i+2,a,b,c), P3(i+2,a,b,c))
#define  P3(i,a,b,c)       print_perm(i,3,(int[3]){a,b,c});

#define AB4(i,a,b,c,d)     IF(a,b,i,CD4(i+2,b,a,c,d),CD4(i+2,a,b,c,d))
#define AC4(i,a,b,c,d)     IF(a,c,i, P4(i+2,c,a,b,d), P4(i+2,a,c,b,d))
#define BC4(i,a,b,c,d)     IF(b,c,i,AC4(i+2,a,b,c,d), P4(i+2,a,b,c,d))
#define BD4(i,a,b,c,d)     IF(b,d,i,BC4(i+2,c,d,a,b),BC4(i+2,a,b,c,d))
#define CD4(i,a,b,c,d)     IF(c,d,i,BD4(i+2,a,b,d,c),BD4(i+2,a,b,c,d))
#define  P4(i,a,b,c,d)     print_perm(i,4,(int[4]){a,b,c,d});

#define AB5(i,a,b,c,d,e)   IF(a,b,i,CD5(i+2,b,a,c,d,e),CD5(i+2,a,b,c,d,e))
#define AC5(i,a,b,c,d,e)   IF(a,c,i, P5(i+2,c,a,b,d,e), P5(i+2,a,c,b,d,e))
#define AE5(i,a,b,c,d,e)   IF(a,e,i,CB5(i+2,e,a,c,b,d),CB5(i+2,a,e,c,b,d))
#define BE5(i,a,b,c,d,e)   IF(b,e,i,AE5(i+2,a,b,c,d,e),DE5(i+2,a,b,c,d,e))
#define BD5(i,a,b,c,d,e)   IF(b,d,i,BE5(i+2,c,d,a,b,e),BE5(i+2,a,b,c,d,e))
#define CB5(i,a,b,c,d,e)   IF(c,b,i,DC5(i+2,a,b,c,d,e),AC5(i+2,a,b,c,d,e))
#define CD5(i,a,b,c,d,e)   IF(c,d,i,BD5(i+2,a,b,d,c,e),BD5(i+2,a,b,c,d,e))
#define DC5(i,a,b,c,d,e)   IF(d,c,i, P5(i+2,a,b,c,d,e), P5(i+2,a,b,d,c,e))
#define DE5(i,a,b,c,d,e)   IF(d,e,i,CB5(i+2,a,b,c,e,d),CB5(i+2,a,b,c,d,e))
#define  P5(i,a,b,c,d,e)   print_perm(i,5,(int[5]){a,b,c,d,e});

#define AB6(i,a,b,c,d,e,f) IF(a,b,i,CD6(i+2,b,a,c,d,e,f),CD6(i+2,a,b,c,d,e,f))
#define AC6(i,a,b,c,d,e,f) IF(a,c,i, P6(i+2,c,a,b,d,e,f), P6(i+2,a,c,b,d,e,f))
#define AE6(i,a,b,c,d,e,f) IF(a,e,i,CB6(i+2,e,a,c,b,d,f),CB6(i+2,a,e,c,b,d,f))
#define BD6(i,a,b,c,d,e,f) IF(b,d,i,DF6(i+2,c,d,a,b,e,f),DF6(i+2,a,b,c,d,e,f))
#define BE6(i,a,b,c,d,e,f) IF(b,e,i,AE6(i+2,a,b,c,d,e,f),DE6(i+2,a,b,c,d,e,f))
#define CB6(i,a,b,c,d,e,f) IF(c,b,i,DC6(i+2,a,b,c,d,e,f),AC6(i+2,a,b,c,d,e,f))
#define CD6(i,a,b,c,d,e,f) IF(c,d,i,EF6(i+2,a,b,d,c,e,f),EF6(i+2,a,b,c,d,e,f))
#define DB6(i,a,b,c,d,e,f) IF(d,b,i,BE6(i+2,a,b,c,d,e,f),BE6(i+2,c,d,a,b,e,f))
#define DC6(i,a,b,c,d,e,f) IF(d,c,i, P6(i+2,a,b,c,d,e,f), P6(i+2,a,b,d,c,e,f))
#define DE6(i,a,b,c,d,e,f) IF(d,e,i,CB6(i+2,a,b,c,e,d,f),CB6(i+2,a,b,c,d,e,f))
#define DF6(i,a,b,c,d,e,f) IF(d,f,i,DB6(i+2,a,b,e,f,c,d),BE6(i+2,a,b,c,d,e,f))
#define EF6(i,a,b,c,d,e,f) IF(e,f,i,BD6(i+2,a,b,c,d,f,e),BD6(i+2,a,b,c,d,e,f))
#define  P6(i,a,b,c,d,e,f) print_perm(i,6,(int[6]){a,b,c,d,e,f});

#define SORT(ABn,n,...) \
  OUT( 0, ""); \
  OUT( 0, "inline void sort" #n "( int t[" #n "] ){" ) \
  OUT( 2, "int tmp;" ) \
  ABn( 2, __VA_ARGS__ ) \
  OUT( 0, "}" )

void print_perm( int ind, int n, int t[n] ){
  printf("%*.s", ind-1, "");
  for( int i=0; i<n; i++ )
    if( i != t[i] ){
      printf(" tmp=t[%i]; t[%i]=",i,i);
      for( int j=t[i],k; j!=i; k=j,j=t[j],t[k]=k)
        printf("t[%i]; t[%i]=",j,j);
      printf("tmp;");
    }
  printf("\n");
}

int main( void ){
  SORT( AB2, 2, 0,1 )
  SORT( AB3, 3, 0,1,2 )
  SORT( AB4, 4, 0,1,2,3 )
  SORT( AB5, 5, 0,1,2,3,4 )
  SORT( AB6, 6, 0,1,2,3,4,5 )
}

生成されたコード3718行の長さ：

sort2（）：8
sort3（）：24
sort4（）：96
sort5（）：512
sort6（）：3072
于 2009-11-14T17:25:04.607 に答える
9

別のソートアルゴリズムを試してください。

データによっては、メモリを速度と交換できる場合があります。

ウィキペディアによると

  • クイックソートには、ベストケースのO（n log n）パフォーマンスとO（1）スペースがあります
  • マージソートには、固定のO（n log n）パフォーマンスとO（n）スペースがあります
  • 基数ソートには、固定のO（n。<桁数>）パフォーマンスとO（n。<桁数>）スペースがあります。

編集

どうやらあなたのデータは整数です。[0、0x0fffffff]の範囲の250万の整数を使用すると、基数ソートの実装は、クイックソートの実装の約4倍の速度になります。

$ ./a.out
qsort時間：0.39秒
基数時間：0.09秒
良い：2000; 悪：0

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define ARRAY_SIZE 2560000
#define RANDOM_NUMBER (((rand() << 16) + rand()) & 0x0fffffff)

int partition(int a[], int lower, int upper) {
  int pivot, i, j, temp;
  pivot = a[lower];
  i = lower + 1;
  j = upper;
  while (i < j) {
    while((i < upper) && (a[i] <= pivot)) i++;
    while (a[j] > pivot) j--;
    if (i < j) {
      temp = a[i];
      a[i] = a[j];
      a[j] = temp;
    }
  }
  if (pivot > a[j]) {
    temp = a[j];
    a[j] = a[lower];
    a[lower] = temp;
  }
  return j;
}

void quick(int a[], int lower, int upper) {
  int loc;
  if (lower < upper) {
    loc = partition(a, lower, upper);
    quick(a, lower, loc-1);
    quick(a, loc+1, upper);
  }
}

#define NBUCKETS 256
#define BUCKET_SIZE (48 * (1 + ARRAY_SIZE / NBUCKETS))

/* "waste" memory */
int bucket[NBUCKETS][BUCKET_SIZE];

void radix(int *a, size_t siz) {
  unsigned shift = 0;
  for (int dummy=0; dummy<4; dummy++) {
    int bcount[NBUCKETS] = {0};
    int *aa = a;
    size_t s = siz;
    while (s--) {
      unsigned v = ((unsigned)*aa >> shift) & 0xff;
      if (bcount[v] == BUCKET_SIZE) {
        fprintf(stderr, "not enough memory.\n");
        fprintf(stderr, "v == %u; bcount[v] = %d.\n", v, bcount[v]);
        exit(EXIT_FAILURE);
      }
      bucket[v][bcount[v]++] = *aa++;
    }
    aa = a;
    for (int k=0; k<NBUCKETS; k++) {
      for (int j=0; j<bcount[k]; j++) *aa++ = bucket[k][j];
    }
    shift += 8;
  }
}

int ar1[ARRAY_SIZE];
int ar2[ARRAY_SIZE];

int main(void) {
  clock_t t0;

  srand(time(0));
  for (int k=0; k<ARRAY_SIZE; k++) ar1[k] = ar2[k] = RANDOM_NUMBER;

  t0 = clock(); while (clock() == t0) /* void */; t0 = clock();
  do {
    quick(ar1, 0, ARRAY_SIZE - 1);
  } while (0);
  double qsort_time = (double)(clock() - t0) / CLOCKS_PER_SEC;

  t0 = clock(); while (clock() == t0) /* void */; t0 = clock();
  do {
    radix(ar2, ARRAY_SIZE);
  } while (0);
  double radix_time = (double)(clock() - t0) / CLOCKS_PER_SEC;

  printf("qsort time: %.2f secs\n", qsort_time);
  printf("radix time: %.2f secs\n", radix_time);

  /* compare sorted arrays by sampling */
  int evil = 0;
  int good = 0;
  for (int chk=0; chk<2000; chk++) {
    size_t index = RANDOM_NUMBER % ARRAY_SIZE;
    if (ar1[index] == ar2[index]) good++;
    else evil++;
  }
  printf("good: %d; evil: %d\n", good, evil);

  return 0;
}
于 2009-11-17T10:44:28.240 に答える
6

クイックソートに関するウィキペディアの記事には、たくさんのアイデアがあります。

于 2009-11-06T15:24:25.893 に答える
2

現在、広く使用されている最も高度なクイックソートは、Java のDualPivotQuicksort.javaに実装されているため 、そのアプローチに従うだけで、パフォーマンスが大幅に向上します。

  • 小さな配列には挿入ソートを使用します (47 は Java で使用される数値です)。
  • 5 の 2 番目と 4 番目の要素を 2 つのピボットとして選択するデュアル ピボット クイックソートを使用します。
  • 並べ替えられた数値の連続を含む配列にマージソートを使用することを検討してください

または、もう少し複雑にしたい場合は、3-pivot クイックソートをコーディングします。

于 2017-11-23T17:36:28.120 に答える
2

  1. Explicit Stack で QuickSort を使用すると、再帰的なオーバーヘッドを排除できます。

    void quickSort(int a[], int lower, int upper)
{
    createStack(); 
    push(lower); 
    push(upper);

    while (!isEmptyStack()) {
    upper=poptop();
    lower=poptop();
       while (lower<upper) {
                 pivPos=partition(selectPivot(a, size), a, lower, upper);
                 push(lower);
                 push(pivPos-1);
                 lower = pivPos+1; // end = end;
       }
   }
}

  2. 次のような、より優れたピボット選択手法を使用できます。

    1. 3の中央値
    2. 中央値の中央値
    3. ランダムピボット
于 2009-11-18T08:39:51.597 に答える
1

これが単なる学習用でない場合は、stdlib.hのqsortを使用してください

于 2009-11-17T17:46:22.427 に答える
1

完全にばかげた答えですが...コードをリリースモードでコンパイルし、最適化をオンにしてください!

于 2009-11-21T13:55:13.067 に答える
1

あなたのコードによると、ソートされた長さが10の場合、最も深いスタックは次のようになります

#0  partition (a=0x7fff5ac42180, lower=3, upper=5) 
#1  0x000000000040062f in quick (a=0x7fff5ac42180, lower=3, upper=5) 
#2  0x0000000000400656 in quick (a=0x7fff5ac42180, lower=0, upper=5) 
#3  0x0000000000400644 in quick (a=0x7fff5ac42180, lower=0, upper=8) 
#4  0x0000000000400644 in quick (a=0x7fff5ac42180, lower=0, upper=9) 
#5  0x00000000004005c3 in main

アルゴ自体に加えて、スタック アクティビティなどのシステムの動作も考慮すると、通常のコール スタック コスト (プッシュ/ポップ) 以外の何かがパフォーマンスを大幅に低下させる可能性があります。マルチタスクであり、スタックが深いほどスイッチングのコストが高くなり、さらにキャッシュ ミスまたはキャッシュライン境界を越えます。

この場合、長さが大きくなると、他のソートアルゴリズムと比較すると負けると思います。

たとえば、長さが最大 ​​40 の場合、スタックは次のようになります (以下に示すよりも多くのエントリがある場合があります)。

#0  partition (a=0x7fff24810cd0, lower=8, upper=9) 
#1  0x000000000040065d in quick (a=0x7fff24810cd0, lower=8, upper=9)  
#2  0x0000000000400672 in quick (a=0x7fff24810cd0, lower=8, upper=10) 
#3  0x0000000000400672 in quick (a=0x7fff24810cd0, lower=8, upper=14) 
#4  0x0000000000400684 in quick (a=0x7fff24810cd0, lower=4, upper=14) 
#5  0x0000000000400672 in quick (a=0x7fff24810cd0, lower=4, upper=18) 
#6  0x0000000000400684 in quick (a=0x7fff24810cd0, lower=0, upper=18) 
#7  0x0000000000400672 in quick (a=0x7fff24810cd0, lower=0, upper=26) 
#8  0x0000000000400672 in quick (a=0x7fff24810cd0, lower=0, upper=38) 
#9  0x0000000000400672 in quick (a=0x7fff24810cd0, lower=0, upper=39) 
#10 0x00000000004005ee in main

スタックが深すぎます。

関数のインライン化も役立ちますが、最終的な実行可能ファイルのコード フットプリントが増加します。@Swissに同意します。並列プログラミングは非常に役立つかもしれません。

于 2009-11-18T08:56:06.997 に答える
0

質問に答えるために私の答えからコピーしました。

編集：この投稿は、不要な呼び出しのオーバーヘッドを取り除くために末尾再帰を利用するなど、すでに明らかなことを行っていることを前提としています。

人々は、特にユーザーが入力を制御できる場合、特定の入力でのパフォーマンスの低下についてクイックソートを批判するのが好きです。次のアプローチでは、パフォーマンスが一致する中間点の選択が得られますが、リストのサイズが大きくなるにつれて、予想される複雑さは指数関数的にO（n log n ）に近づきます。私の経験では、ほとんどの場合、オーバーヘッドがはるかに少ないため、ベストオブ3の選択を大幅に上回っています。「期待される」入力の中間点選択で均等に実行する必要がありますが、不十分な入力に対して脆弱ではありません。

  • ランダムな正の整数でクイックソートを初期化しIます。その値は、並べ替えプロセス全体で使用されます（複数の数値を生成する必要はありません）。
  • ピボットがとして選択されていI mod SectionSizeます。

パフォーマンスを向上させるには、常にクイックソートを「小さな」リストセグメントのシェルソートに切り替える必要があります。カットオフとして15〜100の長さが選択されています。

于 2009-11-19T07:11:52.253 に答える
0

マルチスレッド?

/*
 * multiple-thread quick-sort.
 * Works fine on uniprocessor machines as well.
 */

#include <unistd.h>
#include <stdlib.h>
#include <thread.h>

/* don't create more threads for less than this */
#define SLICE_THRESH   4096

/* how many threads per lwp */
#define THR_PER_LWP       4

/* cast the void to a one byte quanitity and compute the offset */
#define SUB(a, n)      ((void *) (((unsigned char *) (a)) + ((n) * width)))

typedef struct {
  void    *sa_base;
  int      sa_nel;
  size_t   sa_width;
  int    (*sa_compar)(const void *, const void *);
} sort_args_t;

/* for all instances of quicksort */
static int threads_avail;

#define SWAP(a, i, j, width)
{ 
  int n; 
  unsigned char uc; 
  unsigned short us; 
  unsigned long ul; 
  unsigned long long ull; 

  if (SUB(a, i) == pivot) 
    pivot = SUB(a, j); 
  else if (SUB(a, j) == pivot) 
    pivot = SUB(a, i); 

  /* one of the more convoluted swaps I've done */ 
  switch(width) { 
  case 1: 
    uc = *((unsigned char *) SUB(a, i)); 
    *((unsigned char *) SUB(a, i)) = *((unsigned char *) SUB(a, j)); 
    *((unsigned char *) SUB(a, j)) = uc; 
    break; 
  case 2: 
    us = *((unsigned short *) SUB(a, i)); 
    *((unsigned short *) SUB(a, i)) = *((unsigned short *) SUB(a, j)); 
    *((unsigned short *) SUB(a, j)) = us; 
    break; 
  case 4: 
    ul = *((unsigned long *) SUB(a, i)); 
    *((unsigned long *) SUB(a, i)) = *((unsigned long *) SUB(a, j)); 
    *((unsigned long *) SUB(a, j)) = ul; 
    break; 
  case 8: 
    ull = *((unsigned long long *) SUB(a, i)); 
    *((unsigned long long *) SUB(a,i)) = *((unsigned long long *) SUB(a,j)); 
    *((unsigned long long *) SUB(a, j)) = ull; 
    break; 
  default: 
    for(n=0; n<width; n++) { 
      uc = ((unsigned char *) SUB(a, i))[n]; 
      ((unsigned char *) SUB(a, i))[n] = ((unsigned char *) SUB(a, j))[n]; 
      ((unsigned char *) SUB(a, j))[n] = uc; 
    } 
    break; 
  } 
}

static void *
_quicksort(void *arg)
{
  sort_args_t *sargs = (sort_args_t *) arg;
  register void *a = sargs->sa_base;
  int n = sargs->sa_nel;
  int width = sargs->sa_width;
  int (*compar)(const void *, const void *) = sargs->sa_compar;
  register int i;
  register int j;
  int z;
  int thread_count = 0;
  void *t;
  void *b[3];
  void *pivot = 0;
  sort_args_t sort_args[2];
  thread_t tid;

  /* find the pivot point */
  switch(n) {
  case 0:
  case 1:
    return 0;
  case 2:
    if ((*compar)(SUB(a, 0), SUB(a, 1)) > 0) {
      SWAP(a, 0, 1, width);
    }
    return 0;
  case 3:
    /* three sort */
    if ((*compar)(SUB(a, 0), SUB(a, 1)) > 0) {
      SWAP(a, 0, 1, width);
    }
    /* the first two are now ordered, now order the second two */
    if ((*compar)(SUB(a, 2), SUB(a, 1)) < 0) {
      SWAP(a, 2, 1, width);
    }
    /* should the second be moved to the first? */
    if ((*compar)(SUB(a, 1), SUB(a, 0)) < 0) {
      SWAP(a, 1, 0, width);
    }
    return 0;
  default:
    if (n > 3) {
      b[0] = SUB(a, 0);
      b[1] = SUB(a, n / 2);
      b[2] = SUB(a, n - 1);
      /* three sort */
      if ((*compar)(b[0], b[1]) > 0) {
        t = b[0];
        b[0] = b[1];
        b[1] = t;
      }
      /* the first two are now ordered, now order the second two */
      if ((*compar)(b[2], b[1]) < 0) {
        t = b[1];
        b[1] = b[2];
        b[2] = t;
      }
      /* should the second be moved to the first? */
      if ((*compar)(b[1], b[0]) < 0) {
        t = b[0];
        b[0] = b[1];
        b[1] = t;
      }
      if ((*compar)(b[0], b[2]) != 0)
        if ((*compar)(b[0], b[1]) < 0)
          pivot = b[1];
        else
          pivot = b[2];
    }
    break;
  }
  if (pivot == 0)
    for(i=1; i<n; i++) {
      if (z = (*compar)(SUB(a, 0), SUB(a, i))) {
        pivot = (z > 0) ? SUB(a, 0) : SUB(a, i);
        break;
      }
    }
  if (pivot == 0)
    return;

  /* sort */
  i = 0;
  j = n - 1;
  while(i <= j) {
    while((*compar)(SUB(a, i), pivot) < 0)
      ++i;
    while((*compar)(SUB(a, j), pivot) >= 0)
      --j;
    if (i < j) {
      SWAP(a, i, j, width);
      ++i;
      --j;
    }
  }

  /* sort the sides judiciously */
  switch(i) {
  case 0:
  case 1:
    break;
  case 2:
    if ((*compar)(SUB(a, 0), SUB(a, 1)) > 0) {
      SWAP(a, 0, 1, width);
    }
    break;
  case 3:
    /* three sort */
    if ((*compar)(SUB(a, 0), SUB(a, 1)) > 0) {
      SWAP(a, 0, 1, width);
    }
    /* the first two are now ordered, now order the second two */
    if ((*compar)(SUB(a, 2), SUB(a, 1)) < 0) {
      SWAP(a, 2, 1, width);
    }
    /* should the second be moved to the first? */
    if ((*compar)(SUB(a, 1), SUB(a, 0)) < 0) {
      SWAP(a, 1, 0, width);
    }
    break;
  default:
    sort_args[0].sa_base          = a;
    sort_args[0].sa_nel           = i;
    sort_args[0].sa_width         = width;
    sort_args[0].sa_compar        = compar;
    if ((threads_avail > 0) && (i > SLICE_THRESH)) {
      threads_avail--;
      thr_create(0, 0, _quicksort, &sort_args[0], 0, &tid);
      thread_count = 1;
    } else
      _quicksort(&sort_args[0]);
    break;
  }
  j = n - i;
  switch(j) {
  case 1:
    break;
  case 2:
    if ((*compar)(SUB(a, i), SUB(a, i + 1)) > 0) {
      SWAP(a, i, i + 1, width);
    }
    break;
  case 3:
    /* three sort */
    if ((*compar)(SUB(a, i), SUB(a, i + 1)) > 0) {
      SWAP(a, i, i + 1, width);
    }
    /* the first two are now ordered, now order the second two */
    if ((*compar)(SUB(a, i + 2), SUB(a, i + 1)) < 0) {
      SWAP(a, i + 2, i + 1, width);
    }
    /* should the second be moved to the first? */
    if ((*compar)(SUB(a, i + 1), SUB(a, i)) < 0) {
      SWAP(a, i + 1, i, width);
    }
    break;
  default:
    sort_args[1].sa_base          = SUB(a, i);
    sort_args[1].sa_nel           = j;
    sort_args[1].sa_width         = width;
    sort_args[1].sa_compar        = compar;
    if ((thread_count == 0) && (threads_avail > 0) && (i > SLICE_THRESH)) {
      threads_avail--;
      thr_create(0, 0, _quicksort, &sort_args[1], 0, &tid);
      thread_count = 1;
    } else
      _quicksort(&sort_args[1]);
    break;
  }
  if (thread_count) {
    thr_join(tid, 0, 0);
    threads_avail++;
  }
  return 0;
}

void
quicksort(void *a, size_t n, size_t width,
          int (*compar)(const void *, const void *))
{
  static int ncpus = -1;
  sort_args_t sort_args;

  if (ncpus == -1) {
    ncpus = sysconf( _SC_NPROCESSORS_ONLN);

    /* lwp for each cpu */
    if ((ncpus > 1) && (thr_getconcurrency() < ncpus))
      thr_setconcurrency(ncpus);

    /* thread count not to exceed THR_PER_LWP per lwp */
    threads_avail = (ncpus == 1) ? 0 : (ncpus * THR_PER_LWP);
  }
  sort_args.sa_base = a;
  sort_args.sa_nel = n;
  sort_args.sa_width = width;
  sort_args.sa_compar = compar;
  (void) _quicksort(&sort_args);
}
于 2009-11-21T13:20:21.670 に答える
0

最初に行うことは、ベンチマークです。そして、標準の qsort に対して、および c++ std::sort および std::stable_sort に対してベンチマークします。

データセットが十分に大きい場合、結果は、std::stable_sort が優れている場合を除いて、すべてのケースで std::sort が qsort よりも優れていることを示します。これは、std::sort がテンプレート化されているため、比較をインライン化できるためです。

ジェネリックではないため、コードは比較をインライン化します。コードが qsort よりも遅い場合、問題が発生しています。

高速な並べ替えは、openmp などのパーツを並行して並べ替えてから、それらを再びマージすることです。

于 2009-11-18T09:06:47.347 に答える