تحسين نوع سريع
https://stackoverflow.com/questions/1688264
-
18-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russianسؤال
إذا كان ذلك ممكنا ، كيف يمكنني تحسين التالية نوع سريع(أداء الحكمة).أي اقتراحات ؟
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
المحلول
يتم توزز خوارزمية QuickSort بسهولة. إذا كان لديك نوى متعددة للعمل معها، فيمكنك أن ترى قليلا من السرعة. اعتمادا على حجم مجموعة البيانات الكبيرة، يمكن أن توفر لك بسهولة أكبر بسرعة أكبر من أي تحسين آخر. ومع ذلك، إذا كان لديك معالج واحد فقط أو مجموعة بيانات صغيرة نسبيا، فلن يكون هناك الكثير من السرعة.
يمكنني وضع المزيد إذا كان هذا احتمالا.
نصائح أخرى
- اختيار أفضل محور:على سبيل المثال.في المتوسط من ثلاث يمكنك اختيار 3 (عشوائي) العناصر واختيار محور as متوسط عنصر
- عندما طول(a[]) < م (في الممارسة اختيار M = 9) وقف الفرز.بعد qsort() الانتهاء من تطبيق إدراج النوع التي من شأنها أن تأخذ تقريبا M * N = O(N).هذا يتجنب العديد من المكالمات الدالة على مقربة من ورقة من تقسيم-et-impera العودية شجرة.
سيكون الاقتراح الأول هو: استبدال أحد المكالمات العودية للتكرار. وأقصد التكرار الحقيقي، وليس كومة تنفذ يدويا للحصول على العودية. أي بدلا من إجراء مكالمات "جديدة" quick من quick, ، "إعادة تدوير" الخاص بك حاضر دعوة ل quick لمعالجة فرع واحد من العودية، والاتصال quick متكرر لمعالجة فرع آخر.
الآن، إذا كنت تتأكد من أنك تقوم دائما بإجراء مكالمة متكررة حقيقية أقصر التقسيم (واستخدام التكرار لفترة أطول)، سيضمن أن عمق العودية لن يتجاوز أبدا log N حتى في أسوأ الحالات، أي بغض النظر عن مدى جودة اختيار الوسيط الخاص بك.
يتم تنفيذ كل هذا في qsort الخوارزمية التي تأتي مع مكتبة دول مجلس التعاون الخليجي القياسية. إلقاء نظرة على المصدر، يجب أن تكون مفيدة.
تقريبا، قد ينظر التنفيذ الأكثر عملية يتبع الاقتراح أعلاه كما يلي
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 */
}
}
}
هذا مجرد رسم من الفكرة، بالطبع. لم تختبر. مرة أخرى، ألق نظرة على تنفيذ دول مجلس التعاون الخليجي لنفس الفكرة. كما أنها تحل محل المكالمة العودية المتبقية مع العودية "اليدوية"، لكنها ليست ضرورية حقا.
قد يؤدي فرز الكتل الصغيرة (<5 عناصر) مع خوارزمية بلا غموض إلى تحسين الأداء. لقد وجدت مثالا واحدا فقط كيفية كتابة خوارزمية فرز غير مثبتة لمدة 5 عناصر: http://wiki.tcl.tk/4118.
يمكن استخدام الفكرة لتوليد خوارزميات فرز حلاقة ل 2،3،4،5 عناصر في C.
تحرير: لقد جربته على مجموعة واحدة من البيانات، وقياس 87٪ وقت التشغيل مقارنة بالقانون في السؤال. استخدام ترتيب الإدراج على <20 كتل نتج عن 92٪ على نفس مجموعة البيانات. هذا القياس غير ممثل ولكن قد يظهر أن هذه طريقة كيف يمكنك تحسين رمز QuickSort الخاص بك.
تحرير: رمز المثال هذا يكتب وظائف فرز مثبطات لعناصر 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
جرب خوارزمية فرز أخرى.
اعتمادا على بياناتك، قد تكون قادرا على تداول الذاكرة بسرعة.
وفقا ل Wikipedia
- فرز سريع لديه أ أفضل حالة س (سجل ن) الأداء و س (1) الفضاء
- دمج فرز لديه أ ثابت O (تسجيل N N) الأداء و على) الفضاء
- راديكس فرز لديه أ مثبت على .u003Cnumber of digits> في برفومنس و على .u003Cnumber of digits> في الفضاء
يحرر
يبدو أن بياناتك هي أعداد صحيحة. مع وجود أعداد صحيحة 2.5 متر في النطاق [0، 0x0FFFFFFFF]، فإن تطبيقي ل Radix-Trans هو حوالي 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;
}
ال مقالة ويكيبيديا على QuickSort لديه مجموعة من الأفكار.
يمكنك القضاء على recuriosn علوية باستخدام فرز سريع مع صريح المكدس
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; } } }يمكنك استخدام أفضل محور اختيار تقنية مثل:
- متوسط 3
- متوسط المتوسطات
- عشوائية المحورية
يتم تنفيذ QuickSort الأكثر تقدما حاليا على نطاق واسع في Java dualpivotquicksort.java.لذلك يمكنك ببساطة اتباع هذا النهج وسترى تحسين أداء لطيف:
- استخدام فرز الإدراج للحصول على صفائف صغيرة (47 هو الرقم المستخدم في جافا)
- استخدم هذا QuickSort Dual-Pivot اختيار العناصر الثانية والسفانية من 5 كحوري
- النظر في استخدام مدمج للحصول على صفائف مع أشواط من الأرقام الفرز
أو إذا كنت ترغب في إضافة تعقيد أكثر قليلا ثم رمز 3-Pivot QuickSort.
إذا كان هذا ليس فقط لاستخدام التعلم Qsort. من Stdlib.h.
لكل رمز، عند فرز طوله 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
إلى جانب Algo نفسه، إذا نظرنا في سلوك النظام مثل أنشطة المكدس أيضا، فإن أي شيء آخر باستثناء تكاليف مكدس المكالمات العادية (الدفع / البوب) قد تخفف من الأداء الكثير، مثل تبديل السياق إذا كان نظام المهام متعددة، كما تعلمون معظم نظام التشغيل هي المهام متعددة، وأعمق تكاليف المكدس أعلى التبديل، بالإضافة إلى الحد من ذاكرة التخزين المؤقت أو حدود cachline عبر.
أؤمن بهذه الحالة إذا كان طول الطول أكبر، فسوف تخسره عند مقارنة بعض algos الفرز الأخرى.
على سبيل المثال، عندما يصل طول طول إلى 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
أعمق جدا كومة.
الوظيفة المتنقلة مفيدة للغاية، ولكنها تزيد من بصمة التعليمات البرمجية للتنفيذ النهائي. وأنا أتفق مع Wswiss، قد تساعدك البرمجة الموازية كثيرا.
إجابة غبية تماما، ولكن ... ترجمة التعليمات البرمجية الخاصة بك في وضع الإصدار وتشغيل التحسينات!
أول شيء يجب القيام به هو مؤشره. وقم بمعاييره ضد QSort القياسية، مقابل C ++ STD :: Trans and STD :: Stable_Sort.
نتائجك، إذا كانت مجموعة البيانات الخاصة بك تكون كبيرة بما يكفي، فسوف تظهر أن STD :: فرز متفوقة على QSort في جميع الحالات إلا أولئك الذين td :: stable_sort هو متفوقة. وذلك لأن STD :: Trans تم القالب، وبالتالي يمكن إبزيم المقارنة.
الرمز الخاص بك يدخل المقارنة لأنه ليس عام. إذا كان التعليمات البرمجية أبطأ من QSort، فلديك مشكلة هناك.
سيكون الفرز الأسرع هو فرز الأجزاء بالتوازي، مثل OpenMP، ثم دمجها معا.
نسخ من إجابتي للإجابة على السؤال.
يحرر: يفترض أن هذا المنشور يفترض أنك تقوم بالفعل بأشياء واضحة مثل الاستفادة من العودية للتخلص من النفقات النقدية غير الضرورية.
يحب الناس انتقاد QuickSort لأداء ضعيف مع بعض المدخلات، خاصة عندما يكون لدى المستخدم التحكم في الإدخال. النهج التالي ينتج عنه أداء مطابقة اختيار نقطة منتصف ولكن التعقيد المتوقع أضعافا مضاعفة نهج O (ن سجل ن) كما تنمو القائمة في الحجم. في تجربتي، تتفوق بشكل كبير على اختيار أفضل من 3 بسبب نقاط نفقات أقل بكثير في حالة الأغلبية. يجب أن يؤدي ذلك بالتساوي إلى اختيار نقطة منتصف للمدخلات "المتوقعة"، لكنه غير عرضة للمدخلات السيئة.
- تهيئة QuickSort مع عدد صحيح إيجابي عشوائي
I. وبعد سيتم استخدام هذه القيمة طوال عملية الفرز (لا تضطر إلى توليد أرقام متعددة). - يتم تحديد المحور كما
I mod SectionSize.
للحصول على أداء إضافي، يجب عليك دائما تبديل QuickSort الخاص بك إلى SHELT فرز لشرائح القائمة "الصغيرة" - لقد رأيت أطوال من 15-100 تم اختيارها كقطع.
متعددة المتعددة؟
/*
* 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);
}
