Subject: ADS/CL Sorting speed
Date: Sun, 18 May 1997 21:21:21 GMT
From: vnestr@netvision.net.il (Vladimir Nesterovsky)
Organization: .
CC: Reini Urban <rurban@sbox.tu-graz.ac.at>,
     "Tony Tanzillo" <tony.tanzillo@worldnet.att.net>,
     Peter Petrov <basis@access.digex.net>
Newsgroups: comp.cad.autocad

At http://xarch.tu-graz.ac.at/autocad/ads/ we read:

..TSW_SORT :
.. qsort for numbers by William Kiernan: doc, CPP source, exe --
.. I have it return reals when there are more than 32,767 elements in the
.. input list; a list of 33,000 random integers takes about 30 seconds to
.. sort on my P6-150, and have it return indices in reverse order, so you
.. can index a master list when you are sorting a list that you made up by
.. cons-ing a function of the elements of the master list.

Well, I for long wanted to check the speed of my CVSORT, and tonight
I finally did so. To build the random list I used Vital LISP in its
internal LEX mode, which is very much like Common Lisp, so it has
random-number generator built-in. I used

(dotimes (k 33000) (push (random& 33000) ints))

to build INTS as a list of 33000 integers. When trying to sort I
unfortunately ran into a bug in ViLL, and found out that to sort
properly, a list must start with a minimum value (that may be
discarded later), so I used

(push 0 INTS)

to do that.
I made the reals-list with

(setq REALS (mapcar (function (lambda(x)
  (* x (+ 0.95 (/ (random& 1000) 10000.0)))))
  INTS))

As I found out, ViLL's built-in sorting functions,
SORT in LEX mode and VLX-SORT in AutoLISP mode
(available in professional version), left only
unique elements in sorted list, and that's the
reason I added some random fluctuations into INTS
values when making them real. At this point I've
created a LSP file with this two lists for future
testings in ViLL AutoLISP mode and in regular LISP
using my ADS CVSORT function, and in AllegroCL.

I did the tests on P5-90 machine with 16 Meg RAM
running WIN95.

Still in LEX mode in Vital LISP, I used

(time-info (sort INTS '<))

This took _5.7_ sec for INTS and 6.4 for REALS! (compare it to 30 sec.)

In ViLL's AutoLISP mode, after loading the file which
defined the two list variables, I used

(defun time(a)(command"cdate")(eval a)(command"cdate"))
(time '(vlx-sort INTS '<))

which yield 9.0 sec and for REALS -- 9.6 sec. -- still pretty fast!
I guess compilation can't make any dufference here, as
we're talking only about 1 function call. It's also a destructive
call in ViLL, meaning only one occurence of each non-unique element
is left in sorted list.

Inside R12/Dos (null display configured) _my ADS routine_
callable from LISP, CVSORT, sorted the same random list
INTS, defined by loading that same file, in __2.5__ seconds (!!!),
and REALS in 2.75 sec average. I used (time '(CVSORT INTS))
for that. Unlike VLX-SORT, CVSORT sorts a list while keeping
all elements in it.

It's _so_ fast probably due to some "clever" tricks when I sort them
in-place, only relinking resbufs in list acoording to the results of
standard QSORT C-function, thus avoiding unnecessary memory allocations.
I have build this ADS app with Watcom 10.5, using my custom made
ResBufList class.

As usual, I've checked this also on Allegro CL Lite for Windows
(it's a Windows based Common LISP system, which can't be used
with ACAD, unfortunately).

With (time (csort ints #'<)) I got 1.93 (!) seconds average sorting
time for INTS, and 2.53 for REALS variable.

I have also CSORT function (as I've published about a year ago here
in cca) that lets me sort ANY type of elements by ANY user-supplied LISP
value-function in ADS and is also very fast. Still need to check its
speed, but it can't be very different from that of CVSORT, 'cause
it works the same way, with only a little overhead.

----------------------------------
Live long and prosper :)
Vlad