nth-replace (mergesort's achilles heel)

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

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

[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

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

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

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

[LibertyOne]

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

 

(subst ITEM (nth INDEX LST) LST)

[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

 

[BlackBox]

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

[alanjt]

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

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

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

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

[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?

 

[LibertyOne]

 

ok - no answer is also an answer...

[BlackBox]

ok - no answer is also an answer...

 

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 :

 

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

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

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

[Lee Mac]

Thanks for the nod Renderman, appreciated

 

FYI, here is the related function on my site:

 

http://lee-mac.com/substn.html