Topic: Reverse Benchmark

[irneb]

In the greater scheme of things reverse is probably not a great time waster. But I was wondering just how "bad" it really is. So I compared it with just passing the list as is:

Code: [Select]

Benchmarking ...... done for 524288 iterations. Sorted from fastest.
Statement                                Increment  Time(ms) Normalize  Relative
--------------------------------------------------------------------------------
LST1000                                     524288      1249      1249  19440.42
LST1M                                       524288      1263      1263  19224.93
LST5000                                     524288      1280      1280  18969.60
(REVERSE LST1000)                            16384      1437     45984    528.03
(REVERSE LST5000)                             8192      1966    125824    192.98
(REVERSE LST1M)                                 32      1482  24281088      1.00
--------------------------------------------------------------------------------LST1000 is a list containing 1000 integers, LST5000 contains 5000 and LST1M contains 1,000,000 integers.

Clearly reverse is a LOT slower than simply passing the list as is. Thus it must be modifying the result in some way. Though what is strange is it's not directly proportional to the length of the list. E.g. if it was directly proportional then the time to reverse 1000 items should have been around 1000 times faster than the same time to reverse 1000000 items (instead of as shown around 530 times faster).

From this I gather it's better to reverse a long list at the end of calculations than reversing numerous short lists in the middle.

So anyone have an idea about what reverse actually does? So we can say for sure?

[Lee Mac]

Maybe it uses a divide & conquer approach, e.g.

Code - Auto/Visual Lisp: [Select]

1. (defun _reverse ( l / n )
2.     (if (< 1 (setq n (length l)))
3.         (append
4.             (_reverse (_sublist l (/ n 2) (1- n)))
5.             (_reverse (_sublist l 0 (1- (/ n 2))))
6.         )
7.         l
8.     )
9. )
10.  
11. (defun _sublist ( l m n / r )
12.     (repeat (1+ (- n m))
13.         (setq r (cons (nth n l) r)
14.               n (1- n)
15.         )
16.     )
17.     r
18. )

/guess