(dolist) enhancement

[Lutz]

I have been looking into an enhanced (dolist ((x y ... ) L) ...) and actually started coding something, the speed performance impact though seems to big. I also think, that in most cases where a need for a multiparameter 'dolist' is perceived it would be better to structure the iteration list and do something like this:

Code Select Expand


(dolist (p '((a 1) (b 2) (c 3)))
    ... (p 0) ...   ; access the first member of the p sublist
    ... (p 1) ...   ; access the second member of the p sublist
)


Nested lists are good for structuring information and should be used in this way. Then use implicit indexing to access sub members.



But still, after having made this argument I agree, a multi parameter 'dolist' is a good idea and there are cases where it comes in very handy. I may give it another shot.



Lutz

[Fanda]

Nigel: Silly me - I used 2 different functions and compared the speed ;-)



I tried it and it seems more complicated. For simple lists:

>  (setq L '((1 2) (3 4) (5 6)))

((1 2) (3 4) (5 6))



# dolist faster

> (time (dotimes (i 100000) (map (lambda (x) (x 0)) L)))

203

> (time (dotimes (i 100000) (setq r '())(dolist (x L)(push (x 0) r -1))))

125



# map faster

> (time (dotimes (i 100000) (map first L)))

78

> (time (dotimes (i 100000) (setq r '())(dolist (x L) (push (first x) r -1))))

125



I guess - if you have lambda inside the map - you get slow down.



I tried nested lists:

> (setq M '(((1 2) (3 4)) ((5 6) (7 8))))

(((1 2) (3 4)) ((5 6) (7 8)))

> (map (lambda (x) (map first x)) M)

((1 3) (5 7))



> (setq r '())(dolist (x M) (dolist (y x) (push (first y) r -1)))

()7

> r

(1 3 5 7)



You don't get the same results, but algorithm is pretty much the same.



> (time (dotimes (i 100000) (map (lambda (x) (map first x)) M)))

313

> (time (dotimes (i 100000) (setq r '())(dolist (x M) (dolist (y x) (push (first y) r -1)))))

266



So, I would say:

- map is pretty fast for simple functions

- dolist is good for complicated functions and nested lists  (try to nest it 3x, 4x times)





Lutz: If it would mean slow down for current 'dolist', I guess you might give it another name...



My idea of algorithm was to fill in empty lists at the end and then just iterate  through it:

(dolist ((x y) '(1 2 3 4 5)) ...)

-> (dolist ((x y) '(1 2 3 4 5 ())) ...)

(dolist (x '(1 2 3 4) n '(a b)) ...)

-> (dolist (x '(1 2 3 4) n '(a b () ())) ...)



Also:

(dolist (x '(1 2 3 4) n '(a b)) ...)

can be written like:

(dolist ((x n) '(1 2 3 4) '(a b)) ...)

so all the variables are in the first list



Hm... but that would lead to nested lists:

(dolist ((x y) '(1 2 3 4) (w z) '(5 6 7 8)) ...)

rewritten:

(dolist (((x y) (w z)) '(1 2 3 4) '(5 6 7 8)) ...)





Fanda

[nigelbrown]

Nigel: Silly me - I used 2 different functions and compared the speed ;-)

...

So, I would say:

- map is pretty fast for simple functions

- dolist is good for complicated functions and nested lists  (try to nest it 3x, 4x times)



Fanda

Hi Fanda,

I think you are still letting dolist off tooooo lightly.

In your comparison the outer dolist had only to iterate, rather than iterate and collect, so the result was not the same as for the map code. Adding a collection step to the outer dolist so the codes give the same output gives about the same times - consider:

> (time (dotimes (i 100000) (setq r1 '())(dolist (x M) (setq r '())(dolist (y x) (push (first y) r -1)) (push r r1 -1))))

1359

> r1

((1 3) (5 7))

> (time (dotimes (i 100000) (map (lambda (x) (map first x)) M)))

1257

> (map (lambda (x) (map first x)) M)

((1 3) (5 7))

>



map is slightly ahead  (essentially the same).



Nigel

[Fanda]

Oh, oh, oh!

You are right!

I overlooked difference between 'iterating' and 'iterating and collecting'!



Look, what I tried:

> (time (dotimes (i 100000) (setq r '())(map (lambda (x) (map (lambda (y) (push (first y) r -1)) x)) M)))

594

> r

(1 3 5 7)



> (time (dotimes (i 100000) (setq r '())(dolist (x M) (dolist (y x) (push (first y) r -1)))))

250

> r

(1 3 5 7)



This code is what was making me to say, that 'map' is slow. But it's not really true, because the nature of map is to iterate and also collect results. It means, that in the first example, I iterate, but both maps also return lists which are not being used at all!



> (map (lambda (x) (map (lambda (y) (push (first y) r -1)) x)) M)

((1 3) (5 7))



The inside map collects and returns (1 3) and (5 7) and outside map collects that and returns ((1 3) (5 7)). None of it is being used!

=> !!! That's why it is slower !!!



Ok, I leave the 'map' alone, now ;-))))



Fanda

[Jeremy Dunn]

Here is a version of the group function that I wrote that gives you a few more options. I tend to like the enhanced dolist suggestion simply because I can more easily see what is going on. I know it can be done other ways but I am not always as abstract as I would like to be.

Code Select Expand


;; This function performs a multiple slice on a given list
;; One supplies a list and an integer n. The list is broken into a list of sublists of
;; length n. If n is negative the list items are collected going from the end of the list
;; to the beginning. If the optional bool argument is supplied then remaining elements are
;; included in the result.
;; (group '(1 2 3 4 5 6 7) 3)       -> ((1 2 3)(4 5 6))
;; (group '(1 2 3 4 5 6 7) 3 true)  -> ((1 2 3)(4 5 6)(7))
;; (group '(1 2 3 4 5 6 7) -3 true) -> ((1)(2 3 4)(5 6 7))
(define (group lst n bool , len num rep rem start)
  (setq num (abs n))
  (if (< n 0)
      (reverse (map reverse (group (reverse lst) num bool)))
      (= n 0)
      nil
      (begin
        (setq len   (length lst)
              rep   (/ len num)
              rem   (% len num)
              start '()
        )
        (if (< num len)
            (begin
              (dotimes (x rep)
                (setq start (cons (slice lst (* x num) num) start)))
              (if (and bool (> rem 0))
                  (setq start (cons (slice lst (* num rep) rem) start)))
              (reverse start))
            (list lst)))))


[Dmi]

I'm slightly busy now, so I cant flame here with full power :-( ;-)

But checking some code, I found some unexpectance:

Code Select Expand

newLISP v.8.6.1 on linux, execute 'newlisp -h' for more info.

> (array 0 1 '(1 2 3))

Command terminated

....newlisp exits here

Possible zero-length dimension checking must to be in (array) function.

[Lutz]

Thanks for catching this, its fixed in 8.6.5



Lutz