demo.c File Reference

A benchmark demo driver for medians_1D and a couple of other methods. More...

#include "medians_1D.h"
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <time.h>
#include <string.h>
#include <math.h>
#include <float.h>

Include dependency graph for demo.c:

Go to the source code of this file.

Defines
#define	BIG_NUM   (1024*1024)
	Number of elements in the target array.
#define	MAX_ARRAY_VALUE   1024
	Random test data; generated values are in [0...MAX_ARRAY_VALUE-1].
#define	N_METHODS   5
	Number of search methods tested.
#define	odd(x)   ((x)&1)
	Macro to determine an integer's oddness.
#define	PIX_SWAP(a, b)   { pixelvalue temp=(a);(a)=(b);(b)=temp; }
#define	PIX_STACK_SIZE   50
Functions
void	bench (int, size_t)
int	compare (const void *f1, const void *f2)
	This function is only useful to the qsort() routine.
void	pixel_qsort (pixelvalue *, int)
	Old and supposedly optimized quicksort algorithm.
pixelvalue	median_AHU (pixelvalue *list, int n)
	This function uses select_k to find the median.
pixelvalue	select_k (int, pixelvalue *, int)
	Called by median_AHU().
int	main (int argc, char *argv[])
	Main driver demo for median search routines.
Variables
static const char	rcsid []

---

Detailed Description

A benchmark demo driver for medians_1D and a couple of other methods.

Comparison of qsort-based and optimized median search methods for a 1-D data array. The data type is flexible.

Original code by Nicolas Devillard <ndevilla@free.fr> August 1998. Modified by Stephen Arnold <stephen.arnold@acm.org> August 2005. This code in public domain.

A note about this benchmarking method:

The reported times indicate the actual time spent on CPU, they are quite dependent on CPU load. However, the test is quite fast and it is reasonable to assume a constant machine load throughout the test.

Definition in file demo.c.

---

Define Documentation

#define BIG_NUM   (1024*1024)

Number of elements in the target array.

Definition at line 32 of file demo.c.

Referenced by bench(), and main().

#define MAX_ARRAY_VALUE   1024

Random test data; generated values are in [0...MAX_ARRAY_VALUE-1].

Definition at line 35 of file demo.c.

Referenced by bench().

#define N_METHODS   5

Number of search methods tested.

Definition at line 38 of file demo.c.

Referenced by bench().

#define odd

(

x

)

((x)&1)

Macro to determine an integer's oddness.

Definition at line 41 of file demo.c.

Referenced by bench(), and median_AHU().

#define PIX_STACK_SIZE   50

Definition at line 231 of file demo.c.

Referenced by pixel_qsort().

#define PIX_SWAP	(	a,
		b		)	{ pixelvalue temp=(a);(a)=(b);(b)=temp; }

Definition at line 230 of file demo.c.

Referenced by pixel_qsort().

---

Function Documentation

void bench	(	int	,
		size_t
	)

Definition at line 50 of file demo.c.

References BIG_NUM, MAX_ARRAY_VALUE, median_AHU(), N_METHODS, odd, pixel_qsort(), quick_select(), torben(), and wirth().

Referenced by main().

{
    int         i ;
    int         mednum ;
    pixelvalue  med[N_METHODS] ;

    clock_t     chrono ;
    double       elapsed ;

    pixelvalue  *   array_init,
                *   array ;


    srand48(getpid()) ;

    if (verbose) {
        printf("generating element values...\n") ;
        fflush(stdout) ;
    }
    if (array_size<1) array_size = BIG_NUM ;

    if (verbose) {
        printf("array size: %ld\n", (long)array_size) ;
    } else {
        printf("%ld\t", (long)array_size) ;
    }
    
    array_init = malloc(array_size * sizeof(pixelvalue)) ;
    array      = malloc(array_size * sizeof(pixelvalue)) ;

    if (array_init==NULL || array==NULL) {
        printf("memory allocation failure: aborting\n") ;
        return ;
    }

    for (i=0 ; i<array_size; i++) {
        array_init[i] = (pixelvalue)(lrand48() % MAX_ARRAY_VALUE) ;
    }
    mednum = 0 ;

    memcpy(array, array_init, array_size * sizeof(pixelvalue)) ;
    if (verbose) {
        printf("quick select    :\t") ;
        fflush(stdout) ;
    }
    chrono = clock() ;
    med[mednum] = quick_select(array, array_size) ;
    elapsed = (double)(clock() - chrono) / (double)CLOCKS_PER_SEC ;
    if (verbose) {
        printf("%5.3f sec\t", elapsed) ;
        fflush(stdout) ;
        printf("med %g\n", (double)med[mednum]) ;
        fflush(stdout) ;
    } else {
        printf("%5.3f\t", elapsed) ;
        fflush(stdout) ;
    }
    mednum++ ;

    memcpy(array, array_init, array_size * sizeof(pixelvalue)) ;
    if (verbose) {
        printf("Wirth median    :\t") ;
        fflush(stdout) ;
    }
    chrono = clock() ;
    med[mednum] = wirth(array, array_size) ;
    elapsed = (double)(clock() - chrono) / (double)CLOCKS_PER_SEC ;
    if (verbose) {
        printf("%5.3f sec\t", elapsed) ;
        fflush(stdout) ;
        printf("med %g\n", (double)med[mednum]) ;
        fflush(stdout) ;
    } else {
        printf("%5.3f\t", elapsed) ;
        fflush(stdout) ;
    }
    mednum++ ;

    memcpy(array, array_init, array_size * sizeof(pixelvalue)) ;
    if (verbose) {
        printf("AHU median      :\t") ;
        fflush(stdout) ;
    }
    chrono = clock() ;
    med[mednum] = median_AHU(array, array_size) ;
    elapsed = (double)(clock() - chrono) / (double)CLOCKS_PER_SEC ;
    if (verbose) {
        printf("%5.3f sec\t", elapsed) ;
        fflush(stdout) ;
        printf("med %g\n", (double)med[mednum]) ;
        fflush(stdout) ;
    } else {
        printf("%5.3f\t", elapsed) ;
        fflush(stdout) ;
    }
    mednum++ ;

    memcpy(array, array_init, array_size * sizeof(pixelvalue)) ;
    if (verbose) {
        printf("torben          :\t") ;
        fflush(stdout) ;
    }
    chrono = clock() ;
    med[mednum] = torben(array, array_size) ;
    elapsed = (double)(clock() - chrono) / (double)CLOCKS_PER_SEC ;
    if (verbose) {
        printf("%5.3f sec\t", elapsed) ;
        fflush(stdout) ;
        printf("med %g\n", (double)med[mednum]) ;
        fflush(stdout) ;
    } else {
        printf("%5.3f\t", elapsed) ;
        fflush(stdout) ;
    }
    mednum++ ;

    memcpy(array, array_init, array_size * sizeof(pixelvalue)) ;
    if (verbose) {
        printf("fast pixel sort :\t") ;
        fflush(stdout) ;
    }
    chrono = clock() ;
    pixel_qsort(array, array_size) ;
    elapsed = (double)(clock() - chrono) / (double)CLOCKS_PER_SEC ;

    if (odd(array_size)) {
        med[mednum] = array[array_size/2] ;
    } else {
        med[mednum] = array[(array_size/2) -1] ;
    }

    if (verbose) {
        printf("%5.3f sec\t", elapsed) ;
        fflush(stdout) ;
        printf("med %g\n", (double)med[mednum]) ;
        fflush(stdout) ;
    } else {
        printf("%5.3f\t", elapsed) ;
        fflush(stdout) ;
    }
    mednum++ ;

    free(array) ;
    free(array_init) ;

    for (i=1 ; i<N_METHODS ; i++) {
        if (fabs(med[i-1] - med[i]) > 10 * FLT_EPSILON) {
            printf("diverging median values!\n") ;
            fflush(stdout) ;
        }
    }
    printf("\n") ;
    fflush(stdout) ;
    return ;
}

Here is the call graph for this function:

Here is the caller graph for this function:

int compare	(	const void *	,
		const void *
	)

This function is only useful to the qsort() routine.

Definition at line 216 of file demo.c.

{ return ( *(pixelvalue*)f1 > *(pixelvalue*)f2) ? 1 : -1 ; } 

int main	(	int	argc,
		char *	argv[]
	)

Main driver demo for median search routines.

Definition at line 370 of file demo.c.

References bench(), and BIG_NUM.

{
    int     i ;
    int     from, to, step ;
    int     count ;

    if (argc<2) {
        printf("usage:\n") ;
        printf("%s <n>\n", argv[0]) ;
        printf("\tif n=1 the output is verbose for one attempt\n") ;
        printf("\tif n>1 the output reads:\n") ;
        printf("\t# of elements | method1 | method2 | ...\n") ;
        printf("\n") ;
        printf("%s <from> <to> <step>\n", argv[0]) ;
        printf("\twill loop over the number of elements in input\n") ;
        printf("\n") ;
        return 0 ;
    }

    if (argc==2) {
        count = atoi(argv[1]) ;
        if (count==1) {
            bench(1, BIG_NUM) ;
        } else {
            printf("Size\tQS\tWirth\tAHU\tTorben\tpixel sort\n") ;
            for (i=0 ; i<atoi(argv[1]) ; i++) {
                bench(0, BIG_NUM) ;
            }
        }
    } else if (argc==4) {
        from = atoi(argv[1]) ;
        to   = atoi(argv[2]) ;
        step = atoi(argv[3]) ;
        for (count=from ; count<=to ; count+=step) {
            bench(0, count) ;
        }
        return 0 ;
    }

}

Here is the call graph for this function:

pixelvalue median_AHU	(	pixelvalue *	,
		int
	)

This function uses select_k to find the median.

Definition at line 359 of file demo.c.

References odd, and select_k().

Referenced by bench().

{
    if (odd(n)) {
        return select_k((n/2)+1, list, n) ;
    } else {
        return select_k((n/2), list, n) ;
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

void pixel_qsort	(	pixelvalue *	pix_arr,
		int	npix
	)

Old and supposedly optimized quicksort algorithm.

Function : pixel_qsort()

• In : pixel array, size of the array
• Out : void
• Job : sort out the array of pixels
• Note : optimized implementation, unreadable.

Definition at line 233 of file demo.c.

References PIX_STACK_SIZE, and PIX_SWAP.

Referenced by bench().

{
    int         i,
                ir,
                j,
                k,
                l;
    int *       i_stack ;
    int         j_stack ;
    pixelvalue  a ;

    ir = npix ;
    l = 1 ;
    j_stack = 0 ;
    i_stack = malloc(PIX_STACK_SIZE * sizeof(pixelvalue)) ;
    for (;;) {
        if (ir-l < 7) {
            for (j=l+1 ; j<=ir ; j++) {
                a = pix_arr[j-1];
                for (i=j-1 ; i>=1 ; i--) {
                    if (pix_arr[i-1] <= a) break;
                    pix_arr[i] = pix_arr[i-1];
                }
                pix_arr[i] = a;
            }
            if (j_stack == 0) break;
            ir = i_stack[j_stack-- -1];
            l  = i_stack[j_stack-- -1];
        } else {
            k = (l+ir) >> 1;
            PIX_SWAP(pix_arr[k-1], pix_arr[l])
            if (pix_arr[l] > pix_arr[ir-1]) {
                PIX_SWAP(pix_arr[l], pix_arr[ir-1])
            }
            if (pix_arr[l-1] > pix_arr[ir-1]) {
                PIX_SWAP(pix_arr[l-1], pix_arr[ir-1])
            }
            if (pix_arr[l] > pix_arr[l-1]) {
                PIX_SWAP(pix_arr[l], pix_arr[l-1])
            }
            i = l+1;
            j = ir;
            a = pix_arr[l-1];
            for (;;) {
                do i++; while (pix_arr[i-1] < a);
                do j--; while (pix_arr[j-1] > a);
                if (j < i) break;
                PIX_SWAP(pix_arr[i-1], pix_arr[j-1]);
            }
            pix_arr[l-1] = pix_arr[j-1];
            pix_arr[j-1] = a;
            j_stack += 2;
            if (j_stack > PIX_STACK_SIZE) {
                printf("stack too small in pixel_qsort: aborting");
                exit(-2001) ;
            }
            if (ir-i+1 >= j-l) {
                i_stack[j_stack-1] = ir;
                i_stack[j_stack-2] = i;
                ir = j-1;
            } else {
                i_stack[j_stack-1] = j-1;
                i_stack[j_stack-2] = l;
                l = i;
            }
        }
    }
    free(i_stack) ;
}

Here is the caller graph for this function:

pixelvalue select_k	(	int	k,
		pixelvalue *	list,
		int	n
	)

Called by median_AHU().

Function : select_k()

• In : element to search for, list of pixelvalues, # of values
• Out : pixelvalue
• Job : find out the kth smallest value of the list
• Note : recursively called by median_AHU()

Definition at line 315 of file demo.c.

Referenced by median_AHU().

{
    int             n1 = 0,
                    n2 = 0,
                    n3 = 0 ;
    pixelvalue  *   S ;
    int             i, j ;
    pixelvalue      p ;

    if (n==1) return list[0] ;
    p = list[(n>>1)] ;
    for (i=0 ; i<n ; i++) {
        if (list[i]<p) {
            n1++ ;
        } else if (fabs(list[i] - p) < 10 * FLT_EPSILON) {
            n2++ ;
        } else {
            n3++ ;
        }
    }
    if (n1>=k) {
        S = malloc(n1*sizeof(pixelvalue)) ;
        j = 0 ;
        for (i=0 ; i<n ; i++) {
            if (list[i]<p) S[j++] = list[i] ;
        }
        p = select_k(k, S, n1) ;
        free(S) ;
    } else {
        if ((n1+n2)<k) {
            S = malloc(n3 * sizeof(pixelvalue)) ;
            j = 0 ;
            for (i=0 ; i<n ; i++) {
                if (list[i]>p) S[j++] = list[i] ;
            }
            p = select_k(k-n1-n2, S, n3) ;
            free(S) ;
        }
    }
    return p ;
}

Here is the caller graph for this function:

---

Variable Documentation

const char rcsid[] [static]

Initial value:

    "$Id"

Definition at line 18 of file demo.c.

---