Topic: Single dimensional list to duoble dimensional

[irneb]

Many a time you need a list of coordinates, but when working with ActiveX mostly you get a flat array of numbers. Say with a polyline's Coordinates property.

So here I'm attempting a quick-fix to change a list like (X Y X Y X Y ...) into ((X Y) (X Y) (X Y)).

First idea:

Code: [Select]

(defun list-group (lst n / res item)
  (while lst
    (setq item nil)
    (repeat n (setq item (cons (car lst) item) lst (cdr lst)))
    (setq res (cons (reverse item) res)))
  (reverse res))Some sample code:

Code: [Select]

_$ (list-group '(1 2 3 4 5 6 7 8 9) 3)
((1 2 3) (4 5 6) (7 8 9))
_$ (list-group '(1 2 3 4 5 6 7 8 9 10) 3)
((1 2 3) (4 5 6) (7 8 9) (10 nil nil))Clearly if the length of the list is not divisible by the group-by number, you're going to get those nils at the end.

I'm trying to steer clear of nth, since it's rather less efficient than most other methods. Otherwise a simple double increment integer index would have been the most straight-forward principle. Something like this:

Code: [Select]

(defun list-group-i (lst n / item res i j)
  (setq i (length lst))
  (while (>= (setq i (1- i)) 0)
    (setq j n item nil)
    (while (>= (setq j (1- j)) 0)
      (setq item (cons (nth (+ i j) lst) item)))
    (setq res (cons item res) i (- i n -1)))
  res)
And yes I have thought of making that 1st one only use one reverse on the main list and then work backwards. Though then what should happen to the case where the list length is not divisible by the grouping count? Perhaps this:

Code: [Select]

(defun list-group1 (lst n / res item)
  (setq lst (reverse lst))
  (repeat (- n (rem (length lst) n)) (setq lst (cons nil lst)))
  (while lst
    (setq item nil)
    (repeat n (setq item (cons (car lst) item) lst (cdr lst)))
    (setq res (cons item res)))
  res)
Results thus far on a list of 5000 length:

Code: [Select]

Benchmarking ..........Elapsed milliseconds / relative speed for 128 iteration(s):

    (LIST-GROUP1 LST 5)......1030 / 6.53 <fastest>
    (LIST-GROUP LST 5).......1061 / 6.34
    (LIST-GROUP-I LST 5).....6723 / 1 <slowest>Clearly the indexed version is way slower than the others. Anyone have any other ideas?

[Lee Mac]

My offering:

http://lee-mac.com/groupbynum.html

Challenge thread:

http://www.theswamp.org/index.php?topic=32428.0

Challenge thread 2:

http://www.theswamp.org/index.php?topic=5108.0

[MP]

This is what I have in my library. I'm not saying it's faster, in fact it's likely slower than any of the ones in this thread (no time to bench). It's rather simplistic -- I ante it up soley because it does things differently; sharing differences being the swamp way:

Code: [Select]

(defun _SubLists ( lst n / sublist result )

    ;;  Given:  a list of (1 2 3 4 5 6 7 8)
    ;; 
    ;;          and n values of 2, 3 and 4
    ;;
    ;;  Return: ((1 2) (3 4) (5 6) (7 8))
    ;;          ((1 2 3) (4 5 6) (7 8))
    ;;          ((1 2 3 4) (5 6 7 8))
    ;;
    ;;  respectively.

    (foreach x lst       
        (if (eq n (length (setq sublist (cons x sublist))))
            (setq
                result  (cons (reverse sublist) result)
                sublist nil
            )           
        )       
    )
   
    (reverse
        (if sublist
            (cons (reverse sublist) result)
            result
        )
    )   
)
FWIW, cheers.

PS: It doesn't return nil values where the original list is not evenly divisible by the sublist length.

[irneb]

... I'm not saying it's faster ...

Strange that you should mention that ... or perhaps not  :whistle:

Code: [Select]

Benchmarking ...........Elapsed milliseconds / relative speed for 256 iteration(s):

    (_SUBLISTS LST 5)...........1716 / 1.15 <fastest>
    (LIST-GROUP1 LST 5).........1903 / 1.03
    (LM:GROUPBYNUM-R LST 5).....1950 / 1.01
    (LIST-GROUP LST 5)..........1966 / 1
    (LM:GROUPBYNUM LST 5).......1966 / 1 <slowest>Obviously I axed the embarrassing index version  :ugly:

Edit: I'm not too sure if this is "wrong" per say:

Code: [Select]

_$ (_Sublists '(1 2 3 4 5 6 7 8 9 10) 3)
((1 2 3) (4 5 6) (7 8 9) (10))Effectively the same thing isn't it?

And Lee, though your recursive is faster than your iterative (only just), I'd be unwilling to use it on large lists - remember that ~20k error cut-off on recursion.

[irneb]

Challenge thread:

http://www.theswamp.org/index.php?topic=32428.0

Challenge thread 2:

http://www.theswamp.org/index.php?topic=5108.0

Typical!

There are no more challenges ... only redoing the same old thing again!

Sorry guys, I should've searched before starting this thread.

[irneb]

Whahaha!

I thought MP was onto a good idea, So I thought I'd modify a bit to make less reverses (as per my previous code):

Code: [Select]

(defun list-group (lst n / sub res)
  (setq lst (reverse lst))
  (repeat (- n (rem (length lst) n)) (setq lst (cons nil lst)))
  (foreach x lst
    (if (eq n (length (setq sub (cons x sub))))
      (setq res (cons sub res) sub nil)))
  (if sub
    (cons sub res)
    res))
Just look at the benchmarking including the fastest from those other threads:

Code: [Select]

Benchmarking ............Elapsed milliseconds / relative speed for 512 iteration(s):

    (GBN_1_EV LST 5)...................1622 / 3.11 <fastest>
    (LIST-GROUP LST 5).................3947 / 1.28
    (GROUPBYNUM_MAC4 LST 5)............4025 / 1.25
    (_SUBLISTS LST 5)..................4072 / 1.24
    (GROUPBYNUM_MAC3 LST 5)............4228 / 1.19
    (LIST-GROUP-STEPREVERSE LST 5).....4555 / 1.11
    (LM:GROUPBYNUM LST 5)..............4633 / 1.09
    (LM:GROUPBYNUM-R LST 5)............4633 / 1.09
    (GROUPBYNUM_MAC2 LST 5)............4633 / 1.09
    (GBN LST 5)........................4696 / 1.07
    (LIST-GROUP-STEP LST 5)............4711 / 1.07
    (WIZ-GRP LST 5)....................4789 / 1.05
    (GROUPBYNUM_VK LST 5)..............4790 / 1.05
    (GROUPBYNUM_MAC LST 5).............4820 / 1.05
    (SPLIT LST 5)......................5039 / 1 <slowest>Should've remembered from my programming lectures: "Divide and conquer is what makes Quick Sort live up to its name".

Leave it for Evgeniy to remember to do this!

[CAB]

Looks like my attempt did not make the cut. 
http://www.theswamp.org/index.php?topic=5108.msg61975#msg61975

[irneb]

Looks like my attempt did not make the cut. 
http://www.theswamp.org/index.php?topic=5108.msg61975#msg61975

Sorry, missed yours from that huge list of attempts.

Code: [Select]

Benchmarking ............Elapsed milliseconds / relative speed for 512 iteration(s):

    (GBN_1_EV LST 5)...................1654 / 3.1 <fastest>
    (LIST-GROUP LST 5).................3947 / 1.3
    (_SUBLISTS LST 5)..................4056 / 1.27
    (GROUPBYNUM_MAC4 LST 5)............4134 / 1.24
    (GROUPBYNUM_MAC3 LST 5)............4259 / 1.2
    (LIST-GROUP-STEPREVERSE LST 5).....4524 / 1.13
    (LM:GROUPBYNUM LST 5)..............4649 / 1.1
    (LM:GROUPBYNUM-R LST 5)............4649 / 1.1
    (GBN LST 5)........................4649 / 1.1
    (GROUPBYNUM_MAC2 LST 5)............4665 / 1.1
    (LIST-GROUP-STEP LST 5)............4680 / 1.1
    (GROUPBYNUM_MAC LST 5).............4851 / 1.06
    (GROUPBYNUM_VK LST 5)..............4852 / 1.06
    (WIZ-GRP LST 5)....................4882 / 1.05
    (SPLIT LST 5)......................5023 / 1.02
    (GROUPITEMS LST 5).................5132 / 1 <slowest>Oops ... I think I could've lied and said yours "just" didn't make the cut!  :pissed:

[CAB]

Great, I get the consolation Prize.  :ugly:

[irneb]

OK, doing the same to Evgeniy's code as I did to MP's:

Code - Auto/Visual Lisp: [Select]

1. (defun list-gbn (lst n / i func res list-gbn-temp)
2.   (setq func '(a) i 5 lst (reverse lst))
3.   (repeat (- n (rem (length lst) n)) (setq lst (cons nil lst)))
4.   (while (> (setq i (1- i)) 0)
5.     (repeat (/ n i)
6.       (setq func (cons (nth i '(nil
7.                                 (setq a (cons (car lst) a) lst (cdr lst))
8.                                 (setq a (cons (cadr lst) (cons (car lst) a)) lst (cddr lst))
9.                                 (setq a (cons (caddr lst) (cons (cadr lst) (cons (car lst) a))) lst (cdddr lst))
10.                                 (setq a (cons (cadddr lst) (cons (caddr lst) (cons (cadr lst) (cons (car lst) a)))) lst (cddddr lst))))
11.                        func)))
12.     (setq n (rem n i)))
13.   (eval (cons 'defun (cons 'list-gbn-temp (cons '(a) func))))
14.   (while lst (setq res (cons (list-gbn-temp nil) res)))
15.   res)

And lo and behold, I get another ounce of speed out of it! 

Code: [Select]

Benchmarking ............Elapsed milliseconds / relative speed for 512 iteration(s):

    (LIST-GBN LST 5).....1591 / 1.05 <fastest>
    (GBN_1_EV LST 5).....1669 / 1 <slowest>Also tried to make the original a bit more "elegant" ... though I'm still not happy with those 4 setq's.

[irneb]

Oops, silly me - I forgot about this case:

Code: [Select]

$ (list-gbn '(1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10) 5)
((1 2 3 4 5) (6 7 8 9 10) (1 2 3 4 5) (6 7 8 9 10) (nil nil nil nil nil))Here's the fix:

Code - Auto/Visual Lisp: [Select]

1. (defun list-gbn (lst n / r i func res list-gbn-temp)
2.   (setq func '(a) i 5 lst (reverse lst))
3.   (if (> (setq r (rem (length lst) n)) 0)
4.     (repeat (- n r) (setq lst (cons nil lst))))
5.   (while (> (setq i (1- i)) 0)
6.     (repeat (/ n i)
7.       (setq func (cons (nth i '(nil
8.                                 (setq a (cons (car lst) a) lst (cdr lst))
9.                                 (setq a (cons (cadr lst) (cons (car lst) a)) lst (cddr lst))
10.                                 (setq a (cons (caddr lst) (cons (cadr lst) (cons (car lst) a))) lst (cdddr lst))
11.                                 (setq a (cons (cadddr lst) (cons (caddr lst) (cons (cadr lst) (cons (car lst) a)))) lst (cddddr lst))))
12.                        func)))
13.     (setq n (rem n i)))
14.   (eval (cons 'defun (cons 'list-gbn-temp (cons '(a) func))))
15.   (while lst (setq res (cons (list-gbn-temp nil) res)))
16.   res)

And the benchmark:

Code: [Select]

Benchmarking ............Elapsed milliseconds / relative speed for 512 iteration(s):

    (LIST-GBN LST 5).....1591 / 1.04 <fastest>
    (GBN_1_EV LST 5).....1653 / 1 <slowest>Still a whisker faster!  :kewl:

[Lee Mac]

Nice reworking of Evgeniy's algorithm Irne 

[irneb]

Nice reworking of Evgeniy's algorithm Irne 

Thanks! After re-reading his code several times I finally figured out what was going on ... and then realized: "But this can be combined into a loop can't it?"

Anyhow, as I've stated: "I'm still not happy with it." Those 4 setq's in the nth call is too much double typing - there should be a way of combining that into a loop as well. Of course that would make it slightly less efficient - though not by much as it's a once-off in the function.

[irneb]

Actually this principle is quite useful in other systems. I've incorporated the same in my AutoLisp Extender library's NthCDR and FirstN / LastN functions.

Thank you ElpanovEvgeniy! I've cited you as the originator of such code, without it I'd probably never have though of doing it this way.

[Stefan]

A little too late, but here is mine

Code - Auto/Visual Lisp: [Select]

1. (defun gbn (l n / s r)
2.   (repeat (/ (length l) n)
3.     (setq r (cons (reverse (repeat n (setq s (cons (car l) s) l (cdr l)) s)) r) s nil)
4.     )
5.   (reverse (if l (cons l r) r))
6.   )