Topic: Apply function to all numbers in lists within list

[irneb]

Irneb,
can u test this with ur bench-thing?

Im wondering if it makes any difference:
I picked up fnest2 and have made the recursion 'anonym'... the recursion is calling a compiled lambda-expr...

Code: [Select]

(   (lambda (fnest2 / )
      (eval (list 'defun 'anon_fnest2 '(f l / ) (list fnest2 fnest2 'f 'l)))
   )
   (lambda (fnest2 f l / )
      (cond ((atom l) ((eval f) l))
         ((cdr l) (cons (fnest2 fnest2 f (car l)) (fnest2 fnest2 f (cdr l))))
         ((cons (fnest2 fnest2 f (car l)) nil))
      )
   )
)
(anon_fnest2 '1+ '((1 2) (3 . 4) (5 6 (7 8 ((((9)) 10 11))))))

Greets Reltro

If you want you can use it yourself. It's one I derived from this one: http://www.theswamp.org/lilly_pond/mp/lisp/benchmark.txt
I changed it so it tries to never take longer than 1 sec per item to bench, because I've found many a poorly thought-out algorithm might take ages to complete a benchmark. Attached is my version.

As for your code, I'm not sure you need to do that anon_fnest2 inside of a lambda. It doesn't actually do anything different than doing the defun normally. Remember AutoLisp has a Dynamic Symbol Scoping, which means that the anon_fnest is a normal defun after the lambda is run. I'll have to check what you've actually done inside though.

As for the iterative fnest, good code! I knew something like a stack/queue would be needed for it to work. Similar to the breadth-first traversal for the tree structure.
Though it's a lot slower than the others. Test code

Code - Auto/Visual Lisp: [Select]

1. (setq lst  '((((1 "test")) (2 4) (((5.0 7))) (6) (() 8 nil 6 5 nil 3 2 1)))
2. (defun test (n) (cond ((member (type n) '(Int Real)) (1+ n)) (n)))

And the result

Code: [Select]

_$ (quickbench '((fNest 'test lst) (fNest2 'test lst) (Iter_fNest 'test lst) (map-nested 'test lst) (map-nested1 'test lst) (map-nested2 'test lst)))
Benchmarking ...... done for 8192 iterations. Sorted from fastest.
Statement                                Increment  Time(ms) Normalize  Relative
--------------------------------------------------------------------------------
(FNEST2 (QUOTE TEST) LST)                     8192      1265      1265      1.70
(FNEST (QUOTE TEST) LST)                      8192      1341      1341      1.60
(MAP-NESTED2 (QUOTE TEST) LST)                8192      1482      1482      1.45
(MAP-NESTED1 (QUOTE TEST) LST)                8192      1623      1623      1.33
(MAP-NESTED (QUOTE TEST) LST)                 8192      1716      1716      1.25
(ITER_FNEST (QUOTE TEST) LST)                 4096      1076      2152      1.00
--------------------------------------------------------------------------------It does work on nils inside the list, but not dotted pairs. So it's comparable to my first map-nested function as well as the built-in mapcar. But it's not comparable to Lee's fnest and those which were derived from it. I suppose it depends on what you want to achieve from this code:

• If you want a nested version of mapcar, then map-nested is fine (though recursive) or iter_fnest is iterative (though slower).
• If you want to have an exact structure as the input, only having each atom run through your function, then the others do come closer. Especially the fnest2. FNest does handle dotted paiirs, but ignores all nil items, the map-nested1 & 2 seem to still have issues with dotted pairs.

[irneb]

As for the anon_fnest2, it does show you've got a lot of understanding about lambda and the dynamic scope of AutoLisp. Quite tricky code on an advanced level.

Though it has no benefit over the straight forward fnest2 - actually slightly slower:

Code: [Select]

_$ (quickbench '((fNest 'test lst) (fNest2 'test lst) (anon_fNest2 'test lst)))
Benchmarking ... done for 8192 iterations. Sorted from fastest.
Statement                                Increment  Time(ms) Normalize  Relative
--------------------------------------------------------------------------------
(FNEST2 (QUOTE TEST) LST)                     8192      1294      1294      1.05
(ANON_FNEST2 (QUOTE TEST) LST)                8192      1327      1327      1.02
(FNEST (QUOTE TEST) LST)                      8192      1358      1358      1.00
--------------------------------------------------------------------------------AFAICT it's needlessly complicating the code. What was your reasoning in generating a labda function which generates your defun function to use your generated lambda function which then calls itself using a parameter passed into itself so it has a reference to itself? See how convoluted it even sounds?

And even if I use your method and generate an optimized version using the function optimization on a lambda like this:

Code - Auto/Visual Lisp: [Select]

1. ((lambda (fnest2 / ) (eval (list 'defun 'anon_fnest2a '(f l / ) (list fnest2 fnest2 'f 'l))))
2.   (eval (function (lambda (fnest2 f l / )
3.                     (cond ((atom l) ((eval f) l))
4.                           ((cdr l) (cons (fnest2 fnest2 f (car l)) (fnest2 fnest2 f (cdr l))))
5.                           ((cons (fnest2 fnest2 f (car l)) nil)))))))

It's not enough to surpass the straight-forward fnest2 defun itself:

Code: [Select]

_$ (quickbench '((fnest 'test lst) (anon_fNest2a 'test lst) (fNest2 'test lst) (anon_fNest2 'test lst)))
Benchmarking .... done for 8192 iterations. Sorted from fastest.
Statement                                Increment  Time(ms) Normalize  Relative
--------------------------------------------------------------------------------
(FNEST2 (QUOTE TEST) LST)                     8192      1294      1294      1.05
(ANON_FNEST2A (QUOTE TEST) LST)               8192      1311      1311      1.04
(FNEST (QUOTE TEST) LST)                      8192      1327      1327      1.02
(ANON_FNEST2 (QUOTE TEST) LST)                8192      1358      1358      1.00
--------------------------------------------------------------------------------It might have improved something on the reciprocal recursion of the map-nested2 if the definition was the slowing factor. But I've even tested that version using premade defuns for the runMap & doItem nested functions. It makes no difference at all

Code - Auto/Visual Lisp: [Select]

1. (defun runMap (lst) (mapcar 'doItem lst))
2. (defun doItem (item)
3.   (cond ((atom item) ((eval func) item))
4.         ((and (cdr item) (atom (cdr item))) (cons (doItem (car item)) (doItem (cdr item))))
5.         ((runMap item))))
6.  
7. (defun map-nested3 (func lst / )
8.   (runMap lst))

It's actually slower

Code: [Select]

_$ (quickbench '((map-nested2 'test lst) (map-nested3 'test lst)))
Benchmarking .. done for 8192 iterations. Sorted from fastest.
Statement                                Increment  Time(ms) Normalize  Relative
--------------------------------------------------------------------------------
(MAP-NESTED2 (QUOTE TEST) LST)                8192      1434      1434      1.11
(MAP-NESTED3 (QUOTE TEST) LST)                8192      1590      1590      1.00
--------------------------------------------------------------------------------So you see the major time taken seems to be the overhead of calling the function, not the time taken to generate the function.

[reltro]

Hey...

Here is  a complete iterative solution. handles all sort of data I tested since now
But now, its a bit slower, because each nested List hast to run trough twice.

Code: [Select]

(defun Iter_fNest (Expr Lst / Stack Result Dim)
   (while (or Lst Stack)
      (cond
         ((null Lst)
            (setq Lst (car Stack))
            (setq Stack (cdr Stack))
            (setq Result
               (cons
                  (   (lambda ( / O)
                        (repeat (caar Dim)
                           (setq O (cons (car Result) O))
                           (setq Result (cdr Result))
                        )
                        (if (cdar Dim)
                           (apply 'vl-list* O)
                           O
                        )
                     )
                  )
                  Result
               )
            )
            (setq Dim (cdr Dim))
         )
         ((atom (car Lst))
            (setq Result (cons ((eval Expr) (car Lst)) Result))
            (setq Lst (cdr Lst))
         )
         ('T
            (setq Stack (cons (cdr Lst) Stack))
            (apply
               '(lambda (L D / )
                  (setq Lst L)
                  (setq Dim (cons (cons (length Lst) D) Dim))
               )
               (   (lambda (a / lst s)
                     (setq s a)
                     (while (not (atom (cdr a)))
                        (setq lst (cons (car a) lst))
                        (setq a   (cdr a))
                     )
                     (cond
                        ((cdr a)
                           (list
                              (setq lst (reverse (vl-list* (cdr a) (car a) lst)))
                              'dP
                           )
                        )
                        ('T (list s nil))
                     )
                  )
                  (car Lst)
               )
            )
         )
      )
   )
   (reverse Result)
)


Code: [Select]

(iter_fnest '1+ '(((1 (3 . 4) 5) . 3) (1 . 20) 2 3 (1 2 (3 4) . 5) 4))
I think it was foreseeable that the iterative method is slower then the recursiv one

greets reltro

[reltro]

AFAICT it's needlessly complicating the code. What was your reasoning in generating a labda function which generates your defun function to use your generated lambda function which then calls itself using a parameter passed into itself so it has a reference to itself? See how convoluted it even sounds?

I know, its a complicated thinking, but i don't think its needless. In this special case its really needless .
I borned this idea when I tought about to build a function wich can also store some data, like an 'Object' in OOP-language.
(if u are interessted in, I can send u some code )
normally I don't name the anon-recursion with a 'defun-statment...

to build them in the Runtime I use this one:

Code: [Select]

(setq anonRec
   (   (lambda (rec / )
         (eval
            (list 'lambda '(expr / in)
               (list rec rec
                  'expr
                  '((lambda (a b / ) (if a (reverse (cdr a)) b))
                     (member '/ (reverse (cdr (cadr expr))))
                     (cdr (cadr expr))
                  )
               )
            )
         )
      )
      (eval
         (function
            (lambda (rec expr in / )
               (eval
                  (eval
                     (list 'function
                        (list 'lambda in
                           (vl-list*
                              expr
                              (list rec rec (list 'quote expr) (list 'quote in))
                              in
                           )
                        )
                     )
                  )
               )
            )
         )
      )
   )
)

Use it like this:

Code: [Select]

(  (anonRec
      '(lambda (ME a / c)
        (print a)
        (if (> a 0)
          (ME (1- a))
        )
      )
   )
   200
)

Greets reltro

@Irneb ... PS.: Thanks for the Quickbench.lsp

[irneb]

Yep, it could be a good way in some instances. But for this particular I don't think it needs to be done like that. Nothing wrong with it, I just can't see (in this case) that it brings anything better than a much simpler method.

Good one with the iterative! You're correct since for this (and other nested structures like trees & networks) it's usually simpler and quicker to use recursion. The problem with iteration in these cases is that you always need one or more temporary lists which grows and shrinks constantly as you run through different levels, this itself takes time. Then as you've found, sometimes you need to iterate over the entire structure twice if you don't want to recurse. You'll see nearly all samples of coding pertaining to trees are using some sort of recursion, there are very few iterative samples (even through google) because it's so much more complex and usually slower AND usually uses a lot more RAM.

That's not to say iterative is always like this, it's just the "nested" which causes this issue. In general recursion tends to be slower than iterative if you only run through a normal list, and could even use more ram as well. E.g. testing my own rolled foreach loop doing it through recursion and another through while:

Code - Auto/Visual Lisp: [Select]

1. (defun foreach-recursive (var lst code)
2.   (if (set var (car lst))
3.     (progn (eval code)
4.            (foreach-recursive var (cdr lst) code))))
5.  
6. (defun foreach-iterative (var lst code)
7.   (while (set var (car lst))
8.     (eval code)
9.     (setq lst (cdr lst))))

The benchmark

Code: [Select]

$ (setq test '(1 2 3 4 5 6 7 8 9))
(1 2 3 4 5 6 7 8 9)
_$ (quickbench '((foreach-recursive 'x test '(1+ x)) (foreach-iterative 'x test '(1+ x)) (foreach x test (1+ x))))
Benchmarking ... done for 16384 iterations. Sorted from fastest.
Statement                                Increment  Time(ms) Normalize  Relative
--------------------------------------------------------------------------------
(FOREACH X TEST (1+ X))                      16384      1187      1187      5.20
(FOREACH-ITERATIVE (QUOTE X) TEST (Q...)      4096      1264      5056      1.22
(FOREACH-RECURSIVE (QUOTE X) TEST (Q...)      4096      1543      6172      1.00
--------------------------------------------------------------------------------Of course using the built-in foreach is a lot quicker as it's fully compiled (probably written in C as well).

Anyhoo! You're welcome to the QuickBench. It's not perfect though, there are some others which are slightly more accurate. I just use it as the 1st benchmark to weed out the really slow code before I use one of the other benchmark routines to figure out exactly which code is fractionally faster than the other. Though more often than not I don't bother too much if there's only a 1% (or so) difference.