Author Topic: (Challange) Insert at position  (Read 11695 times)

0 Members and 1 Guest are viewing this topic.

JohnK

  • Administrator
  • Seagull
  • Posts: 10603
(Challange) Insert at position
« 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!
    TheSwamp.org (serving the CAD community since 2003)
    Member location map - Add yourself

    Donate to TheSwamp.org

    JohnK

    • Administrator
    • Seagull
    • Posts: 10603
    (Challange) Insert at position
    « Reply #1 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.
    TheSwamp.org (serving the CAD community since 2003)
    Member location map - Add yourself

    Donate to TheSwamp.org

    MP

    • Seagull
    • Posts: 17750
    • Have thousands of dwgs to process? Contact me.
    Re: (Challange) Insert at position
    « Reply #2 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.
      Engineering Technologist • CAD Automation Practitioner
      Automation ▸ Design ▸ Drafting ▸ Document Control ▸ Client
      cadanalyst@gmail.comhttp://cadanalyst.slack.comhttp://linkedin.com/in/cadanalyst

      CAB

      • Global Moderator
      • Seagull
      • Posts: 10401
      (Challange) Insert at position
      « Reply #3 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)
      )
      I've reached the age where the happy hour is a nap. (°¿°)
      Windows 10 core i7 4790k 4Ghz 32GB GTX 970
      Please support this web site.

      MP

      • Seagull
      • Posts: 17750
      • Have thousands of dwgs to process? Contact me.
      (Challange) Insert at position
      « Reply #4 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
      Engineering Technologist • CAD Automation Practitioner
      Automation ▸ Design ▸ Drafting ▸ Document Control ▸ Client
      cadanalyst@gmail.comhttp://cadanalyst.slack.comhttp://linkedin.com/in/cadanalyst

      JohnK

      • Administrator
      • Seagull
      • Posts: 10603
      (Challange) Insert at position
      « Reply #5 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?
      TheSwamp.org (serving the CAD community since 2003)
      Member location map - Add yourself

      Donate to TheSwamp.org

      CAB

      • Global Moderator
      • Seagull
      • Posts: 10401
      (Challange) Insert at position
      « Reply #6 on: July 30, 2004, 01:59:47 PM »
      WOW, 500!
      I had no idea there was that much difference.
      I've reached the age where the happy hour is a nap. (°¿°)
      Windows 10 core i7 4790k 4Ghz 32GB GTX 970
      Please support this web site.

      CAB

      • Global Moderator
      • Seagull
      • Posts: 10401
      (Challange) Insert at position
      « Reply #7 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))
      )
      I've reached the age where the happy hour is a nap. (°¿°)
      Windows 10 core i7 4790k 4Ghz 32GB GTX 970
      Please support this web site.

      JohnK

      • Administrator
      • Seagull
      • Posts: 10603
      (Challange) Insert at position
      « Reply #8 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?!
      TheSwamp.org (serving the CAD community since 2003)
      Member location map - Add yourself

      Donate to TheSwamp.org

      CAB

      • Global Moderator
      • Seagull
      • Posts: 10401
      (Challange) Insert at position
      « Reply #9 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
      I've reached the age where the happy hour is a nap. (°¿°)
      Windows 10 core i7 4790k 4Ghz 32GB GTX 970
      Please support this web site.

      MP

      • Seagull
      • Posts: 17750
      • Have thousands of dwgs to process? Contact me.
      (Challange) Insert at position
      « Reply #10 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*.

      :)
      Engineering Technologist • CAD Automation Practitioner
      Automation ▸ Design ▸ Drafting ▸ Document Control ▸ Client
      cadanalyst@gmail.comhttp://cadanalyst.slack.comhttp://linkedin.com/in/cadanalyst

      JohnK

      • Administrator
      • Seagull
      • Posts: 10603
      (Challange) Insert at position
      « Reply #11 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!?
      TheSwamp.org (serving the CAD community since 2003)
      Member location map - Add yourself

      Donate to TheSwamp.org

      CAB

      • Global Moderator
      • Seagull
      • Posts: 10401
      (Challange) Insert at position
      « Reply #12 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. :)
      I've reached the age where the happy hour is a nap. (°¿°)
      Windows 10 core i7 4790k 4Ghz 32GB GTX 970
      Please support this web site.

      MP

      • Seagull
      • Posts: 17750
      • Have thousands of dwgs to process? Contact me.
      (Challange) Insert at position
      « Reply #13 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. :)
      Engineering Technologist • CAD Automation Practitioner
      Automation ▸ Design ▸ Drafting ▸ Document Control ▸ Client
      cadanalyst@gmail.comhttp://cadanalyst.slack.comhttp://linkedin.com/in/cadanalyst

      SMadsen

      • Guest
      (Challange) Insert at position
      « Reply #14 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)