Changeset 2287 for branches/parallel
- Timestamp:
- 09/05/11 18:30:08 (13 years ago)
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
branches/parallel/src/TableTraverse.cpp
r2284 r2287 73 73 #endif 74 74 75 #ifdef HAVE_QSORT_R 76 77 static int compWithComparator(void *arg, const void *a, const void *b) 78 { 79 return ((asap::Comparator *)arg)->compare(a, b); 80 } 81 82 #else 83 75 84 static inline void swap_(char *a, char *b, size_t size) 76 85 { … … 91 100 } 92 101 93 static void sort_(char *left, char *right, const size_t size, 102 // returning NULL means, already sorted. 103 static inline char *quickFindPivot(char *const left, char *const right, 104 const size_t size, asap::Comparator *comp) 105 { 106 char *const m = &left[(((right - left) / size) / 2 ) * size]; 107 char *result = NULL; 108 if (left == m) { // This means there are at most 2 elements. 109 int diff = (left == right) ? 0 : comp->compare(left, right); 110 if (diff > 0) { 111 swap_(left, right, size); 112 } 113 if (diff != 0) { 114 return right; 115 } 116 return result; 117 } 118 119 int diff = comp->compare(left, m); 120 if (diff > 0) { 121 swap_(left, m, size); 122 } 123 int diff2 = comp->compare(m, right); 124 if (diff == 0 && diff2 == 0) { 125 return result; 126 } 127 result = m; 128 if (diff2 > 0) { 129 swap_(right, m, size); 130 int diff3 = comp->compare(left, m); 131 if (diff3 > 0) { 132 swap_(left, m, size); 133 } else if (diff3 == 0) { 134 result = right; 135 } 136 } else if (diff == 0) { 137 result = right; 138 } 139 return result; 140 } 141 142 static inline char *findPivot(char *const start, char *const end, 143 size_t size, asap::Comparator *comp) 144 { 145 char *result = quickFindPivot(start, end, size, comp); 146 if (result || &start[2*size] >= end) { 147 return result; 148 } 149 150 for (char *pivot = start + size; pivot <= end; pivot += size) { 151 int diff = comp->compare(start, pivot); 152 if (diff < 0) { 153 return pivot; 154 } else if (diff > 0) { 155 swap_(start, pivot, size); 156 return pivot; 157 } 158 } 159 return NULL; // all values are same. 160 } 161 162 static void sort_(char *const left, char *const right, const size_t size, 94 163 asap::Comparator *comp, int level) 95 164 { 96 c onst size_t len = (right - left) / size;97 if ( len < 2) {165 char *const m = findPivot(left, right, size, comp); 166 if (m == NULL) { 98 167 return; 99 168 } 100 size_t mid = len >> 1;101 169 char *l = left; 102 char *r = right - size;170 char *r = right; 103 171 char pivot[size] __attribute__ ((aligned (16))); 104 cpy(pivot, &left[mid*size], size);172 cpy(pivot, m, size); 105 173 while (true) { 106 174 while (l < r && comp->compare(l, pivot) < 0) { 107 175 l += size; 108 176 } 109 while (l < r && comp->compare( r, pivot) >0) {177 while (l < r && comp->compare(pivot, r) <= 0) { 110 178 r -= size; 111 179 } 112 180 if (l >= r) { 113 181 break; … … 117 185 r -= size; 118 186 } 119 sort_(left, l, size, comp, level + 1); 187 if (l == r && comp->compare(l, pivot) < 0) { 188 l += size; 189 } 190 sort_(left, l - size, size, comp, level + 1); 120 191 sort_(l, right, size, comp, level + 1); 121 192 } 193 194 #endif 122 195 123 196 static inline void modernQSort(void *base, size_t elements, size_t size, 124 197 asap::Comparator *comp) 125 198 { 126 sort_((char *)base, &((char *)base)[elements * size], size, comp, 0); 199 if (elements > 1) { 200 #ifdef HAVE_QSORT_R 201 qsort_r(base, elements, size, comp, compWithComparator); 202 #else 203 sort_((char *)base, &((char *)base)[(elements - 1) * size], size, comp, 0); 204 #endif 205 } 127 206 } 128 207 … … 224 303 } 225 304 226 #if 0 305 #if 0 && TIMING 306 #include <assert.h> 307 308 #define elementsof(x) (sizeof(x)/sizeof(*x)) 309 227 310 using namespace asap ; 228 311 229 class MyComp: public Comparator {312 class IntComp: public Comparator { 230 313 public: 231 314 virtual int compare(const void *a, const void *b) { … … 234 317 }; 235 318 319 static int compare(const void *a, const void *b) { 320 return (*(int*)a) - (*(int*)b); 321 } 322 236 323 int main() 237 324 { 325 IntComp myComp; 238 326 srand((int)currenttime()); 239 int x[100]; 240 printf("init\n"); 241 for (int i = 0; i < 100; i++) { 242 x[i] = rand() % 100; 243 } 244 MyComp myComp; 245 printf("sorting\n"); 327 const size_t N = 1024*1024*100; 328 int *x = new int[N]; 329 int xx[] = { 330 5, 3,0, 1, 2,4, 4, 4 331 }; 332 #if 0 333 { 334 int x[] = {1}; 335 char *p = findPivot((char *)x, (char *)&x[0], sizeof(x[0]), &myComp); 336 assert(p == NULL); 337 } 338 { 339 int x[] = {1, 1}; 340 char *p = findPivot((char *)x, (char *)&x[1], sizeof(x[0]), &myComp); 341 assert(p == NULL); 342 } 343 { 344 int x[] = {2, 1}; 345 char *p = findPivot((char *)x, (char *)&x[1], sizeof(x[0]), &myComp); 346 assert((int*)p == &x[1] && x[0] == 1 && x[1] == 2); 347 } 348 { 349 int x[] = {1, 2}; 350 char *p = findPivot((char *)x, (char *)&x[1], sizeof(x[0]), &myComp); 351 assert((int*)p == &x[1] && x[0] == 1 && x[1] == 2); 352 } 353 { 354 int x[] = {1, 1, 1}; 355 char *p = findPivot((char *)x, (char *)&x[2], sizeof(x[0]), &myComp); 356 assert(p == NULL); 357 } 358 { 359 int x[] = {2, 1, 1}; 360 char *p = findPivot((char *)x, (char *)&x[2], sizeof(x[0]), &myComp); 361 assert((int*)p == &x[2]); 362 assert(x[0] == 1 && x[1] == 1 && x[2] == 2); 363 } 364 { 365 int x[] = {1, 2, 1}; 366 char *p = findPivot((char *)x, (char *)&x[2], sizeof(x[0]), &myComp); 367 assert((int*)p == &x[2]); 368 assert(x[0] == 1 && x[1] == 1 && x[2] == 2); 369 } 370 { 371 int x[] = {1, 1, 2}; 372 char *p = findPivot((char *)x, (char *)&x[2], sizeof(x[0]), &myComp); 373 assert((int*)p == &x[2]); 374 assert(x[0] == 1 && x[1] == 1 && x[2] == 2); 375 } 376 { 377 int x[] = {2, 2, 1}; 378 char *p = findPivot((char *)x, (char *)&x[2], sizeof(x[0]), &myComp); 379 assert((int*)p == &x[1]); 380 assert(x[0] == 1 && x[1] == 2 && x[2] == 2); 381 } 382 { 383 int x[] = {2, 1, 2}; 384 char *p = findPivot((char *)x, (char *)&x[2], sizeof(x[0]), &myComp); 385 assert((int*)p == &x[1]); 386 assert(x[0] == 1 && x[1] == 2 && x[2] == 2); 387 } 388 { 389 int x[] = {1, 2, 2}; 390 char *p = findPivot((char *)x, (char *)&x[2], sizeof(x[0]), &myComp); 391 assert((int*)p == &x[1]); 392 assert(x[0] == 1 && x[1] == 2 && x[2] == 2); 393 } 394 { 395 int x[] = {1, 2, 3}; 396 char *p = findPivot((char *)x, (char *)&x[2], sizeof(x[0]), &myComp); 397 assert((int*)p == &x[1]); 398 assert(x[0] == 1 && x[1] == 2 && x[2] == 3); 399 } 400 { 401 int x[] = {2, 1, 3}; 402 char *p = findPivot((char *)x, (char *)&x[2], sizeof(x[0]), &myComp); 403 assert((int*)p == &x[1]); 404 assert(x[0] == 1 && x[1] == 2 && x[2] == 3); 405 } 406 { 407 int x[] = {1, 3, 2}; 408 char *p = findPivot((char *)x, (char *)&x[2], sizeof(x[0]), &myComp); 409 assert((int*)p == &x[1]); 410 assert(x[0] == 1 && x[1] == 2 && x[2] == 3); 411 } 412 { 413 int x[] = {3, 1, 2}; 414 char *p = findPivot((char *)x, (char *)&x[2], sizeof(x[0]), &myComp); 415 assert((int*)p == &x[1]); 416 assert(x[0] == 1 && x[1] == 2 && x[2] == 3); 417 } 418 { 419 int x[] = {3, 2, 1}; 420 char *p = findPivot((char *)x, (char *)&x[2], sizeof(x[0]), &myComp); 421 assert((int*)p == &x[1]); 422 assert(x[0] == 1 && x[1] == 2 && x[2] == 3); 423 } 424 { 425 int x[] = {2, 3, 1}; 426 char *p = findPivot((char *)x, (char *)&x[2], sizeof(x[0]), &myComp); 427 assert((int*)p == &x[1]); 428 assert(x[0] == 1 && x[1] == 2 && x[2] == 3); 429 } 430 { 431 int x[] = {36, 39, 42, 41, 36}; 432 char *p = findPivot((char *)x, (char *)&x[4], sizeof(x[0]), &myComp); 433 assert((int*)p == &x[4]); 434 assert(x[4] == 42); 435 } 436 437 //assert(("assert enabled: OK", false)); 438 modernQSort(x, 8, sizeof(x[0]), &myComp); 439 for (int i = 0; i < 8; i++) { 440 fprintf(stderr, "%d\n", x[i]); 441 } 442 #endif 443 fprintf(stderr, "init\n"); 444 for (int i = 0; i < N; i++) { 445 x[i] = rand(); 446 } 447 fprintf(stderr, "sorting\n"); 246 448 modernQSort(x, 1, sizeof(x[0]), &myComp); 247 449 modernQSort(x, 2, sizeof(x[0]), &myComp); 248 450 modernQSort(x, 3, sizeof(x[0]), &myComp); 249 modernQSort(x, 100, sizeof(x[0]), &myComp); 250 for (int i = 0; i < 100; i++) { 451 if (! getenv("QSORT")) { 452 double _s = currenttime(); 453 modernQSort(x, N, sizeof(x[0]), &myComp); 454 double _e = currenttime(); 455 fprintf(stderr, "modernSorted %.3f\n", _e - _s); 456 } else { 457 double _s = currenttime(); 458 qsort(x, N, sizeof(x[0]), compare); 459 double _e = currenttime(); 460 fprintf(stderr, "qsorted %.3f\n", _e - _s); 461 } 462 fprintf(stderr, "outputting\n"); 463 for (int i = 0; i < N; i++) { 251 464 printf("%d\n", x[i]); 252 465 } 253 } 254 #endif 466 delete[] x; 467 } 468 #endif
Note:
See TracChangeset
for help on using the changeset viewer.