Author Topic: Sorting using MergeSort  (Read 3020 times)

0 Members and 2 Guests are viewing this topic.

irneb

  • Water Moccasin
  • Posts: 1794
  • ACad R9-2016, Revit Arch 6-2016
Sorting using MergeSort
« on: May 21, 2012, 11:33:48 AM »
I was actually very surprised at the speed differential (after compiling  :lmao: ):
Code - Auto/Visual Lisp: [Select]
  1. (defun sort-merge-i  (lst comp / l r item res)
  2.   (setq res (mapcar 'list lst))
  3.   (while (> (length res) 1)
  4.     (setq lst nil)
  5.     (while res
  6.       (setq item nil l (car res) r (cadr res) res (cddr res))
  7.       (while (and l r)
  8.         (if (apply comp (list (car l) (car r)))
  9.           (setq item (cons (car l) item)
  10.                 l (cdr l))
  11.           (setq item (cons (car r) item)
  12.                 r (cdr r))))
  13.       (foreach n l (setq item (cons n item)))
  14.       (foreach n r (setq item (cons n item)))
  15.       (setq lst (cons (reverse item) lst)))
  16.     (setq res lst))
  17.   res)
  18.  
  19.  
  20.  
  21. (defun sort-merge-r  (lst comp / v l r)
  22.   (cond ((> (setq v (length lst)) 2)
  23.          (setq v (/ v 2))
  24.          (repeat v
  25.            (setq l   (cons (car lst) l)
  26.                  lst (cdr lst)))
  27.          (setq l (sort-merge-r l comp)
  28.                r (sort-merge-r lst comp)
  29.                v nil)
  30.          (while (and l r)
  31.            (if (apply comp (list (car l) (car r)))
  32.              (setq v (cons (car l) v)
  33.                    l (cdr l))
  34.              (setq v (cons (car r) v)
  35.                    r (cdr r))))
  36.          (foreach n l (setq v (cons n v)))
  37.          (foreach n r (setq v (cons n v)))
  38.          (reverse v))
  39.         ((<= v 1) lst)
  40.         ((apply comp lst) lst)
  41.         (t (reverse lst))))
Before compiling the lisp, as expected just silly slow:
Code: [Select]
Benchmarking ... done for 1024 iterations. Sorted from fastest.
Statement                                Increment  Time(ms) Normalize  Relative
--------------------------------------------------------------------------------
(VL-SORT LST (QUOTE <))                       1024      1670      1670     37.37
(SORT-MERGE-I LST (QUOTE <))                    32      1856     59392      1.05
(SORT-MERGE-R LST (QUOTE <))                    32      1950     62400      1.00
--------------------------------------------------------------------------------
But compile it and the vl-sort don't look SOOOO good anymore:
Code: [Select]
Benchmarking ... done for 32768 iterations. Sorted from fastest.
Statement                                Increment  Time(ms) Normalize  Relative
--------------------------------------------------------------------------------
(SORT-MERGE-R LST (QUOTE <))                 32768      1154      1154      1.03
(SORT-MERGE-I LST (QUOTE <))                 32768      1186      1186      1.00
(VL-SORT LST (QUOTE <))                      32768      1186      1186      1.00
--------------------------------------------------------------------------------
Sample was a list of 1000 random floating points.
Common sense - the curse in disguise. Because if you have it, you have to live with those that don't.

VovKa

  • Water Moccasin
  • Posts: 1632
  • Ukraine
Re: Sorting using MergeSort
« Reply #1 on: May 21, 2012, 12:12:28 PM »
Quote
Elapsed milliseconds / relative speed for 1024 iteration(s):

    (VL-SORT LST (QUOTE <))...........1953 / 16.63 <fastest>
    (SORT-MERGE-I LST (QUOTE <)).....31532 / 1.03
    (SORT-MERGE-R LST (QUOTE <)).....32484 / 1.00 <slowest>

irneb

  • Water Moccasin
  • Posts: 1794
  • ACad R9-2016, Revit Arch 6-2016
Re: Sorting using MergeSort
« Reply #2 on: May 22, 2012, 03:06:55 AM »
Extremely strange ... yesterday the timings were nearly exactly the same, today the best I get is with lsa compilation - and that gives a similar 1:16 speed differential (otherwise the 1:30+ as per my original test). There must've happened something strange with that test, perhaps a bug somewhere.
Common sense - the curse in disguise. Because if you have it, you have to live with those that don't.

HasanCAD

  • Swamp Rat
  • Posts: 1422
Re: Sorting using MergeSort
« Reply #3 on: May 22, 2012, 08:14:37 AM »
Code: [Select]
[quote author=irneb link=topic=41777.msg468960#msg468960 date=1337614428]
Statement                                   Increment  Time(ms) Normalize  Relative
--------------------------------------------------------------------------------
(SORT-MERGE-R LST (QUOTE <))                 32768      1154      1154      1.03
(SORT-MERGE-I LST (QUOTE <))                 32768      1186      1186      1.00
(VL-SORT LST (QUOTE <))                      32768      1186      1186      1.00
--------------------------------------------------------------------------------
Sample was a list of 1000 random floating points.
[/quote]

How do you compare between differences lisps?

irneb

  • Water Moccasin
  • Posts: 1794
  • ACad R9-2016, Revit Arch 6-2016
Re: Sorting using MergeSort
« Reply #4 on: May 22, 2012, 08:24:44 AM »
Well instead of running the normal Benchmark ... which would take ages to compare two codes with extremely different speeds, I've made one that "estimates" the differences by running each until it's taken more than one second, then multiplies the times by the differences in iterations. Thus it takes no more than a bit more than one second per code:
Code - Auto/Visual Lisp: [Select]
  1.  
  2. (defun quickbench  (statements / maxinc _printformat _rtodec)
  3.   (princ "Benchmarking ")
  4.   (setq statements (mapcar '(lambda (statement / inc time start stop)
  5.                               (princ ".")
  6.                               (setq inc 1 time 0.)
  7.                               (while (< time 1000)
  8.                                 (setq inc   (* inc 2)
  9.                                       start (getvar "MilliSecs"))
  10.                                 (repeat (/ inc 2) (eval statement))
  11.                                 (setq stop (getvar "MilliSecs"))
  12.                                 (setq time (+ time (- stop start))))
  13.                               (list statement (/ inc 2) time))
  14.                            statements)
  15.         maxinc     (cadar statements))
  16.   (foreach statement  (cdr statements)
  17.     (if (< maxinc (cadr statement))
  18.       (setq maxinc (cadr statement))))
  19.   (setq statements
  20.          (vl-sort (mapcar '(lambda (statement /)
  21.                              (append statement (list (* (last statement) (/ maxinc (cadr statement))))))
  22.                           statements)
  23.                   '(lambda (a b) (< (last a) (last b)))))
  24.   (princ (strcat " done for "
  25.                  (rtos (float maxinc) 2 0)
  26.                  " iterations. Sorted from fastest.\n"
  27.                  "Statement                                Increment  Time(ms) Normalize  Relative\n"
  28.                  "--------------------------------------------------------------------------------\n"))
  29.   (setq maxinc (float (last (last statements))))
  30.   (defun _rtodec (val d / p)
  31.     (setq val (rtos val 2 d))
  32.     (cond ((> d 0)
  33.            (if (not (setq p (vl-string-search "." val))) (setq p (strlen val) val (strcat val ".")))
  34.            (repeat (- d (- (strlen val) p) -1) (setq val (strcat val "0")))))
  35.     val)
  36.   (defun _printformat (statement / a v p)
  37.     (princ (if (> (strlen (setq a (vl-princ-to-string (car statement)))) 40)
  38.              (setq a (strcat (substr a 1 36) "...)"))
  39.              a))
  40.     (repeat (- 40 (strlen a)) (princ " "))
  41.     (setq a (rtos (float (cadr statement)) 2 0))
  42.     (repeat (- 10 (strlen a)) (princ " "))
  43.     (princ a)
  44.     (setq a (rtos (float (caddr statement)) 2 0))
  45.     (repeat (- 10 (strlen a)) (princ " "))
  46.     (princ a)
  47.     (setq a (rtos (setq v (float (last statement))) 2 0))
  48.     (repeat (- 10 (strlen a)) (princ " "))
  49.     (princ a)
  50.     (setq a (_rtodec (/ maxinc v) 2))
  51.     (repeat (- 10 (strlen a)) (princ " "))
  52.     (princ a)
  53.     (princ "\n"))
  54.   (foreach statement statements (_printformat statement))
  55.   (princ "--------------------------------------------------------------------------------")
  56.   (princ))
It's not as exact as Michael's code, but in this case doesn't take a hour to run.
Common sense - the curse in disguise. Because if you have it, you have to live with those that don't.

irneb

  • Water Moccasin
  • Posts: 1794
  • ACad R9-2016, Revit Arch 6-2016
Re: Sorting using MergeSort
« Reply #5 on: May 23, 2012, 10:10:45 AM »
Another strange thing:
Code: [Select]
(setq unsorted nil)
(repeat 1000 (setq unsorted (cons (* (random nil) 1000.) unsorted)))
(setq sorted (vl-sort unsorted '<))
Then I get:
Code: [Select]
Benchmarking ...... done for 2048 iterations. Sorted from fastest.
Statement                                Increment  Time(ms) Normalize  Relative
--------------------------------------------------------------------------------
(VL-SORT SORTED (QUOTE <))                    2048      1949      1949     35.86
(VL-SORT UNSORTED (QUOTE <))                  1024      1623      3246     21.53
(SORT-MERGE-I SORTED (QUOTE <))                 64      1341     42912      1.63
(SORT-MERGE-R SORTED (QUOTE <))                 64      1357     43424      1.61
(SORT-MERGE-R UNSORTED (QUOTE <))               32      1076     68864      1.01
(SORT-MERGE-I UNSORTED (QUOTE <))               32      1092     69888      1.00
--------------------------------------------------------------------------------
I thought the vl-sort uses QuickSort. If so it must have some feature which tests if the list is already sorted. Because that's one of the main problems with QuickSort - if the list is already sorted it would take much longer.

Either that or vl-sort uses merge-sort itself. In that case I can much more easily understand these benchmarks.
Common sense - the curse in disguise. Because if you have it, you have to live with those that don't.

JohnK

  • Administrator
  • Seagull
  • Posts: 10657
Re: Sorting using MergeSort
« Reply #6 on: May 23, 2012, 11:02:06 AM »
On the C++ side of things (vl-sort): the STL sort function out preforms a hand-rolled quicksort routine.
TheSwamp.org (serving the CAD community since 2003)
Member location map - Add yourself

Donate to TheSwamp.org

irneb

  • Water Moccasin
  • Posts: 1794
  • ACad R9-2016, Revit Arch 6-2016
Re: Sorting using MergeSort
« Reply #7 on: May 23, 2012, 12:43:25 PM »
It then probably uses the QuickSort variant called Quick3 here: http://www.sorting-algorithms.com/

BTW, do you know if it first converts the list into an array and then sorts that? Apparently QS gets an extra boost out of memory caching when sorting an array.
Common sense - the curse in disguise. Because if you have it, you have to live with those that don't.

JohnK

  • Administrator
  • Seagull
  • Posts: 10657
Re: Sorting using MergeSort
« Reply #8 on: May 23, 2012, 01:22:36 PM »
Going way over my head quickly with those kind of questions (Sorting linked lists require "pointer surgery", sorting lists is--so I've read--theoretically more efficient than sorting arrays.). ...About all *I* know is: that stuff is a lot of templates (that would mean that "It's optimized at compilation for the data-types").
TheSwamp.org (serving the CAD community since 2003)
Member location map - Add yourself

Donate to TheSwamp.org

irneb

  • Water Moccasin
  • Posts: 1794
  • ACad R9-2016, Revit Arch 6-2016
Re: Sorting using MergeSort
« Reply #9 on: May 23, 2012, 02:03:45 PM »
It's a bit of either the one or the other. Some algorithms perform better on arrays than on lists, others do the opposite. E.g. the swap idea in quick sort means you need to get to an nth item in the list/array. Now with a linked list, that means you need to iterate n positions through the list just to get at the item you want to compare / swap. With merge sort you need not use nth indexing at all - that's why it's generally better for linked lists. Some algorithms cannot even be used on linked lists, e.g. Heap Sort.

Although you can quickly convert a linked list into an array, then sort that, then convert it back to a list. And if the list contains large items you could create a reference array (i.e. an array of pointers to the data items of the list). That way the array is much smaller, and memory operations are much smaller too (only moving pointers 4/8byte instead of multiple bytes for strings / objects). One discussion I've seen is where the conversion to and from an array does not nullify the speed increase obtained from QS and mem-cache, thus it becomes faster than doing a merge sort directly on the linked list.
Common sense - the curse in disguise. Because if you have it, you have to live with those that don't.

Lee Mac

  • Seagull
  • Posts: 12924
  • London, England
Re: Sorting using MergeSort
« Reply #10 on: May 27, 2012, 11:10:01 AM »
This thread may be of interest to you Irneb:

http://www.theswamp.org/index.php?topic=38292