TheSwamp

Code Red => AutoLISP (Vanilla / Visual) => Topic started by: John Kaul (Se7en) on July 30, 2004, 12:11:18 PM

Title: (Challange) Insert at position
Post by: John Kaul (Se7en) on July 30, 2004, 12:11:18 PM
Alright you guys, you know the rules! Get to it!

I want a tool to insert an item into a list at a specific postion (zero based).

(<tool name here> [item] [position])

Example:
given a list: (1 2 4 5 6 7)

(insert@ '(1 2 4 5 6 7) 3 2)
-> (1 2 3 4 5 6 7)

And ....GO!
Title: (Challange) Insert at position
Post by: John Kaul (Se7en) on July 30, 2004, 12:14:51 PM
OBTW, I found one of Reni's posts that has a util like this a few days ago and i thought it was a good idea for a challenge.  

...And since im using Crappystation today i will post that procedure a bit later and maybe get to writing one of my own at lunch.
Title: Re: (Challange) Insert at position
Post by: MP on July 30, 2004, 12:48:10 PM
Quote from: Se7en
Alright you guys, you know the rules! Get to it!

I want a tool to insert an item into a list at a specific postion (zero based).

(<tool name here>
    [item] [position])

    Example:
    given a list: (1 2 4 5 6 7)

    (insert@ '(1 2 4 5 6 7) 3 2)
    -> (1 2 3 4 5 6 7)

    And ....GO!

    Certainly not optimized, but here's my quick stab at it:
    Code: [Select]
    (defun ListInsert ( lst item position / i index1 index2 )
        (cond
            (   (< position 1) (cons item lst))
            (   (< (length lst) position) (append lst (list item)))
            (   (setq i -1)
                (append
                    (reverse
                        (mapcar 'cdr
                            (member
                                (assoc (1- position)
                                    (setq index2
                                        (reverse
                                            (setq index1
                                                (mapcar
                                                   '(lambda (x) (cons (setq i (1+ i)) x))
                                                    lst
                                                )
                                            )
                                        )
                                    )    
                                )
                                index2
                            )    
                        )
                    )
                    (list item)
                    (mapcar 'cdr (member (assoc position index1) index1))
                )
            )
        )    
    )


    (listinsert '(1 2 4 5 6 7) 3 2) ==> (1 2 3 4 5 6 7)

    Cheers,

    M.
    Title: (Challange) Insert at position
    Post by: CAB on July 30, 2004, 01:19:44 PM
    Code: [Select]
    (defun insert@ (lst itm pos / nlst idx)
      (setq nlst '()
            idx -1)
      (while (< (setq idx (1+ idx)) (length lst))
        (if (= idx pos)
          (setq nlst (cons (nth idx lst) (cons itm nlst)))
          (setq nlst (cons (nth idx lst) nlst))
        )
      )
      (reverse nlst)
    )
    Title: (Challange) Insert at position
    Post by: MP on July 30, 2004, 01:44:27 PM
    Quote from: CAB
    Code: [Select]
    (defun insert@ (lst itm pos / nlst idx)
      (setq nlst '()
            idx -1)
      (while (< (setq idx (1+ idx)) (length lst))
        (if (= idx pos)
          (setq nlst (cons (nth idx lst) (cons itm nlst)))
          (setq nlst (cons (nth idx lst) nlst))
        )
      )
      (reverse nlst)
    )

    Hi CAB,

    It is tempting to go that route, because it's less code, but you would be surprised at the difference in performance. Try this:

    (setq lst '(0 0))

    (repeat 15 (setq lst (append lst lst)))

    Now bench the execution time of

    (ListInsert lst 1 1)

    versus

    (Insert@ lst 1 1)

    Actually, you don't even neeed to bench it, the difference is dramatic enough you don't need execution times to see the difference (which is the order of about 500). Obviously on short lists the performance difference is negligable, but I frequently deal with huge lists, thus the performance concern.

    Havin' fun,

    M
    Title: (Challange) Insert at position
    Post by: John Kaul (Se7en) on July 30, 2004, 01:56:15 PM
    w00t! discussion!

    CAB, that is the same thing i was thinking.

    MP, good point.

    As i promised, here is Reni U.'s procedure.

    Code: [Select]
    ;;; Insert atom in list at pos n
    (defun insert (lst x n)
      (cond
        ((zerop n) (cons x lst))
        (T (cons (car lst) (insert (cdr lst) x (1- n))))))


    Now taking into concideration MP's big list point and the fact that this lil procedure uses a recursive method, should there be a concern?
    Title: (Challange) Insert at position
    Post by: CAB on July 30, 2004, 01:59:47 PM
    WOW, 500!
    I had no idea there was that much difference.
    Title: (Challange) Insert at position
    Post by: CAB on July 30, 2004, 02:21:12 PM
    OK, How about this one :shock:
    Code: [Select]
    (defun insert@ (lst itm pos / ptr)
      (setq ptr (nth pos lst))
      (append (reverse(cdr(member ptr (reverse lst)))) (list itm) (member ptr lst))
    )
    Title: (Challange) Insert at position
    Post by: John Kaul (Se7en) on July 30, 2004, 03:32:34 PM
    I think it looks perty CAB. (Does that count?)

    What no one else has a say 'cept MP CAB and Reni?!
    Title: (Challange) Insert at position
    Post by: CAB on July 30, 2004, 03:44:48 PM
    Here are my timer test.
    Code: [Select]

      (startTimer)
      ;;;=============================================================
      (repeat 1000
       (Insert '(1 2 4 5 6 7) 3 2)
      )
      ;;;=============================================================
      (endTimer "instest")

    ==============================
    New insert@
    Timed instest: 0.009978
    Timed instest: 0.009978
    Timed instest: 0.009978
    ==============================
    Old insert@
    Timed instest: 0.029974
    Timed instest: 0.029974
    Timed instest: 0.029974
    Timed instest: 0.029974
    ==============================
    M's ListInsert Routine
    Timed instest: 0.059988
    Timed instest: 0.059988
    Timed instest: 0.059988
    ==============================
    Old insert@ again
    Timed instest: 0.030014
    Timed instest: 0.019996
    Timed instest: 0.029974
    Timed instest: 0.019996
    Timed instest: 0.029974
    ==============================
    New insert@ again
    Timed instest: 0.020036
    Timed instest: 0.010018
    Timed instest: 0.009978
    Timed instest: 0.009978
    Timed instest: 0.019996
    Timed instest: 0.019996
    Timed instest: 0.010018
    Timed instest: 0.010018
    Timed instest: 0.009978
    ==============================
    M's ListInsert Routine again
    Timed instest: 0.059988
    Timed instest: 0.059988
    Timed instest: 0.070006
    Timed instest: 0.059988
    Timed instest: 0.070006
    Timed instest: 0.060028
    Timed instest: 0.059988
    Timed instest: 0.060028
    Timed instest: 0.060993
    Timed instest: 0.070006
    ==============================
    Insert by Reni U.
    Timed instest: 0.009978
    Timed instest: 0.010018
    Timed instest: 0.010018
    Timed instest: 0.010018
    Timed instest: 0.009978
    Timed instest: 0.009978
    Timed instest: 0.009978
    Timed instest: 0.010018
    Timed instest: 0.010018
    Timed instest: 0.009978
    Title: (Challange) Insert at position
    Post by: MP on July 30, 2004, 05:17:18 PM
    I think you will find that your new function only works as long as every single item in the existing list is unique.

    The performance of Reine's function progressivley degrades the closer the replacement position is to the far end of the list (when the list is of significant length).

    Also, Reine's is limitied by the stack (because it recurses). Try Reine's function on the list I created above and insert at the second last position.

    *Kaboom*.

    :)
    Title: (Challange) Insert at position
    Post by: John Kaul (Se7en) on July 30, 2004, 05:22:32 PM
    MP, Thats kinda my point. What makes Mapcar free form that restraint since it too is recursive  by nature. ...well for that matter Lisp is recursive isnt it!?
    Title: (Challange) Insert at position
    Post by: CAB on July 30, 2004, 05:42:16 PM
    Quote from: MP
    I think you will find that your new function only works as long as every single item in the existing list is unique.


    SHOOT, BACK TO THE DRAWING BOARD. :)
    Title: (Challange) Insert at position
    Post by: MP on July 30, 2004, 07:56:26 PM
    Quote from: Se7en
    MP, That's kinda my point. What makes Mapcar free form that restraint since it too is recursive  by nature. ...well for that matter Lisp is recursive isn't it!?

    Is mapcar recursive? I don't know that it is or isn't, but I'm leaning towards not.  If it were recursive it would be subject to stack failures, and I've never seen a mapcar call produce a stack failure. That doesn't mean it can't happen, just that I've never seen it happen in 15 years of LISP programming.

    LISP comfortably supports recursive calls (the first language to support recursion if I'm not mistaken), but I wouldn't say "it's recursive". LIST based for sure, and some LISP processing is recursive, but in my way of thinking a blanket "is recursive" statement doesn't fit. However, this is another unqualified opinion.

    Having said that, I'm just a hack -- some real bit head with fully functioning grey matter will have to step up to the plate because I don't know the internal workings of the LISP engine.

    Cheers. :)
    Title: (Challange) Insert at position
    Post by: SMadsen on July 30, 2004, 08:15:30 PM
    I'd do it much like CAB's first INSERT@ function

    Code: [Select]
    (defun insert@ (lst item n / a nlst)
      (setq a 0)
      (while lst
        (and (= a n) (setq nlst (cons item nlst)))
        (setq nlst (cons (car lst) nlst)
              lst  (cdr lst)
              a    (1+ a))
      )
      (reverse nlst)
    )


    (setq alst '(A B C D E F G))
    (insert@ alst '(X Y Z) 3)
    (A B C (X Y Z) D E F G)
    Title: (Challange) Insert at position
    Post by: CAB on July 30, 2004, 08:41:11 PM
    Here is Stig's run at the timer
    Stig's Insert@
    Timed instest: 0.019996
    Timed instest: 0.029974
    Timed instest: 0.029974
    Timed instest: 0.019996
    Timed instest: 0.019996
    Timed instest: 0.030014
    Timed instest: 0.019996
    Timed instest: 0.019996
    Timed instest: 0.019996
    Timed instest: 0.029974
    Timed instest: 0.030014
    Timed instest: 0.019996
    Timed instest: 0.019996
    Title: (Challange) Insert at position
    Post by: John Kaul (Se7en) on July 30, 2004, 10:27:04 PM
    Mapcar is recursive by nature. (Im almost postitve!) Here is an entry from Structure and Interpretation of Computer Programs (http://mitpress.mit.edu/sicp/full-text/book/book.html)

    Code: [Select]
    Mapping over lists

    One extremely useful operation is to apply some transformation to each element in a list and generate the list of results. For instance, the following procedure scales each number in a list by a given factor:

    (define (scale-list items factor)
      (if (null? items)
          nil
          (cons (* (car items) factor)
                (scale-list (cdr items) factor))))
    (scale-list (list 1 2 3 4 5) 10)
    (10 20 30 40 50)

    We can abstract this general idea and capture it as a common pattern expressed as a higher-order procedure, just as in section 1.3. The higher-order procedure here is called map. Map takes as arguments a procedure of one argument and a list, and returns a list of the results produced by applying the procedure to each element in the list:12

    (define (map proc items)
      (if (null? items)
          nil
          (cons (proc (car items))
                (map proc (cdr items)))))
    (map abs (list -10 2.5 -11.6 17))
    (10 2.5 11.6 17)


    This  doesnt prove that it is but since Autolisp is alot like scheme i would assume that "map-car" is recursive. Besides the name makes sence; Map a procedure to the first in the list.

    But, we are doing nothing but splitting hairs here. Recursive is recursive. Seeing as recursion is a basic principle for problem solving in programing i would suspect that 90% of our functions are in fact recursive by nature.

    ...maybe its not subject to stack failures because of built in error traping in the intripriter. huh?

    Gawd i love these discussions! They get me thinking!
    Title: (Challange) Insert at position
    Post by: sinc on August 01, 2004, 02:27:00 AM
    It doesn't say anything about mapcar, but here's something kind of interesting that explains where car and cdr came from:

    http://www-formal.stanford.edu/jmc/history/lisp/lisp.html
    Title: (Challange) Insert at position
    Post by: John Kaul (Se7en) on August 01, 2004, 11:36:18 AM
    What dosent say anything about mapcar?

    Yes that is a very good reference to have. I had another (similar) one at one time, ill have to look arround for it when i get some time.  Good find!

    Heres the almost exact same reference to what CAR & CDR stand for in the Struct&Intrip book. LINK (http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-14.html#footnote_Temp_133)
    Title: (Challange) Insert at position
    Post by: Sdoman on August 01, 2004, 08:07:48 PM
    Had some time to play with this today.  So here's my two cents worth, if anyone is still watching.  Not sure if this is any faster.
    Code: [Select]

    (defun insert@ (lst item pos / tmp)
      ;; Insert item into lst at pos, zero based
      (repeat pos
        (setq tmp (cons (car lst) tmp)
              lst (cdr lst)
        )
      )
      (append (reverse tmp) (list item) lst)
    )


    (setq alst '(A B C (1 2 3) D E F G))
    (length alst) -> 8

    (insert@ alst '(X Y Z) 0) -> ((X Y Z) A B C (1 2 3) D E F G)
    (insert@ alst '(X Y Z) 3) -> (A B C (X Y Z) (1 2 3) D E F G)
    (insert@ alst '(X Y Z) 8) -> (A B C (1 2 3) D E F G (X Y Z))
    (insert@ alst '(X Y Z) 10) -> (A B C (1 2 3) D E F G nil nil (X Y Z))

    In the last example you can see that the value of the argument 'Pos was larger then the number of positions existing in the argument 'Lst.  Hence, the function padded the result with nils in order to put Iitem at 'Pos.  

    I'm not sure if that's the best way to handle this "position overflow" condition.  Perhaps the function should simply return nil under this condition.

    Comments anyone?

    Regards,
    Steve Doman
    Title: (Challange) Insert at position
    Post by: CAB on August 01, 2004, 08:27:33 PM
    Nice Job Steve.
    It's pritty quick.

    Timed instest: 0.019996
    Timed instest: 0.020036
    Timed instest: 0.019996
    Timed instest: 0.019996
    Timed instest: 0.009978
    Timed instest: 0.020036
    Timed instest: 0.009978
    Title: (Challange) Insert at position
    Post by: Sdoman on August 01, 2004, 08:32:32 PM
    Thanks for time testing CAB.

    While you where doing that, I was editing my previous post with a comment about overflow.  (Sorry, probably should have created a new post)

    What do you think about the result of the function when given a "postiion overflow" condition?
    Title: (Challange) Insert at position
    Post by: CAB on August 01, 2004, 08:40:11 PM
    Did not have much of a change.

    Timed instest: 0.019996
    Timed instest: 0.019996
    Timed instest: 0.010018
    Timed instest: 0.009978
    Timed instest: 0.010018
    Timed instest: 0.019996
    Timed instest: 0.009978
    Timed instest: 0.009978
    Timed instest: 0.019996
    Timed instest: 0.010018
    Timed instest: 0.020036
    Timed instest: 0.019996


    One thing I noticed about Stig's routine.
    There were a few .03 which I did not see in other runs.
    I ran Stig's again and they reappeared. Something going on there?
    Title: (Challange) Insert at position
    Post by: Sdoman on August 01, 2004, 08:49:16 PM
    Cab,

    I didn't change my code, I added a comment to the end of my first post :)
    Sorry 'bout all the confusion.

    Regading Stig's function, perhaps the timer results are larger when his function is tested on very long lists, since it keeps iterating to the end of the list, rather than stopping at the target postion.
    Title: (Challange) Insert at position
    Post by: SMadsen on August 01, 2004, 09:38:59 PM
    Steve, good point about stopping and simply append the remaining list. Nice work!
    Title: (Challange) Insert at position
    Post by: Sdoman on August 01, 2004, 10:34:35 PM
    Thanks a billion Stig!