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

0 Members and 1 Guest are viewing this topic.

CAB

  • Global Moderator
  • Seagull
  • Posts: 10365
(Challange) Insert at position
« Reply #15 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
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.

John Kaul (Se7en)

  • Administrator
  • Needs a day job
  • Posts: 9267
(Challange) Insert at position
« Reply #16 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

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!
“Common sense is not so common.” ~Voltaire

--> Donate to TheSwamp.org <--

sinc

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

John Kaul (Se7en)

  • Administrator
  • Needs a day job
  • Posts: 9267
(Challange) Insert at position
« Reply #18 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
“Common sense is not so common.” ~Voltaire

--> Donate to TheSwamp.org <--

Sdoman

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

CAB

  • Global Moderator
  • Seagull
  • Posts: 10365
(Challange) Insert at position
« Reply #20 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
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.

Sdoman

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

CAB

  • Global Moderator
  • Seagull
  • Posts: 10365
(Challange) Insert at position
« Reply #22 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?
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.

Sdoman

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

SMadsen

  • Guest
(Challange) Insert at position
« Reply #24 on: August 01, 2004, 09:38:59 PM »
Steve, good point about stopping and simply append the remaining list. Nice work!

Sdoman

  • Guest
(Challange) Insert at position
« Reply #25 on: August 01, 2004, 10:34:35 PM »
Thanks a billion Stig!