TheSwamp
Code Red => AutoLISP (Vanilla / Visual) => Topic started by: MP on February 15, 2005, 04:54:12 PM
-
Ok, so I'm making up new terminology.
Many years ago I had competed in a contest to write a function to flatten a nested list (no dotted pairs) to a non nested list.
Example:
(setq lst
'(1 (2 (3 (4 (5 (6 (7 (8))))))))
)
(flatten lst)
=> (1 2 3 4 5 6 7 8)
The winner in my mind (based on eloquence) was one by Doug Broad, a very pretty recursive one --
(defun flatten ( lst )
;; by Doug Broad
(cond
((null lst) nil)
((atom lst) (list lst))
((atom (car lst)) (cons (car lst) (Flatten (cdr lst))))
((append (Flatten (car lst))(Flatten (cdr lst))))
)
)
I recently had need (like yesterday) to flatten a nested list and thought I'd take a stab at writing a new one with fresh eyes. Well ... I ended up penning a funny one that is 'bicursive', that is, two functions keep calling each other until the problem is solved. While Doug's beats it when small lists are being processed, it smokes when processing larger lists (when you really need the performance) --
(defun Squish ( lst )
;; © 2005 Michael Puckett
(apply 'append
(mapcar 'SquishEx lst)
)
)
(defun SquishEx ( x / a )
;; © 2005 Michael Puckett
(if (listp x)
(if (listp (setq a (car x)))
(append (Squish a) (Squish (cdr x)))
(cons a (Squish (cdr x)))
)
(list x)
)
)
(squish lst)
=> (1 2 3 4 5 6 7 8)
Some benchmarking (http://theswamp.org/phpBB2/viewtopic.php?t=3952) --
(progn
(defun Flatten ( lst )
;; by Doug Broad
(cond
((null lst) nil)
((atom lst) (list lst))
((atom (car lst)) (cons (car lst) (Flatten (cdr lst))))
((append (Flatten (car lst))(Flatten (cdr lst))))
)
)
(defun Squish ( lst )
;; © 2005 Michael Puckett
(apply 'append
(mapcar 'SquishEx lst)
)
)
(defun SquishEx ( x / a )
;; © 2005 Michael Puckett
(if (listp x)
(if (listp (setq a (car x)))
(append (Squish a) (Squish (cdr x)))
(cons a (Squish (cdr x)))
)
(list x)
)
)
(setq big_list
(setq small_list
'(1 (2 (3 (4 (5 (6 (7 (8))))))))
)
)
(Benchmark
'( (flatten small_list)
(squish small_list)
)
)
(repeat 8
(setq big_list
(append big_list big_list)
)
)
(Benchmark
'( (flatten big_list)
(squish big_list)
)
)
)
Results --
Milliseconds / relative speed for 16384 iteration(s):
(FLATTEN SMALL_LIST).....1750 / 1.36 <fastest>
(SQUISH SMALL_LIST)......2375 / 1.00 <slowest>
Milliseconds / relative speed for 64 iteration(s):
(SQUISH BIG_LIST).......1672 / 7.05 <fastest> YEOW!
(FLATTEN BIG_LIST).....11781 / 1.00 <slowest>
Questions --
(1) Do you see any potential problems or flaws in my logic?
(2) Can you write one that has a flatter performance, i.e. performs equally well at both ends of the spectrum (small versus large lists)?
Thanks guys.
I found one problem, any nil values in the original list are removed; they should be retained.
-
(1) Do you see any potential problems or flaws in my logic?
(2) Can you write one that has a flatter performance, i.e. performs equally well at both ends of the spectrum (small versus large lists)?
1) Can I get back to ya on this, once I figure out your logic. <g>
2) Not likely but that's never stopped me before.
MP, that's some beautiful code man.
-
Thank you Mark. :)
I found a problem -- squish removes nils from the original list, and it really shouldn't. Doug's flatten does not.
i.e.
(flatten '(1 nil (2 nil (3 nil))))
=> (1 nil 2 nil 3 nil)
(squish '(1 nil (2 nil (3 nil))))
=> (1 2 3)
Recoded --
(defun Squish ( lst )
;; © 2005 Michael Puckett
(apply 'append
(mapcar 'SquishEx lst)
)
)
(defun SquishEx ( x / a )
;; © 2005 Michael Puckett
(if x
(if (listp x)
(if (listp (setq a (car x)))
(append (Squish a) (Squish (cdr x)))
(cons a (Squish (cdr x)))
)
(list x)
)
'(nil)
)
)
(squish '(1 nil (2 nil (3 nil))))
=> (1 nil 2 nil 3 nil)
Nested if statements benched better than an equivalent cond structure; hmmm.
It still benches very well against flatten despite the additional if test (same data) as initial benching:
Milliseconds / relative speed for 64 iteration(s):
(SQUISH BIG_LST).......1656 / 6.98 <fastest>
(FLATTEN BIG_LST).....11563 / 1.00 <slowest>
:)
-
Very interesting!
(progn
(defun Flatten ( lst )
;; by Doug Broad
(cond
((null lst) nil)
((atom lst) (list lst))
((atom (car lst)) (cons (car lst) (Flatten (cdr lst))))
((append (Flatten (car lst))(Flatten (cdr lst))))
)
)
(defun Squish ( lst )
;; © 2005 Michael Puckett
(apply 'append
(mapcar 'SquishEx lst)
)
)
(defun SquishEx ( x / a )
;; © 2005 Michael Puckett
(if x
(if (listp x)
(if (listp (setq a (car x)))
(append (Squish a) (Squish (cdr x)))
(cons a (Squish (cdr x)))
)
(list x)
)
'(nil)
)
)
(setq lst
'(1 (2 (3 (4 (5 (6 (7 (8))))))))
)
(while t
(princ
(strcat
"\nFlattened length = "
(itoa (length (squish lst)))
"\n"
)
)
(Benchmark
'( (flatten lst)
(squish lst)
)
)
(setq lst (append lst lst))
)
(princ)
)
Results --
Flattened length = 8, 16384 iteration(s): Flatten performing better
(FLATTEN LST).....1656 / 1.35 <fastest>
(SQUISH LST)......2234 / 1.00 <slowest>
Flattened length = 16, 8192 iteration(s):
(FLATTEN LST).....1344 / 1.37 <fastest>
(SQUISH LST)......1843 / 1.00 <slowest>
Flattened length = 32, 4096 iteration(s):
(FLATTEN LST).....1265 / 1.31 <fastest>
(SQUISH LST)......1656 / 1.00 <slowest>
Flattened length = 64, 2048 iteration(s):
(FLATTEN LST).....1360 / 1.17 <fastest>
(SQUISH LST)......1594 / 1.00 <slowest>
Flattened length = 128, 1024 iteration(s): Squish performing better
(SQUISH LST)......1547 / 1.03 <fastest>
(FLATTEN LST).....1594 / 1.00 <slowest>
Flattened length = 256, 512 iteration(s):
(SQUISH LST)......1562 / 1.35 <fastest>
(FLATTEN LST).....2109 / 1.00 <slowest>
Flattened length = 512, 256 iteration(s):
(SQUISH LST)......1531 / 2.09 <fastest>
(FLATTEN LST).....3203 / 1.00 <slowest>
Flattened length = 1024, 128 iteration(s):
(SQUISH LST)......1562 / 3.51 <fastest>
(FLATTEN LST).....5484 / 1.00 <slowest>
Flattened length = 2048, 64 iteration(s):
(SQUISH LST).......1562 / 6.64 <fastest>
(FLATTEN LST).....10375 / 1.00 <slowest>
Flattened length = 4096, 32 iteration(s):
(SQUISH LST).......1578 / 12.68 <fastest>
(FLATTEN LST).....20016 / 1.00 <slowest>
Flattened length = 8192, 16 iteration(s):
(SQUISH LST).......1438 / 23.54 <fastest>
(FLATTEN LST).....33844 / 1.00 <slowest>
Flattened length = 16384, 8 iteration(s):
(SQUISH LST).......1312 / 38.73 <fastest>
(FLATTEN LST).....50813 / 1.00 <slowest>
Flattened length = 32768, 4 iteration(s):
(SQUISH LST).......1265 / 72.90 <fastest>
(FLATTEN LST).....92218 / 1.00 <slowest>
Flattened length = 65536, 2 iteration(s):
(SQUISH LST)........1187 / 104.07 <fastest>
(FLATTEN LST).....123532 / 1.00 <slowest>
Flattened list length = 131072
*KAFREAKINBOOM*, Hard error occurred ***
Flatten crashed when the list had grown to 131072 items (when denested) because it blew up the stack. Squish still crushed the big 'ol list down, in 1250 milliseconds (1 iteration), very reasonable! :)
Nonetheless, flatten remains an eloquent example of recursion and Doug Broad an excellent codesmith (a very nice gentlemen too I might add).
-
*blink* *blink* What dahell 'r ya doin'?! I cant find that logic anywhere in my book! ...'Bicurson' Pthhht!?
Let me see this stuff.
***
Oh my head hurts. I keep getting lost. ...Im just gonna nod and go over there now. Okay?
-
Final thought (I think).
Nesting the two defuns inside a wrapper defun realizes a very small performance hit for the convenience (in benchmark terms, the non nested version averages 1.02 times faster, wow). In the big picture that kind of performance difference is inconsequetial (especially considering the dramatic results above).
Anyway, this is what is going into my library:
(defun flatten ( lst / f1 f2 )
;; © 2005 Michael Puckett
(defun f1 ( lst )
(apply 'append
(mapcar 'f2 lst)
)
)
(defun f2 ( x / a )
(if x
(if (listp x)
(if (listp (setq a (car x)))
(append (f1 a) (f1 (cdr x)))
(cons a (f1 (cdr x)))
)
(list x)
)
'(nil)
)
)
(f1 lst)
)
Not as pretty as Doug's but sometimes ugly has to finish the job. :)
-
I know this isn't a challenge and I hope you don't mind but, this is what I came up with. Mind you it doesn't handle the nil's like your does.
(setq lst
'(1 (2 (3 (4 (5 (6 (7 (8))))))))
)
(defun level (lst / leveled)
(while (> (length lst) 0)
(setq leveled (cons (car lst) leveled))
(setq lst (car (vl-remove (car lst) lst)))
)
(if leveled (reverse leveled))
)
(setq leveled_list (level lst))
--> (1 2 3 4 5 6 7 8)
-
Actually, I though I invited better performing, alternate algorithms. Didn't I? Regardless, they're welcome. This is the swamp isn't it? :)
Having said that, observe:
(setq lst
'(1 nil (2 nil (3 nil (4 nil (5 nil
(6 nil (7 nil (8 nil)))))))
)
)
(level lst)
=> (1)
(squish lst)
=> (1 nil 2 nil 3 nil 4 nil 5 nil 6 nil 7 nil 8 nil)
Don't abandon it though, it has promise. I'd rework it for you but I know you like figuring these things out as much as I do, so I'll keep me mitts off. :)
Thanks Mark.
-
I like to know how this preforms compared to yours MP but i'm not sure how to go about it.
-
Once it works correctly you can compare performance using this (http://www.theswamp.org/lilly_pond/mp/lisp/benchmark.txt?nossi=1).
-
MP, nice work. Bicursion? Cool, new word :)
I'm a little amazed that it doesn't bust the stack before Doug's FLATTEN routine does. Running a trace stack on both (with the list you showed in first post), yours go down 23 levels before hitting (f1 nil), while Doug's only runs 16 levels before hitting (flatten nil) and starting to rewind.
But I guess it's only recursive as long as there are atoms on each level (which means 1 recursion each on this particular list), so it will never run as deep as Doug's function will for each call.
Mark, try dotting the list manually and see what it returns:
(setq lst '(1 . (2 . (3 . (4 . (5 . (6 . (7 . (8)))))))))
=> (1 2 3 4 5 6 7 8)
That's basically what your routine does. It can be shortened into this little recursion:
(defun consem (lst)
(if (vl-consp lst) (cons (car lst) (consem (cadr lst))))
)
It's depending on CAR element always being an atom and CADR element always being a list.
-
This is a very cool subject. (Ive thought about this last night and "wow"!) Its a tough thing to get your head arround. (Recursivly that is.)
-
(defun consem (lst)
(if (vl-consp lst) (cons (car lst) (consem (cadr lst))))
)
Stig, it's absolutely beautiful, but she no worky on the nested lists per my first post.
:(
-
(Dang, off to work, see ya in a couple hours).
-
Stig, it's absolutely beautiful, but she no worky on the nested lists per my first post.
:(
It wasn't supposed to. Only supposed to explain why Mark's routine can't handle multiple atoms on same level. That's why Doug's routine had to implement multiple conditions.
Nevermind it can only handle one kind of list though, did you try to benchmark it? It's pretty fast :D
-
It wasn't supposed to. Only supposed to explain why Mark's routine can't handle multiple atoms on same level. That's why Doug's routine had to implement multiple conditions.
Ackkk: Too little sleep, too much coffee. Sorry?
Nevermind it can only handle one kind of list though, did you try to benchmark it? It's pretty fast :D
:lol:
-
Well I finally got mine to work.
It aint pretty but.
(defun delist (lst / 1-list a)
(while lst
(if (listp lst)
(if (and (listp (setq a (car lst))) a)
(setq 1-list (append (delist a) 1-list))
(setq 1-list (cons a 1-list))
)
(setq 1-list (cons lst 1-list))
)
(setq lst (cond ((listp lst)(cdr lst))))
)
1-list
)
Flattened length = 8
Benchmarking ................Elapsed milliseconds / relative speed for 8192 iteration(s):
(DELIST LST)......1272 / 2.21 <fastest>
(SQUISH LST)......1662 / 1.69
(FLATTEN LST).....2814 / 1.00 <slowest>
Flattened length = 16
Benchmarking ................Elapsed milliseconds / relative speed for 8192 iteration(s):
(DELIST LST)......1792 / 1.40 <fastest>
(FLATTEN LST).....1893 / 1.33
(SQUISH LST)......2513 / 1.00 <slowest>
Flattened length = 32
Benchmarking ...............Elapsed milliseconds / relative speed for 4096 iteration(s):
(DELIST LST)......1482 / 1.42 <fastest>
(FLATTEN LST).....1563 / 1.35
(SQUISH LST)......2103 / 1.00 <slowest>
Flattened length = 64
Benchmarking ..............Elapsed milliseconds / relative speed for 2048 iteration(s):
(DELIST LST)......1392 / 1.40 <fastest>
(FLATTEN LST).....1502 / 1.29
(SQUISH LST)......1942 / 1.00 <slowest>
Flattened length = 128
Benchmarking .............Elapsed milliseconds / relative speed for 1024 iteration(s):
(DELIST LST)......1502 / 1.25 <fastest>
(FLATTEN LST).....1582 / 1.18
(SQUISH LST)......1873 / 1.00 <slowest>
Flattened length = 256
Benchmarking ............Elapsed milliseconds / relative speed for 512 iteration(s):
(DELIST LST)......1772 / 1.05 <fastest>
(SQUISH LST)......1853 / 1.01
(FLATTEN LST).....1863 / 1.00 <slowest>
Flattened length = 512
Benchmarking ...........Elapsed milliseconds / relative speed for 256 iteration(s):
(SQUISH LST)......1833 / 1.33 <fastest> <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
(DELIST LST)......2354 / 1.03
(FLATTEN LST).....2433 / 1.00 <slowest>
Flattened length = 1024
Benchmarking ..........Elapsed milliseconds / relative speed for 128 iteration(s):
(SQUISH LST)......1833 / 1.99 <fastest>
(DELIST LST)......3535 / 1.03
(FLATTEN LST).....3645 / 1.00 <slowest>
Flattened length = 2048
Benchmarking .........Elapsed milliseconds / relative speed for 64 iteration(s):
(SQUISH LST)......1833 / 3.29 <fastest>
(DELIST LST)......5898 / 1.02
(FLATTEN LST).....6039 / 1.00 <slowest>
-
MP,
What happens when you use this list for your test?
(setq lst '((1 . 2) (1 nil 3) ((11 12) (21 22) 4)))
-
:lol: :lol:
KABOOM!
:lol: :lol:
-
Hi Charles,
It is not intended for dotted pairs. From my initial post:
Many years ago I had competed in a contest to write a function to flatten a nested list (no dotted pairs) to a non nested list.
But thank you for the heads up; greatly appreciated.
:D
-
Hi Charles,
It is not intended for dotted pairs. From my initial post:
Many years ago I had competed in a contest to write a function to flatten a nested list (no dotted pairs) to a non nested list.
But thank you for the heads up; greatly appreciated.
:D
MP,
You're quite right, I'm sure I read that yesterday but that was yesterday. :)
Sorry about that.
-
No worries Charles, it's all propellers here!
(http://www.theswamp.org/screens/mp/prophead.png)
-
Hey Charles, did you view the results from your DeList? Hint, hint. :)
-
Hey Charles, did you view the results from your DeList? Hint, hint. :)
Are you talking about the fact the return list is reversed?
I had to modify the code as follows to fix that.
Do you have a better solution?
(setq lst1 '((1 . 2) (1 nil 3) ((11 12) (21 22) 4)))
(setq lst2 '(1 (2 (3 (4 (5 (nil (7 (8)))))))))
(setq lst3 '((((((((1) 2) 3) 4) 5) 6) 7) 8))
(defun delist (lst / delst)
(defun delst (lst / 1-list a)
(while lst
(if (and (listp lst) (listp (setq a (car lst))) a)
(setq 1-list (append (delst a) 1-list))
(setq 1-list (cons (cond ((listp lst) a)(lst))1-list))
)
(setq lst (cond ((listp lst) (cdr lst))))
)
1-list
)
(reverse (delst lst))
)
(princ (delist lst1))
(print)
(princ (delist lst2))
(print)
(princ (delist lst3))
Result
(1 2 1 nil 3 11 12 21 22 4)
(1 2 3 4 5 nil 7 8)
(1 2 3 4 5 6 7 8)
And the fix killed my advantage. :(
Flattened length = 8
Benchmarking ................Elapsed milliseconds / relative speed for 8192 iteration(s):
(DELIST LST)......1532 / 1.23 <fastest>
(FLATTEN LST).....1533 / 1.23
(SQUISH LST)......1882 / 1.00 <slowest>
Flattened length = 16
Benchmarking ...............Elapsed milliseconds / relative speed for 4096 iteration(s):
(DELIST LST)......1001 / 1.31 <fastest>
(FLATTEN LST).....1021 / 1.28
(SQUISH LST)......1311 / 1.00 <slowest>
Flattened length = 32
Benchmarking ...............Elapsed milliseconds / relative speed for 4096 iteration(s):
(FLATTEN LST).....1753 / 1.30 <fastest>
(DELIST LST)......1783 / 1.28
(SQUISH LST)......2283 / 1.00 <slowest>
Flattened length = 64
Benchmarking ..............Elapsed milliseconds / relative speed for 2048 iteration(s):
(DELIST LST)......1752 / 1.24 <fastest>
(FLATTEN LST).....1772 / 1.23
(SQUISH LST)......2174 / 1.00 <slowest>
Flattened length = 128
Benchmarking .............Elapsed milliseconds / relative speed for 1024 iteration(s):
(FLATTEN LST).....1963 / 1.06 <fastest>
(DELIST LST)......1983 / 1.05
(SQUISH LST)......2083 / 1.00 <slowest>
Flattened length = 256
Benchmarking ...........Elapsed milliseconds / relative speed for 256 iteration(s):
(SQUISH LST)......1002 / 1.20 <fastest>
(FLATTEN LST).....1191 / 1.01
(DELIST LST)......1202 / 1.00 <slowest>
PS Cool propellers 8)
-
Hi Charles --
I'm not seeing the rationale for the nested defun delst (which is not local incidentally). It's performing the same thing the body of delist could. I'd just reverse 1-list when you're done.
Note, it's tempting to think, hmmm, the raw list has fewer members than the processed list, it should take less time to reverse.
However, it will yeild wonky results:
(reverse '(1(2(3(4(5(6(7(8)))))))))
=> ((2 (3 (4 (5 (6 (7 (8))))))) 1)
Flattening that would produce:
=> (2 3 4 5 6 7 8 1)
Reversing:
=> (1 8 7 6 5 4 3 2)
Not quite right!
:D
-
You're confunen me. Easy to do I know.
I edited my previous post.
> localized the function
> added the raw list to compare with the results.
The delist call to delst just reverses the return value from delst.
It does not send a reversed raw list. As you say that would produce incorrect results.
-
Sorry Charles, was getting ready for work when I hastilly made that post. The point I was trying to make is this ...
(defun foo1 ( lst / result )
(foreach x lst
(if SomeConditionMet
(setq result
(cons x result)
)
)
)
(reverse result)
)
(defun foo2 ( lst / result )
(foreach x (reverse lst)
(if SomeConditionMet
(setq result
(cons x result)
)
)
)
result
)
In foo1 the order of the elements in variable result is reversed from the original, hense you have to reverse its contents when returning it to the caller.
In foo2 the order of the elements in variable result is the same as the original, hense no need to reverse it when returning it to the caller.
Speaking generally, When dealing with flat lists (the norm), foo1 is preferable when the result has fewer elements than the original (the norm); foo2 prefereable when the result has more elements than the original.
However, reversing a nested list, processing it and then returning the result may not yield the desired result! </point>
But I'm not saying that's what you did, recall "Note, it's tempting to think ..."
Cheers.
:D
-
A traffic cop here .. (http://www.theswamp.org/forum/index.php?topic=7496.msg94337#msg94337).
pointed me to this thread.
Way cool.
-
cheater way to flatten a list.... :ugly:
(defun buldge (alist)
(setq alist (vl-princ-to-string alist))
(while (vl-string-search "(" (setq alist (vl-string-subst "" "(" alist))))
(while (vl-string-search ")" (setq alist (vl-string-subst "" ")" alist))))
(read (strcat "(" alist ")"))
)
-
Try that on this !!
(setq lst2 '(1 (2 (3 (4 (5 "ABC" "DE FG"(nil (7 (8 )))))))))
Then back to the drawing board ..
-
I already knew it was broken... ("("(5 4 3 ) nil ")") is a real good time.
it was just humorous
-
I already knew it was broken... ("("(5 4 3 ) nil ")") is a real good time.
it was just humorous
FLAME ON:
That type of post, particularly a supposed code solution, is not worth the bandwidth it takes to send it.
It's illogical and poorly reasoned. The rest of the world agrees with me.
FLAME OFF:
-
FLAME ON:
now where'd i put that fire extiguisher.... :roll:
-
Asked wants can let the result with what method equate to this ?
(setq lst '("A" ("B1" "B2" "B3" "B4" "B5") "C" "D" "E"))
=> (("A")
(nil "B1")
(nil "B2")
(nil "B3")
(nil "B4")
("C")
("D")
("E")
)
(setq lst '(10 (20.1 20.2 20.3 20.4 20.5) 30 40 50))
=> ((10)
(nil 20.1)
(nil 20.2)
(nil 20.3)
(nil 20.4)
(30)
(40)
(50)
)
(setq lst '(10 (20 21 (22.1 22.2 (22.30 22.31 22.32) 22.4) 23 24) 30 (40 41 42) 50))
=> ((10)
(nil 20)
(nil 21)
(nil nil 22.1)
(nil nil 22.2)
(nil nil nil 22.3)
(nil nil nil 22.31)
(nil nil nil 22.32)
(nil nil 22.4)
(nil 23)
(nil 24)
(30)
(nil 40)
(nil 41)
(nil 42)
(50)
)
-
I'm not sure what you're asking, but if you use the final function I
penned from this discussion and use it to process the three samples
you provided --
( (lambda ( / flatten )
(defun flatten ( lst / f1 f2 )
(defun f1 ( lst )
(apply 'append
(mapcar 'f2 lst)
)
)
(defun f2 ( x / a )
(if x
(if (listp x)
(if (listp (setq a (car x)))
(append (f1 a) (f1 (cdr x)))
(cons a (f1 (cdr x)))
)
(list x)
)
'(nil)
)
)
(f1 lst)
)
(mapcar 'print
(mapcar 'flatten
'(
("A" ("B1" "B2" "B3" "B4" "B5") "C" "D" "E")
(10 (20.1 20.2 20.3 20.4 20.5) 30 40 50)
(10 (20 21 (22.1 22.2 (22.30 22.31 22.32) 22.4) 23 24) 30 (40 41 42) 50)
)
)
)
(princ)
)
)
It outputs this --
("A" "B1" "B2" "B3" "B4" "B5" "C" "D" "E")
(10 20.1 20.2 20.3 20.4 20.5 30 40 50)
(10 20 21 22.1 22.2 22.3 22.31 22.32 22.4 23 24 30 40 41 42 50)
Which in my mind faithfully honors the original intent of the function.
Hope that helps / clarifies.
Cheers and welcome to the swamp.
-
Thank you the suggestion
-
You're very welcome.