QuickSort(), native code, Force compiler 
Author Message
 QuickSort(), native code, Force compiler

Hi all,

Quote:
> 1. Created a quicksort in Clipper code for single dimentional arrays.
> ...
> Folks, if you are sorting arrays, you just gotta try this function.
> ...
> This is interesting, I did some testing of the QuickSort() function
> and in my (simple and trivial) test cases it didn't appear to offer
> anything over Clipper's asort().
> ...
> Thanks for looking into this.  For some time, I've been annoyed by
> how slowly Clipper sorts arrays.  I haven't found a replacement
> function yet (and don't know a low level language that would let me
> write one myself).

Here is some code to compare with the previously posted one. It appears
that the simple algorithm used in the sample function, called here
ClipperSort(), is faster than QuickSort() or asort(). In addition,
let me present the same algorithm implemented in the Force language.

//----- Clipper module: test.prg ------------------------------------

proc main
local aArray := {    5,  33,  999,    55,     1, ;
                   100,  66,    0,     7,    44, ;
                  1320,  99,  -87, 32767, 32766, ;
                  -308, 363, 3536,   374, 12209 }
local n
local nTime
? "Started 10,000 iterations of sorting a 20-element integer array"
nTime := seconds()
for n := 1 to 10000                           // measured times (sec)  ?
// QuickSort( aArray )                        // 32.90                 ?
// asort( aArray )                            // 12.58                 ?
// ClipperSort( aArray, len( aArray ) )       //  7.31                 ?
   ForceSort( aArray, len( aArray ) )         //  1.82                 ?
next
? "Time elapsed", seconds() - nTime
wait
for n := 1 to 20
   ? aArray[ n ]
next
return

proc ClipperSort( aArr, nArraySize )
local n
local x, y
local lPass := .f.
do while .not. lPass
   lPass := .t.
   for n := 1 to nArraySize - 1
      x := aArr[ n ]
      y := aArr[ n + 1 ]
      if x > y
         aArr[ n ] := y
         aArr[ n + 1 ] := x
         lPass := .f.
      endif
   next
enddo
return

//----- Force module: fsort.prg -------------------------------------

func int _parinfo extern             // Native code compilers, like C
param value int iParamNum            // or Force, require that functions
                                     // are declared before they are
func int _parinfa extern             // used.
param value int  iParamNum, ;        // Such declarations are called
      value uint uArrayIndex         // prototypes.
                                     // The prototypes for the standard
func int _parni extern               // functions of these languages are
param value int iParamNum, ;         // placed in include files, similarly
      value int iArrayIndex          // to the declarations in Clipper's
                                     // .ch files.
func logical _storni extern          // <=== The four functions declared
param value int iNumber, ;           // here are resident in clipper.lib
      value int iParamNum, ;         // and are necessary for accessing
      value int iArrayIndex          // Clipper variables from native code.

#define TYPE_NUMERIC   2
#define TYPE_ARRAY   512

#pragma W_FUNC_PROC-

/*
The function below is the exact mirror of the ClipperSort() function
shown above. The only substantial difference is that the elements of
the array passed from the calling Clipper code are accessed via
calls to the above-declared _parni() and _storni() functions, instead
of directly by [index] positions. This sample function deals with integer
arrays only. A more generic array sorter would call the appropriate
data retriever functions in clipper.lib, after checking the type of
the array.
*/

//-------------------
proc ForceSort Pascal
vardef                               // Native code compilers need to know
   int     nArraySize                // the data type of all variables.
   int     n                         // Such explicit declarations also
   int     x, y                      // help the programmer to find bugs
   logical lPass                     // during compilation rather than
enddef                               // at runtime.
nArraySize := _parni( 2, 0 )
if    _parinfo( 0 )    != 2 .or. ;            // Here all parameters are
      _parinfo( 1 )    != TYPE_ARRAY .or. ;   // type-checked to avoid
      _parinfa( 1, 1 ) != TYPE_NUMERIC .or. ; // runtime errors.
      nArraySize < 2
   return                                     // Return if params invalid.
endif
lPass := .f.
do while .not. lPass                          // The Force language is
   lPass := .t.                               // syntactically the closest
   for n := 1 to nArraySize - 1               // relative of Clipper
      x := _parni( 1, n )                     // amongst all native code
      y := _parni( 1, n + 1 )                 // languages. Force has
      if x > y                                // speed and power similar
         _storni( y, 1, n )                   // to C, but it does not
         _storni( x, 1, n + 1 )               // pose the learning curve
         lPass := .f.                         // of C, often intimidating
      endif                                   // to xBase programmers.
   next                                       // In addition, Force has
enddo                                         // the same database commands
endproc                                       // and other xBase elements
                                              // like Clipper.

The above code is written in Force 4.0. This version of Force is
not yet available on the market, so I include the linkable object code
of fsort.prg below in uuencoded form, for your testing convenience.

begin 600 FSORT.OBJ
<encoded_portion_removed>
end

Zoltan (Force Development Team)

____________________________________________________

System Analyst,  DecaGen Software,  Szeged,  Hungary
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~



Thu, 11 Nov 1999 03:00:00 GMT  
 
 [ 1 post ] 

 Relevant Pages 

1. Native code compilers

2. Re(try): A native-code compiler in Forth

3. A native-code Java compiler in Forth

4. What is a 'native code' compiler

5. public relase of HiPE native-code Erlang compiler

6. XDS native code compiler for NT

7. XDS native code Modula/Oberon compilers: DEMO is available for MS-DOS

8. XDS native code compiler for NT

9. XDS native code Modula/Oberon compilers: DEMO is available for MS-DOS

10. OCaml native code compiler has little to do with C--

11. native-code Scheme compilers for Linux

12. Cobol-Compiler on Linux wanted - native code

 

 
Powered by phpBB® Forum Software