Topic: Place your bets (process evaluation time)

[JohnK]

The recent ``remove nth'' thread has spawn some thoughts and I decided to share some of my more interesting notes. But before I reveal the results, please tell me which one will out preform the others and why you think so.

My predictions are (well ``were'') on the version two but with version one in a very tight second.
Why: because I thought the defined named abstractions would be faster then actual computations.

Code: [Select]

;;;
;;;  --- Set up procedures ---
;;;

(defun fib-up-to--ver1 ( nu / fib-lst fib-nu )
  ;; (fib-up-to--ver1 1836311903)
  ;; =>
  ;; (1836311903 1134903170 701408733 433494437 267914296 165580141 102334155
  ;; 63245986 39088169 24157817 14930352 9227465 5702887 3524578 2178309 1346269
  ;; 832040 514229 317811 196418 121393 75025 46368 28657 17711 10946 6765 4181 2584
  ;; 1597 987 610 377 233 144 89 55 34 21 13 8 5 3 2 1 1 0)
  ;;
  ;; this proced uses an iterative process
  (setq fib-nu 1
        fib-lst '(0))
  (while (< (car fib-lst) nu)
         (setq
           fib-lst (cons (+ (car fib-lst) fib-nu) fib-lst)
           fib-nu (cadr fib-lst)))
  fib-lst
 )


(defun fib-up-to--ver2 ( nu / fib-lst fib-nu )
  ;; (fib-up-to--ver2 1836311903)
  ;; =>
  ;; (1836311903 1134903170 701408733 433494437 267914296 165580141 102334155
  ;; 63245986 39088169 24157817 14930352 9227465 5702887 3524578 2178309 1346269
  ;; 832040 514229 317811 196418 121393 75025 46368 28657 17711 10946 6765 4181 2584
  ;; 1597 987 610 377 233 144 89 55 34 21 13 8 5 3 2 1 1 0)
  ;;
  ;; this proced uses an iterative process with names
  (defun plus ( n1 n2 ) (+ n1 n2))
 
  (defun pair ( item lst )
    (cons item (eval lst)))

  (setq fib-nu 1
        fib-lst '(0))
  (while (< (car fib-lst) nu)
         (setq
           fib-lst (pair (plus (car fib-lst) fib-nu) 'fib-lst)
           fib-nu (cadr fib-lst)))
  fib-lst
 )


(defun fib-up-to--ver3 ( nu / fib-lst fib-nu )
  ;; (fib-up-to--ver3 1836311903)
  ;; =>
  ;; (1836311903 1134903170 701408733 433494437 267914296 165580141 102334155
  ;; 63245986 39088169 24157817 14930352 9227465 5702887 3524578 2178309 1346269
  ;; 832040 514229 317811 196418 121393 75025 46368 28657 17711 10946 6765 4181 2584
  ;; 1597 987 610 377 233 144 89 55 34 21 13 8 5 3 2 1 1 0)
  ;;
  ;; this proced uses an iterative process with names and some lex scope
  (defun add-em ( )
    (+ (car fib-lst) fib-nu))
 
  (defun pair-em ( item )
    (cons item fib-lst))

  (setq fib-nu 1
        fib-lst '(0))
  (while (< (car fib-lst) nu)
         (setq
           fib-lst (pair-em (add-em))
           fib-nu (cadr fib-lst)))
  fib-lst
 )

(defun fib-up-to--ver4 ( nu / calc-fib-lst )
  ;; (fib-up-to--ver4 1836311903)
  ;; =>
  ;; (1836311903 1134903170 701408733 433494437 267914296 165580141 102334155
  ;; 63245986 39088169 24157817 14930352 9227465 5702887 3524578 2178309 1346269
  ;; 832040 514229 317811 196418 121393 75025 46368 28657 17711 10946 6765 4181 2584
  ;; 1597 987 610 377 233 144 89 55 34 21 13 8 5 3 2 1 1 0)
  ;;
  ;; this proced uses a liner recursive process

  (defun calc-fib-lst ( nu lst )
    (if (>= (car lst) nu)
      lst
      (progn
        (setq lst (cons (+ (car lst) (cadr lst)) lst))
        (calc-fib-lst nu lst))) )
 
  (calc-fib-lst nu '(1 0))
 )
BTW, No cheating! There are not any ``wrong'' thoughts.

[CAB]

John,

I have not done any testing but make my assumptions based on past observations & my poor memory of those observations.

I think WHILE is faster than mapcar, foreach, or repeat.
I think the overhead of a recursive function makes it slower in general.
I think the overhead of calling a function also is slower than making the operation local within a function. It may take more code but I thought it would be faster.

So my vote is for version 1 to be the fastest.

[It's Alive!]

My vote is is for #1

Dan

[Kerry]

My guess is :
fastest 1
slowest 2 <by lots>

and a penny each way for second on the other 2.

[ElpanovEvgeniy]

I did not check speed, but I think, a favorite recursive process...
Now in Moscow late, in the morning I shall write other recursion...

[ElpanovEvgeniy]

I did not check speed, but I think, a favorite recursive process...
Now in Moscow late, in the morning I shall write other recursion...

Code: [Select]

(defun fib-up-to--ver5 (nu / cfl)
  (defun cfl (nu b c)
    (if (< c nu)
      (cons b (cfl nu c (+ b c)))
      (list b nu)
    ) ;_ if
  ) ;_ defun
  (reverse (cfl nu 0 1))
) ;_ defun

Test speed

Code: [Select]

(BenchMark '(
             (fib-up-to--ver1 1836311903)
             (fib-up-to--ver2 1836311903)
             (fib-up-to--ver3 1836311903)
             (fib-up-to--ver4 1836311903)
             (fib-up-to--ver5 1836311903)
            )
) ;_ BenchMark
_$
Benchmarking ................Elapsed milliseconds / relative speed for 8192 iteration(s):

    (FIB-UP-TO--VER5 1836311903).....1046 / 4.9 <fastest>
    (FIB-UP-TO--VER1 1836311903).....1422 / 3.6
    (FIB-UP-TO--VER4 1836311903).....1547 / 3.31
    (FIB-UP-TO--VER3 1836311903).....1750 / 2.93
    (FIB-UP-TO--VER2 1836311903).....5125 / 1 <slowest>


[ElpanovEvgeniy]

I cannot write function...
More quickly (fib-up-to--ver5 1836311903)  but without recursion...

[ElpanovEvgeniy]

Test speed, after compilation...

Code: [Select]

_$
Benchmarking .................Elapsed milliseconds / relative speed for 16384 iteration(s):

    (FIB-UP-TO--VER5 1836311903).....1766 / 5.18 <fastest>
    (FIB-UP-TO--VER1 1836311903).....1937 / 4.73
    (FIB-UP-TO--VER4 1836311903).....2312 / 3.96
    (FIB-UP-TO--VER3 1836311903).....2406 / 3.81
    (FIB-UP-TO--VER2 1836311903).....9156 / 1 <slowest>



[CAB]

I assume you tried this variation. I am supprised it was slower than recursion.

Code: [Select]

(defun fib-up-to--ver6 (nu / b c d cfl)
  (setq b 1 c 0)
  (while (<= c nu)
    (setq cfl (cons c cfl)
          d   c
          c   (+ b c)
          b   d))
  cfl
)

[ElpanovEvgeniy]

I assume you tried this variation. I am supprised it was slower than recursion.

Code: [Select]

(defun fib-up-to--ver6 (nu / b c d cfl)
  (setq b 1 c 0)
  (while (<= c nu)
    (setq cfl (cons c cfl)
          d   c
          c   (+ b c)
          b   d))
  cfl
)

fo not compilation:

Code: [Select]

_$
Benchmarking ................Elapsed milliseconds / relative speed for 8192 iteration(s):

    (FIB-UP-TO--VER5 1836311903).....1063 / 4.97 <fastest>
    (FIB-UP-TO--VER6 1836311903).....1188 / 4.45
    (FIB-UP-TO--VER1 1836311903).....1422 / 3.71
    (FIB-UP-TO--VER4 1836311903).....1579 / 3.35
    (FIB-UP-TO--VER3 1836311903).....1781 / 2.97
    (FIB-UP-TO--VER2 1836311903).....5282 / 1 <slowest>


[CAB]

Thanks Evgeniy, you learn something every day here. 

So it's not the recursion that requires time, it's how you use it.



Gotta run... see you later.

[ElpanovEvgeniy]

Thanks Evgeniy, you learn something every day here. 

So it's not the recursion that requires time, it's how you use it.



Gotta run... see you later.

Your code worked incorrectly... 
I have repaired it.

Code: [Select]

(defun fib-up-to--ver6_1 (nu / b c d cfl)
  (setq b 0 c 1)
  (while (< c nu)
    (setq cfl (cons b cfl)
          d   c
          c   b
          b   (+ c d)
    ) ;_ setq
  ) ;_ while
  cfl
) ;_ defun

[ElpanovEvgeniy]

Thanks Alan!

Test speed, after compilation...

Code: [Select]

_$
Benchmarking .................Elapsed milliseconds / relative speed for 16384 iteration(s):

    (FIB-UP-TO--VER6_1 1836311903).....1563 / 5.69 <fastest>
    (FIB-UP-TO--VER5 1836311903).......1718 / 5.18
    (FIB-UP-TO--VER1 1836311903).......1906 / 4.66
    (FIB-UP-TO--VER4 1836311903).......2281 / 3.9
    (FIB-UP-TO--VER3 1836311903).......2375 / 3.74
    (FIB-UP-TO--VER2 1836311903).......8891 / 1 <slowest>


[Joe Burke]

John,

I have not done any testing but make my assumptions based on past observations & my poor memory of those observations.

I think WHILE is faster than mapcar, foreach, or repeat.
I think the overhead of a recursive function makes it slower in general.
I think the overhead of calling a function also is slower than making the operation local within a function. It may take more code but I thought it would be faster.

So my vote is for version 1 to be the fastest.

Seems to me this idea "I think WHILE is faster than mapcar, foreach, or repeat" is comparing apples to oranges without qualification. While is faster when it lets the loop end based on the argument passed.

It is not faster than repeat for instance, given the number of iterations are known. Because while has to evaluate the argument passed on each iteration. Not so with repeat.

[CAB]

Hey Joe,
Not sure if you consider this an un biased test.

Code: [Select]

(defun c:test ()
  (BenchMark
    '((apples)
      (oranges)
     )
  )
)


(defun apples (/ ss i ename result)
  (setq ss (ssget "X"))
  (setq i -1)
  (while (setq ename (ssname ss (setq i (1+ i))))
    (setq result (cons ename result))
  )
)

(defun oranges (/ ss i ename result)
  (setq ss (ssget "X"))
  (setq i -1)
  (repeat (sslength ss)
    (setq ename (ssname ss (setq i (1+ i))))
    (setq result (cons ename result))
  )
)
But here are my results:

Code: [Select]

Command: test
Elapsed milliseconds / relative speed for 256 iteration(s):

    (APPLES)......1863 / 1.17 <fastest>
    (ORANGES).....2183 / 1.00 <slowest>