Jump to content
wishbonesr

nth-replace (mergesort's achilles heel)

Recommended Posts

wishbonesr

I've completed MergeSort algorithm implementation in Autolisp based on Ellis Dee's vb6 version here: http://www.vbforums.com/showpost.php?p=2909257&postcount=12

 

The problem is that I need to replace nth atom in the lisp array, and the only way I can currently accomplish this, is by iterating the entire list. This takes, what would be a spectacular sorting algorithm, and destroys it's efficiency by iterating the list nth(log) times. I'm going to try not to muddy the water too much, but here is my nth-replace function based on Michels nth-remove function...

 

  (defun nth-replace (n_atom f_list f_n / ) ;replaced the nth element of a list
   ;n_atom is new atom
   ;f_list is list to be operated on
   ;f_n is the index that will be replaced
   (if (and (numberp f_n) (listp f_list))
     (if (and (>= f_n 0) (< f_n (length f_list)) n_atom)
(progn
  (repeat f_n
    (setq f_list (append (cdr f_list) (list (car f_list))))
    )
  (setq f_list (append (cdr f_list) (list n_atom)))
  (repeat (- (length f_list) f_n 1)
    (setq f_list (append (cdr f_list) (list (car f_list))))
    )
  )
)
     )
   f_list
   );defun

 

I'm not completely new to autolisp, but I'm hoping there's a fundamental function I'm overlooking that can either replace an atom at a certain level, or can return a list up to a certain atom (nth instance), and then I can append my change, and then the latter half of the list.

Share this post


Link to post
Share on other sites
BlackBox

Consider this example:

 

(defun replace3 ( alist position newitem / i )
   (setq i -1)
   (mapcar '(lambda ( x ) (if (= position (setq i (1+ i))) newitem x)) alist)
)

 

linky

 

** Edit - Sample from VLIDE Console:

 

REPLACE3 
_$ (replace3 '(1 2 3 3 2 1) 3 4)
(1 2 3 4 2 1)
_$ 

Share this post


Link to post
Share on other sites
Stefan BMR

First thought..

(defun nth-rep (x l n / i)
 (setq i -1)
 (mapcar '(lambda (a) (cond ((= (setq i (1+ i)) n) x) (a))) l)
 )

EDIT: Oops... too late

Share this post


Link to post
Share on other sites
alanjt

quickie, but should work...

 

(defun _nthReplace (item index lst)
 (if (and lst (> index 0))
   (cons (car lst) (_nthReplace item (1- index) (cddr lst)))
   (cons item (cdr lst))
 )
)

Share this post


Link to post
Share on other sites
wishbonesr

Renderman / Stefan BMR

Spectacular Gentlemen. Freaking spectacular.

If I could express my elation, I would have to type that about 5000 times.

 

It makes so much sense, I'm embarassed. Optimized without a recreated var.

So after testing both the IF and the COND method, the IF won by 3 seconds when processing 1000 random numbers. Keeping in mind that either were lightyears from what I had, which I stopped processing after a couple of hours.

 

IF Results:

Time: 
15.19 seconds
; 10 forms loaded from #<editor ".../mergesort2.LSP">
_1_$ 

 

COND Results:

Time: 
18.02 seconds
; 10 forms loaded from #<editor ".../mergesort2.LSP">
_1_$

 

 

Posting MergeSort in a seperate thread.

Share this post


Link to post
Share on other sites
BlackBox
Renderman / Stefan BMR

Spectacular Gentlemen. Freaking spectacular.

If I could express my elation, I would have to type that about 5000 times.

 

Lee deserves credit for the code that I posted above, as he presented that offering as an enhanced version of my own (earlier in the same thread, linked above). LoL

 

... I am glad it helped you, though. :beer:

Share this post


Link to post
Share on other sites
LibertyOne

Just a question I have after reading this thread. In AutoLisp why wouldn't subst work?

 

(subst ITEM (nth INDEX LST) LST)

Share this post


Link to post
Share on other sites
Stefan BMR

Try

(subst 1 0 '(0 1 0 2 0))

subst

 

Searches a list for an old item and returns a copy of the list with a new item substituted in place of every occurrence of the old item

 

Share this post


Link to post
Share on other sites
BlackBox

Stefan is correct - Lee also makes this point to me, in the linked thread above. :thumbsup:

Share this post


Link to post
Share on other sites
alanjt

i thought the point was the replace the nth item, not every matching item.

Share this post


Link to post
Share on other sites
BlackBox
i thought the point was the replace the nth item, not every matching item.

 

*Touches finger to nose*

 

... That's why Stefan (here), and Lee (in the linked thread) advise against using SUBST.

Share this post


Link to post
Share on other sites
alanjt
*Touches finger to nose*

 

... That's why Stefan (here), and Lee (in the linked thread) advise against using SUBST.

Oops, his and liberty's post as one.

Share this post


Link to post
Share on other sites
LibertyOne

OK - I see the point in not using subst.

 

I would like to tinker around with this myself a bit but don't have an AutoLisp interpreter handy at the moment and my fingers are really itching!

Could someone copy the following code and tell me what is returned? Thanks!

(setq mylist '(a b c d e f))
(setq flist (cons (nth 3 mylist) nil))

Share this post


Link to post
Share on other sites
BlackBox

I would like to tinker around with this myself a bit but don't have an AutoLisp interpreter handy at the moment and my fingers are really itching!

Could someone copy the following code and tell me what is returned?

 

implied-facepalm.jpg

Share this post


Link to post
Share on other sites
LibertyOne
implied-facepalm.jpg

 

ok - no answer is also an answer... :glare:

Share this post


Link to post
Share on other sites
BlackBox
ok - no answer is also an answer... :glare:

 

I read your request; the "Implied Facepalm" image IS what was returned on my end...

 

Okay, I'll stop... Since you were a good sport about it, here you go :D:

 

_$ (setq mylist '(a b c d e f))
(A B C D E F)
_$ (setq flist (cons (nth 3 mylist) nil))
(D)
_$ 

Share this post


Link to post
Share on other sites
LibertyOne

Thanks for the reply, RenderMan. I really have to complain a bit now that I have no access to an AutoCAD command line. Being able to write code the last 13 years and then having no AutoCAD is like going cold-turkey!

 

I was assuming that (D) was going to be returned but wasn't 100% sure. (About 2% was thinking (A B C D)) I've been reading about cons cells lately, and wanred to practice...

Share this post


Link to post
Share on other sites
BlackBox
Thanks for the reply, RenderMan.

 

You're welcome.

 

I really have to complain a bit now that I have no access to an AutoCAD command line. Being able to write code the last 13 years and then having no AutoCAD is like going cold-turkey!

 

I have nowhere near your experience, but if things do not improve at my place of work in the very immediate future, I too may be able to relate to your dilemma.

Share this post


Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.
Note: Your post will require moderator approval before it will be visible.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.


×
×
  • Create New...