Jump to content

nth-replace (mergesort's achilles heel)


wishbonesr

Recommended Posts

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.

Link to comment
Share on other sites

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)
_$ 

Link to comment
Share on other sites

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

Link to comment
Share on other sites

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))
 )
)

Link to comment
Share on other sites

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.

Link to comment
Share on other sites

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:

Link to comment
Share on other sites

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

 

Link to comment
Share on other sites

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.

Link to comment
Share on other sites

*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.

Link to comment
Share on other sites

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))

Link to comment
Share on other sites

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

Link to comment
Share on other sites

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)
_$ 

Link to comment
Share on other sites

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...

Link to comment
Share on other sites

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.

Link to comment
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
Unfortunately, your content contains terms that we do not allow. Please edit your content to remove the highlighted words below.
Reply to this topic...

×   Pasted as rich text.   Restore formatting

  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...