Hi,
I have found a way for to can sort the numeric data into the array by the two
sides in // :)
*********************************
*Test modified bubble_sort algo *
*********************************
(loop=1, size=16, nsorted=(8+8)
iteration 1 : -125 [-14 99 -34 -65 90 85 -36 82 46 -26 -37 72 -14 -36 ] 104
iteration 2 : -125 -65 [-36 -34 -14 90 85 -36 82 46 -26 -37 72 -14 ] 99 104
iteration 3 : -125 -65 -37 [-34 -14 -14 85 -36 82 46 -26 -36 72 ] 90 99 104
iteration 4 : -125 -65 -37 -36 [-14 -14 72 -36 82 46 -26 -34 ] 85 90 99 104
iteration 5 : -125 -65 -37 -36 -36 [-14 72 -14 -34 46 -26 ] 82 85 90 99 104
iteration 6 : -125 -65 -37 -36 -36 -34 [-26 -14 -14 46 ] 72 82 85 90 99 104
iteration 7 : -125 -65 -37 -36 -36 -34 46 [-14 -26 ] -14 72 82 85 90 99 104
iteration 8 : -125 -65 -37 -36 -36 -34 -14 -26 [] 46 -14 72 82 85 90 99 104
0.000 seconds
(16 swaps per iteration)
Ordered data at the begin (8 values) : -125 -65 -37 -36 -36 -34 -14 -26
No ordered data (0 values) :
Ordered data at end (8 values) : 46 -14 72 82 85 90 99 104
Now, my sort routine is systematically very faster than the sort_u8() func and
is faster than the qsort() function until the data array size is more than about
450 bytes.
*********************************
* Test original bubble_sort algo *
**********************************
(loop=10240, size=8)
0.020 seconds
(16 swaps per iterations)
**************************************
* Test the standard quicksort routine *
*************************************
(nbiter=10240, size=8)
0.020 seconds
*********************************
*Test modified bubble_sort algo *
*********************************
(loop=10240, size=8, nsorted=(4+4)
0.010 seconds
(8 swaps per iteration)
to
*********************************
* Test original bubble_sort algo *
**********************************
(loop=10240, size=450)
3.980 seconds
(47491 swaps per iterations)
**************************************
* Test the standard quicksort routine *
*************************************
(nbiter=10240, size=450)
1.950 seconds
*********************************
*Test modified bubble_sort algo *
*********************************
(loop=10240, size=450, nsorted=(225+225)
1.920 seconds
(450 swaps per iteration)
=> here is the code of this new sort func :
static void sort_u8_ext2(uint8_t *data, int n, int (*functest)(const void *,
const void *), int lowers, int greaters)
{
int i, k;
int minval, maxval;
int imin = 0;
int imax = 0;
int left = 0;
int right = n - 1;
if ( ( lowers < 1 ) || ( lowers > n ) ) { lowers = n / 2; }
if ( (greaters < 1 ) || ( greaters > n ) ) { greaters = n / 2; }
greaters = n - greaters;
curriter = 0;
while( left < right )
{
minval = data[left];
maxval = data[right];
for( i = left + 1 ; i < right ; i++)
{
if( functest( (void *) data + i, (void *) &minval ) <=
0 )
{
minval = data[i];
imin = i;
}
if( functest( (void *) data + i, (void *) &maxval ) >=
0 )
{
maxval = data[i];
imax = i;
}
}
if ( imin )
{
swap_u8( data + left , data + imin );
#ifdef DEBUG_ALGO
nswaps++;
#endif
}
if ( imax )
{
swap_u8( data + right, data + imax );
#ifdef DEBUG_ALGO
nswaps++;
#endif
}
left++;
#ifdef DEBUG_VALUES
printf("iteration %d : ", ++curriter);
for( k = 0; k < left; k++)
{
printf("%d ", data[k]);
}
/* if( left < right ) */ printf("[");
for( k = left ; k < right ; k++)
{
printf("%d ", data[k]);
}
/* if( right > left ) */ printf("] ");
for( k = right ; k < n ; k++)
{
printf("%d ", data[k]);
}
printf("\n");
#endif
right--;
// printf("(left=%d right=%d lowers=%d greaters=%d) \n", left,
right, lowers,
greaters);
if ( ( left > lowers ) && ( right < greaters ) )
{
/* Early terminaison */
printf("Early termination (left=%d right=%d lowers=%d
greaters=%d) \n",
left, right, lowers, greaters);
return;
}
}
}
static void swap_u8 (uint8_t *a, uint8_t *b)
{
uint8_t tmp;
tmp = *a;
*a = *b;
*b = tmp;
}
And here, the part of my program that use this sort_u8_ext() func :
printf("\n*********************************");
printf("\n*Test modified bubble_sort algo *");
printf("\n*********************************\n");
#ifndef SYMETRIC_ALGO
printf("(loop=%d, size=%d, nsorted=%d)\n", niter, size, nsorted);
#else
printf("(loop=%d, size=%d, nsorted=(%d+%d)\n",
niter, size, nsorted, nsorted);
#endif
for( i = 0; i < niter ; i++)
{
// printf("Iteration %d \n", i);
memcpy(ordered,unordered, size);
nswaps=0;
start = clock();
#ifdef DEBUG_INTERNAL
bubble_sort2(ordered, size, nsorted);
#else
// sort_u8_ext(ordered, size, nsorted);
sort_u8_ext2( ordered, size, compare_u8, nsorted, nsorted);
#endif
end = clock();
cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
timer3 += cpu_time_used;
}
printf("%.3f seconds \n", timer3);
#ifdef DEBUG_ALGO
printf("(%d swaps per iteration)\n", nswaps);
#endif
#ifdef DEBUG_RESULTS
#ifndef SYMETRIC_ALGO
printf("Ordered data (%d values) : ", nsorted);
#else
printf("Ordered data at the begin (%d values) : ", nsorted);
#endif
for( i = 0; i < nsorted; i++)
{
printf("%d ", ordered[i]);
}
printf("\n");
if( i < size )
{
#ifdef SYMETRIC_ALGO
printf("No ordered data (%d values) : ", size - i - nsorted);
for( ; i < size - nsorted ; i++)
{
printf("%d ", ordered[i]);
}
printf("\n");
if (i < size )
{
printf("Ordered data at end (%d values) : ", size - i);
#else
printf("No ordered data (%d values) : ", size - i);
#endif
for( ; i < size ; i++)
{
printf("%d ", ordered[i]);
}
printf("\n");
#ifdef SYMETRIC_ALGO
}
#endif
}
#endif
=> what is the best candidate for to test this new func into the schrodinger's
testsuite ?
@+
Yannoo#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#ifndef uint8_t
#define uint8_t char
#endif
#define DEBUG_ALGO
// #define DEBUG_VALUES
// #define DEBUG_INTERNAL
// #define DEBUG_RESULTS
#define SYMETRIC_ALGO
#ifndef min
#define min(a,b) ((a)<(b)?a:b)
#endif
int size = 1024;
int niter = 1024;
int nsorted = 512;
int nbegin = 512;
int nend = 512;
int nswaps = 0;
uint8_t *unordered;
uint8_t *ordered;
int curriter = 0;
static void bubble_sort (uint8_t * d, int n)
{
int start = 0;
int end = n;
int i, k;
int x;
/* OMG mabubble sort! */
while (start < end) {
for (i = start; i < end - 1; i++) {
if (d[i] > d[i + 1]) {
x = d[i];
d[i] = d[i + 1];
d[i + 1] = x;
#ifdef DEBUG_ALGO
nswaps++;
#endif
#ifdef DEBUG_INTERNAL
// printf("swapped d[%d]=%d and d[%d]=%d \n", i, d[i], i+1, d[i+1]);
printf("presorted : ");
for( k = 0; k < n ; k++)
{
if ( k == i+1 )
{
printf("(%d) ", d[k]);
}else{
printf("%d ", d[k]);
}
}
printf("\n");
#endif
}
}
end--;
for (i = end - 2; i >= start; i--) {
if (d[i] > d[i + 1]) {
x = d[i];
d[i] = d[i + 1];
d[i + 1] = x;
#ifdef DEBUG_ALGO
nswaps++;
#endif
#ifdef DEBUG_INTERNAL
// printf("swapped d[%d]=%d and d[%d=]%d \n", i, d[i], i+1, d[i+1]);
printf("presorted : ");
for( k = 0; k < n; k++)
{
if ( k == i )
{
printf("(%d) ", d[k]);
}else{
printf("%d ", d[k]);
}
}
printf("\n");
#endif
}
}
start++;
}
}
static void bubble_sort2(uint8_t * d, int n, int firsts)
{
int i, j, k;
int x;
int lower, upper, toswap;
int swapped = 0;
if ( (n < 2) || ( firsts < 1) )
return;
/* if ( firsts >= n )
{
firsts = n -1 ;
}
*/
if ( firsts > (n/2) ){ firsts = n/2; }
#ifdef DEBUG_ALGO
// printf("Sort from beginning \n");
#endif
for (i = 0; i < firsts ; i++) {
toswap = 0;
lower = d[i];
for( j = i+1; j < n ; j++) {
if (d[j] < lower ){
toswap = j;
lower = d[j];
}
}
if ( toswap )
{
#ifdef DEBUG_INTERNAL
// printf("swap d[%d]=%d and d[%d]=%d \n", i, d[i], toswap, d[toswap]);
#endif
x = d[i];
d[i] = d[toswap];
d[toswap] = x;
#ifdef DEBUG_ALGO
nswaps++;
#endif
#ifdef DEBUG_INTERNAL
printf("presorted : ");
for( k = 0; k < i+1 ; k++)
{
printf("%d ", d[k]);
}
printf("[");
for( k = i+1 ; k < n; k++)
{
if( k == toswap )
{
printf("(%d) ", d[k]);
}else{
printf("%d ", d[k]);
}
}
printf("]\n");
#endif
}
}
#ifdef SYMETRIC_ALGO
#ifdef DEBUG_ALGO
// printf("Sort from ending \n");
#endif
for (i = n -1 ; i >= (n - firsts) ; i--) {
#ifdef DEGUG_INTERNAL
// printf("i=%d n=%d firsts=%d \n", i, n, firsts);
#endif
toswap = 0;
upper = d[i];
for( j = i-1 ; j >= firsts ; j--) {
if (d[j] > upper ){
#ifdef DEBUG_INTERNAL
// printf("d[%d] > %d (=%d) \n", j, upper, d[j]);
#endif
toswap = j;
upper = d[j];
}
}
if ( toswap )
{
#ifdef DEBUG_INTERNAL
// printf("swap d[%d]=%d and d[%d]=%d \n", i, d[i], toswap, d[toswap]);
#endif
x = d[i];
d[i] = d[toswap];
d[toswap] = x;
#ifdef DEBUG_ALGO
nswaps++;
#endif
#ifdef DEBUG_INTERNAL
printf("presorted : ");
printf("[");
for( k = 0; k < i ; k++)
{
if ( k == toswap)
{
printf("(%d) ", d[k]);
}else{
printf("%d ", d[k]);
}
}
printf("] ");
for( k = i ; k < n; k++)
{
printf("%d ", d[k]);
}
printf("\n");
#endif
}
}
#endif
}
static void sort_u8_ext(uint8_t * d, int n, int firsts)
{
int i, j, k;
int x;
int lower, upper, toswap;
int swapped = 0;
if ( (n < 2) || ( firsts < 1) )
return;
/*
if ( firsts >= n )
{
firsts = n -1 ;
}
*/
if ( firsts > (n/2) ){ firsts = n/2; }
for (i = 0; i < firsts ; i++)
{
toswap = 0;
lower = d[i];
for( j = i+1; j < n ; j++)
{
if (d[j] < lower )
{
toswap = j;
lower = d[j];
}
}
if ( toswap )
{
x = d[i];
d[i] = d[toswap];
d[toswap] = x;
#ifdef DEBUG_ALGO
nswaps++;
#endif
}
}
for (i = n -1 ; i >= (n - firsts) ; i--)
{
toswap = 0;
upper = d[i];
for( j = i-1 ; j >= firsts ; j--)
{
if (d[j] > upper )
{
toswap = j;
upper = d[j];
}
}
if ( toswap )
{
x = d[i];
d[i] = d[toswap];
d[toswap] = x;
#ifdef DEBUG_ALGO
nswaps++;
#endif
}
}
}
static int compare_u8 (const void * a, const void * b)
{
return ( *(uint8_t*)a - *(uint8_t*)b );
}
static void swap_u8 (uint8_t *a, uint8_t *b)
{
uint8_t tmp;
tmp = *a;
*a = *b;
*b = tmp;
}
static void sort_u8_ext2(uint8_t *data, int n, int (*functest)(const void *, const void *), int lowers, int greaters)
{
int i, k;
int minval, maxval;
int imin = 0;
int imax = 0;
int left = 0;
int right = n - 1;
if ( ( lowers < 1 ) || ( lowers > n ) ) { lowers = n / 2; }
if ( (greaters < 1 ) || ( greaters > n ) ) { greaters = n / 2; }
greaters = n - greaters;
curriter = 0;
while( left < right )
{
minval = data[left];
maxval = data[right];
for( i = left + 1 ; i < right ; i++)
{
if( functest( (void *) data + i, (void *) &minval ) <= 0 )
{
minval = data[i];
imin = i;
}
if( functest( (void *) data + i, (void *) &maxval ) >= 0 )
{
maxval = data[i];
imax = i;
}
}
if ( imin )
{
swap_u8( data + left , data + imin );
#ifdef DEBUG_ALGO
nswaps++;
#endif
}
if ( imax )
{
swap_u8( data + right, data + imax );
#ifdef DEBUG_ALGO
nswaps++;
#endif
}
left++;
#ifdef DEBUG_VALUES
printf("iteration %d : ", ++curriter);
for( k = 0; k < left; k++)
{
printf("%d ", data[k]);
}
/* if( left < right ) */ printf("[");
for( k = left ; k < right ; k++)
{
printf("%d ", data[k]);
}
/* if( right > left ) */ printf("] ");
for( k = right ; k < n ; k++)
{
printf("%d ", data[k]);
}
printf("\n");
#endif
right--;
// printf("(left=%d right=%d lowers=%d greaters=%d) \n", left, right, lowers, greaters);
if ( ( left > lowers ) && ( right < greaters ) )
{
/* Early terminaison */
printf("Early termination (left=%d right=%d lowers=%d greaters=%d) \n",
left, right, lowers, greaters);
return;
}
}
}
int main(int argc, char **argv){
int i;
clock_t start, end;
float timer1=0, timer2=0, timer3=0;
float cpu_time_used;
if (argc > 1 )
{
niter = atoi(argv[1]);
if ( argc > 2 )
{
size = atoi(argv[2]);
if ( argc > 3 )
{
nsorted = atoi(argv[3]);
}else{
nsorted = size;
}
}
printf("Set test with nbiter=%d, size=%d and nsorted=%d \n", niter, size, nsorted);
#ifndef SYMETRIC_ALGO
if ( nsorted > size )
{
printf("update nsorted (%d) to max size value (%d) \n",
nsorted, size);
nsorted = size;
}
#else
if ( nsorted > (size/2) )
{
printf("update nsorted (%d) to the middle of the size value (%d), so %d \n", nsorted, size, size/2);
nsorted = size /2 ;
}
#endif
}else{
printf("syntax : %s niter [size=%d] [nsorted=%d] \n",
argv[0], niter, size, nsorted);
return 0;
}
unordered = (uint8_t *) malloc(size);
ordered = (uint8_t *) malloc(size);
srand ( time(NULL) );
for( i = 0; i < size; i++ )
{
// unordered[i] = 127 - (i % 217);
// unordered[i] = i % 5 + 10;
unordered[i] = rand() % 255;
}
#ifdef DEBUG_RESULTS
printf("\nOriginal data (%d values) : ", size);
for( i = 0; i < size; i++)
{
printf("%d ", unordered[i]);
}
printf("\n");
#endif
printf("\n*********************************");
printf("\n* Test original bubble_sort algo *");
printf("\n**********************************\n");
printf("(loop=%d, size=%d)\n", niter, size);
for( i = 0; i < niter ; i++)
{
// printf("Iteration %d \n", i);
memcpy(ordered,unordered, size);
nswaps=0;
start = clock();
bubble_sort(ordered, size);
end = clock();
cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
timer1 += cpu_time_used;
}
printf("%.3f seconds \n", timer1);
#ifdef DEBUG_ALGO
printf("(%d swaps per iterations) \n", nswaps);
#endif
#ifdef DEBUG_RESULTS
printf("Ordered data (%d values) : ", size);
for( i = 0; i < size; i++)
{
printf("%d ", ordered[i]);
}
printf("\n");
#endif
printf("\n**************************************");
printf("\n* Test the standard quicksort routine *");
printf("\n*************************************\n");
printf("(nbiter=%d, size=%d)\n", niter, size);
for( i = 0; i < niter ; i++)
{
// printf("Iteration %d \n", i);
memcpy(ordered,unordered, size);
nswaps=0;
start = clock();
qsort (ordered, size, sizeof(uint8_t), compare_u8);
end = clock();
cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
timer2 += cpu_time_used;
}
printf("%.3f seconds \n", timer2);
#ifdef DEBUG_RESULTS
printf("Ordered data (%d values) : ", size);
for( i = 0; i < size; i++)
{
printf("%d ", ordered[i]);
}
printf("\n");
#endif
printf("\n*********************************");
printf("\n*Test modified bubble_sort algo *");
printf("\n*********************************\n");
#ifndef SYMETRIC_ALGO
printf("(loop=%d, size=%d, nsorted=%d)\n", niter, size, nsorted);
#else
printf("(loop=%d, size=%d, nsorted=(%d+%d)\n",
niter, size, nsorted, nsorted);
#endif
for( i = 0; i < niter ; i++)
{
// printf("Iteration %d \n", i);
memcpy(ordered,unordered, size);
nswaps=0;
start = clock();
#ifdef DEBUG_INTERNAL
bubble_sort2(ordered, size, nsorted);
#else
// sort_u8_ext(ordered, size, nsorted);
sort_u8_ext2( ordered, size, compare_u8, nsorted, nsorted);
#endif
end = clock();
cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
timer3 += cpu_time_used;
}
printf("%.3f seconds \n", timer3);
#ifdef DEBUG_ALGO
printf("(%d swaps per iteration)\n", nswaps);
#endif
#ifdef DEBUG_RESULTS
#ifndef SYMETRIC_ALGO
printf("Ordered data (%d values) : ", nsorted);
#else
printf("Ordered data at the begin (%d values) : ", nsorted);
#endif
for( i = 0; i < nsorted; i++)
{
printf("%d ", ordered[i]);
}
printf("\n");
if( i < size )
{
#ifdef SYMETRIC_ALGO
printf("No ordered data (%d values) : ", size - i - nsorted);
for( ; i < size - nsorted ; i++)
{
printf("%d ", ordered[i]);
}
printf("\n");
if (i < size )
{
printf("Ordered data at end (%d values) : ", size - i);
#else
printf("No ordered data (%d values) : ", size - i);
#endif
for( ; i < size ; i++)
{
printf("%d ", ordered[i]);
}
printf("\n");
#ifdef SYMETRIC_ALGO
}
#endif
}
#endif
return 0;
}
------------------------------------------------------------------------------
Live Security Virtual Conference
Exclusive live event will cover all the ways today's security and
threat landscape has changed and how IT managers can respond. Discussions
will include endpoint security, mobile security and the latest in malware
threats. http://www.accelacomm.com/jaw/sfrnl04242012/114/50122263/
_______________________________________________
Schrodinger-devel mailing list
Schrodinger-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/schrodinger-devel
