Replacing an item in a list

and a new entry just for grins...
I know T.T. replace_nth

--

Let me write a function comparable with Doug's replacenth:

(defun ALE_SubstNth_NoNil (NthPos NewItm In_Lst /
InRLst LstLng OldItm)
(if (> (setq LstLng (- (length In_Lst) (1+ NthPos))) -1)
(progn
(setq OldItm (nth NthPos In_Lst) InRLst (reverse In_Lst))
(while
(/=
NthPos
(length (setq InRLst (cdr (member OldItm InRLst))))
)
)
(while
(/=
LstLng
(length (setq In_Lst (cdr (member OldItm In_Lst))))
)
)
(append (reverse InRLst) (list NewItm) In_Lst)
)
In_Lst
)
)

my results (on my laptop P266-A2k4) are:

Comando: (progn
(_> (gc)(gc)
(_> (setq i 0 Lst nil)
(_> (repeat 256 (setq Lst (cons (cons i (chr i)) Lst) i (1+ i)))
(_> (setq Lst (reverse Lst) Item (cons Pos "TEST")
((_> Pos 1
((_> )
(_> (timer '(replacenth Pos Item Lst) 10000 nil)
(_> (timer '(ALE_SubstNth_NoNil Pos Item Lst) 10000 nil)
(_> (timer '(ALE_Subst_Nth Pos Item Lst (reverse lst)) 10000 nil)
(_> )

REPLACENTH : Elapsed time for 10000 iterations: 0.41 secs.
ALE_SUBSTNTH_NONIL : Elapsed time for 10000 iterations: 1.64 secs.
ALE_SUBST_NTH : Elapsed time for 10000 iterations: 1.69 secs.

Comando: (progn
(_> (gc)(gc)
(_> (setq i 0 Lst nil)
(_> (repeat 256 (setq Lst (cons (cons i (chr i)) Lst) i (1+ i)))
(_> (setq Lst (reverse Lst) Item (cons Pos "TEST")
((_> Pos 128
((_> )
(_> (timer '(replacenth Pos Item Lst) 10000 nil)
(_> (timer '(ALE_SubstNth_NoNil Pos Item Lst) 10000 nil)
(_> (timer '(ALE_Subst_Nth Pos Item Lst (reverse lst)) 10000 nil)
(_> )

REPLACENTH : Elapsed time for 10000 iterations: 2.18 secs.
ALE_SUBSTNTH_NONIL : Elapsed time for 10000 iterations: 1.76 secs.
ALE_SUBST_NTH : Elapsed time for 10000 iterations: 1.82 secs.

Comando: (progn
(_> (gc)(gc)
(_> (setq i 0 Lst nil)
(_> (repeat 256 (setq Lst (cons (cons i (chr i)) Lst) i (1+ i)))
(_> (setq Lst (reverse Lst) Item (cons Pos "TEST")
((_> Pos 255
((_> )
(_> (timer '(replacenth Pos Item Lst) 10000 nil)
(_> (timer '(ALE_SubstNth_NoNil Pos Item Lst) 10000 nil)
(_> (timer '(ALE_Subst_Nth Pos Item Lst (reverse lst)) 10000 nil)
(_> )

REPLACENTH : Elapsed time for 10000 iterations: 4.05 secs.
ALE_SUBSTNTH_NONIL : Elapsed time for 10000 iterations: 1.94 secs.
ALE_SUBST_NTH : Elapsed time for 10000 iterations: 2.02 secs.



--

Marc'Antonio Alessi
http://xoomer.virgilio.it/alessi
(strcat "NOT a " (substr (ver) 8 4) " guru.")

--

 

If you don't mind, I would appreciate it if you refrained
from volunteering contributions here that include code
that is written, based on, or 'inspired' by myself.

 

I'm pretty sure that was pre-visual LISP, and you'll find
that while they're generally superior in terms of performance,
recursive solutions had significant limitations in the old
AutoLISP, which was not properly tail-recursive and had
a limited and fixed stack size.

Since I don't use any form of LISP for serious development
work any longer, especially when performance is even
remotely relevant, these LISP performance comparisons
we see here occasionally, seem a bit silly to me nowadays

 

....

I wrote "only for maniac"...


Cheers.

--

Marc'Antonio Alessi
http://xoomer.virgilio.it/alessi
(strcat "NOT a " (substr (ver) 8 4) " guru.")

--

 

Well Doug's code is about as neanderthal as you can get. Without testing I'll
bet that it would have been boss in 1999 and earlier, and in spite of your
Grinch attitude I sincerely wish you a healthy, happy Christmas and many
rewarding New Years to come.

My apologies. Marco. Your code is very clever. Thanks and Merry Christmas.

 

Wel're all code maniacs, its just a question of means
and limitations.

 

Thanks John,

and Merry Christmas from Italy to you and your family.

"Auguri di Buone Feste a tutti."

Ciao.


Marco

 

Marco:

I'm not sure what's happening, but my relative times for replacenth are much
lower. What's that laptop? What's your OS?

 

Hi John,
Thanks for the compliments. In general, recursive routines use
more overhead and operate slower than iterative routines. My
routine is no exception. An optimal routine would probably
do different things depending on the position of the item in the list.
and it would be iterative. I was just having fun.

In the timings mine performs best at the beginning of the list (for
obvious reasons) while Marco's performs best when the item to
be replaced has an index larger than the list. Juerg's performs
consistently independed of the position.

Of the programs posted Marco's averages fastest but if long lists
were expected regularly, a program could probably be written
to beat it. For instance, if the index is past the middle of the list,
one could work backwards. The average timing could then
be approximately the time it takes to get through one fourth the
list.


Merry Christmas.

My timings with your timer:
Pos 1
REPLACENTH : Elapsed time for 1000 iterations: 0.06 secs.
ALE_SUBST_NTH : Elapsed time for 1000 iterations: 0.22 secs.
MEEDITLIST : Elapsed time for 1000 iterations: 0.41 secs.
Pos 128
REPLACENTH : Elapsed time for 1000 iterations: 0.31 secs.
ALE_SUBST_NTH : Elapsed time for 1000 iterations: 0.23 secs.
MEEDITLIST : Elapsed time for 1000 iterations: 0.41 secs.
pos 256
REPLACENTH : Elapsed time for 1000 iterations: 0.59 secs.
ALE_SUBST_NTH : Elapsed time for 1000 iterations: 0.08 secs.
MEEDITLIST : Elapsed time for 1000 iterations: 0.41 secs.

 

But, Doug. Running most any version of R15+ on this <now> old PIII/1.2/Win2K
laptop yields faster times for yours than the others, even if the Pos is near
the length of the list. Might it be my flavor... Map/LDD?

BTW, hope you and yours have a Merry Christmas and a healthy Happy New Year to
come.

 

I'm not sure what's happening, but my relative times for replacenth are

OS: XP Pro Sp2

P266 - 512Mb Ram

A2k2 - no Express Tools, (atoms-family 1) > length = 734


--

Marc'Antonio Alessi
http://xoomer.virgilio.it/alessi
(strcat "NOT a " (substr (ver) 8 4) " guru.")

--

 

In the timings mine performs best at the beginning of the list (for

Doug,

I think that most important differences are the followings:

All the functions that use 'mapcar', 'foreach', ...:
- "scan" all the list
- each pass a new list is build

Your recursive and replace-element-in-list ('while'):
- "scan" the list only index times
- each pass a new list is build

My ALE_Subst_Nth:
- do not "scan" the list directly but let 'member' "scan" the list
- the two 'while' loops works only if in the list there are double
elements (very rare case)
- normally only three lists are build


If we wont optimize the "scan until" method for long list and
high index value this is a new approach:

(defun ALE_SubstNth_NoRmv (NthPos NewItm In_Lst / LstLng SttLst)
(cond
( (> (/ (setq LstLng (length In_Lst)) 2) NthPos)
(repeat NthPos
(setq
SttLst (cons (car In_Lst) SttLst)
In_Lst (cdr In_Lst)
)
)
(append (reverse SttLst) (cons NewItm (cdr In_Lst)))
)
( (> (1+ NthPos) LstLng) In_Lst )
( T
(setq In_Lst (reverse In_Lst))
(repeat (1- (- LstLng NthPos))
(setq
SttLst (cons (car In_Lst) SttLst)
In_Lst (cdr In_Lst)
)
)
(append (reverse (cdr In_Lst)) (cons NewItm SttLst))
)
)
)

For:
(progn
(gc)(gc)
(setq i 0 Lst nil)
(repeat 10000 (setq Lst (cons (cons i (chr i)) Lst) i (1+ i)))
(setq
Lst (reverse Lst)
Pos 10 ; see below
Item (cons Pos "TEST")
)
(timer '(replacenth Pos Item Lst) 100 nil)
(timer '(ALE_SubstNth_NoNil Pos Item Lst) 100 nil)
(timer '(ALE_SubstNth_NoRmv Pos Item Lst) 100 nil)
)

; Pos = 10
; REPLACENTH : Elapsed time for 100 iterations: 0.01 secs.
; ALE_SUBSTNTH_NONIL : Elapsed time for 100 iterations: 0.55 secs.
; ALE_SUBSTNTH_NORMV : Elapsed time for 100 iterations: 0.17 secs.

; Pos = 4999
; REPLACENTH : Elapsed time for 100 iterations: 0.74 secs.
; ALE_SUBSTNTH_NONIL : Elapsed time for 100 iterations: 0.65 secs.
; ALE_SUBSTNTH_NORMV : Elapsed time for 100 iterations: 0.82 secs.

; Pos = 8000
; REPLACENTH : Elapsed time for 100 iterations: 1.19 secs.
; ALE_SUBSTNTH_NONIL : Elapsed time for 100 iterations: 0.71 secs.
; ALE_SUBSTNTH_NORMV : Elapsed time for 100 iterations: 0.70 secs.

; Pos = 9999
; REPLACENTH : Elapsed time for 100 iterations: 1.61 secs.
; ALE_SUBSTNTH_NONIL : Elapsed time for 100 iterations: 0.83 secs.
; ALE_SUBSTNTH_NORMV : Elapsed time for 100 iterations: 0.61 secs.

--

Marc'Antonio Alessi
http://xoomer.virgilio.it/alessi
(strcat "NOT a " (substr (ver) 8 4) " guru.")

--

 

If we want optimize the recursive method for long list and
high index value this is a new approach:

(defun ALE_SubstNth_Rec (NthPos NewItm In_Lst)
(if In_Lst
(if (> (/ (setq LstLng (length In_Lst)) 2) NthPos)
(ALE_SubstNth_Rec_Aux NthPos NewItm In_Lst)
(if (>= LstLng (1- NthPos))
(reverse
(ALE_SubstNth_Rec_Aux
(- LstLng NthPos -1) NewItm (reverse In_Lst)
)
)
In_Lst
)
)
)
)

(defun ALE_SubstNth_Rec_Aux (NthPos NewItm In_Lst)
(if (zerop NthPos)
(cons NewItm (cdr In_Lst))
(cons
(car In_Lst)
(ALE_SubstNth_Rec_Aux (1- NthPos) NewItm (cdr In_Lst))
)
)
)

;For:
(progn
(gc)(gc)
(setq i 0 Lst nil Ntimes 200)
(repeat Ntimes (setq Lst (cons (cons i (chr i)) Lst) i (1+ i)))
(setq Lst (reverse Lst) Pos Ntimes Item (cons Pos "TEST"))
(repeat 9
(princ ";Pos: ") (princ Pos)
(timer '(replacenth Pos Item Lst) 10000 nil)
(timer '(ALE_SubstNth_NoNil Pos Item Lst) 10000 nil)
(timer '(ALE_SubstNth_Rec Pos Item Lst) 10000 nil)
(princ "\n")
(setq Pos (- Pos (/ Ntimes 8)))
)
)

;Pos: 200
;REPLACENTH : Elapsed time for 10000 iterations: 3.33 secs.
;ALE_SUBSTNTH_NONIL : Elapsed time for 10000 iterations: 0.61 secs.
;ALE_SUBSTNTH_REC : Elapsed time for 10000 iterations: 0.92 secs.
;Pos: 175
;REPLACENTH : Elapsed time for 10000 iterations: 3.01 secs.
;ALE_SUBSTNTH_NONIL : Elapsed time for 10000 iterations: 1.61 secs.
;ALE_SUBSTNTH_REC : Elapsed time for 10000 iterations: 1.27 secs.
;Pos: 150
;REPLACENTH : Elapsed time for 10000 iterations: 2.67 secs.
;ALE_SUBSTNTH_NONIL : Elapsed time for 10000 iterations: 1.5 secs.
;ALE_SUBSTNTH_REC : Elapsed time for 10000 iterations: 1.61 secs.
;Pos: 125
;REPLACENTH : Elapsed time for 10000 iterations: 2.3 secs.
;ALE_SUBSTNTH_NONIL : Elapsed time for 10000 iterations: 1.47 secs.
;ALE_SUBSTNTH_REC : Elapsed time for 10000 iterations: 1.97 secs.
;Pos: 100
;REPLACENTH : Elapsed time for 10000 iterations: 1.95 secs.
;ALE_SUBSTNTH_NONIL : Elapsed time for 10000 iterations: 1.45 secs.
;ALE_SUBSTNTH_REC : Elapsed time for 10000 iterations: 2.29 secs.
;Pos: 75
;REPLACENTH : Elapsed time for 10000 iterations: 1.61 secs.
;ALE_SUBSTNTH_NONIL : Elapsed time for 10000 iterations: 1.41 secs.
;ALE_SUBSTNTH_REC : Elapsed time for 10000 iterations: 1.6 secs.
;Pos: 50
;REPLACENTH : Elapsed time for 10000 iterations: 1.28 secs.
;ALE_SUBSTNTH_NONIL : Elapsed time for 10000 iterations: 1.36 secs.
;ALE_SUBSTNTH_REC : Elapsed time for 10000 iterations: 1.27 secs.
;Pos: 25
;REPLACENTH : Elapsed time for 10000 iterations: 0.91 secs.
;ALE_SUBSTNTH_NONIL : Elapsed time for 10000 iterations: 1.35 secs.
;ALE_SUBSTNTH_REC : Elapsed time for 10000 iterations: 0.93 secs.
;Pos: 0
;REPLACENTH : Elapsed time for 10000 iterations: 0.56 secs.
;ALE_SUBSTNTH_NONIL : Elapsed time for 10000 iterations: 1.31 secs.
;ALE_SUBSTNTH_REC : Elapsed time for 10000 iterations: 0.59 secs.



;For:
(progn
(gc)(gc)
(setq i 0 Lst nil Ntimes 10000)
(repeat Ntimes (setq Lst (cons (cons i (chr i)) Lst) i (1+ i)))
(setq Lst (reverse Lst) Pos Ntimes Item (cons Pos "TEST"))
(repeat 9
(princ ";Pos: ") (princ Pos)
(timer '(replacenth Pos Item Lst) 100 nil)
(timer '(ALE_SubstNth_NoNil Pos Item Lst) 100 nil)
(timer '(ALE_SubstNth_Rec Pos Item Lst) 100 nil)
(princ "\n")
(setq Pos (- Pos (/ Ntimes 8)))
)
)

;Pos: 10000
;REPLACENTH : Elapsed time for 100 iterations: 1.47 secs.
;ALE_SUBSTNTH_NONIL : Elapsed time for 100 iterations: 0.01 secs.
;ALE_SUBSTNTH_REC : Elapsed time for 100 iterations: 0.34 secs.
;Pos: 8750
;REPLACENTH : Elapsed time for 100 iterations: 1.29 secs.
;ALE_SUBSTNTH_NONIL : Elapsed time for 100 iterations: 0.72 secs.
;ALE_SUBSTNTH_REC : Elapsed time for 100 iterations: 0.51 secs.
;Pos: 7500
;REPLACENTH : Elapsed time for 100 iterations: 1.12 secs.
;ALE_SUBSTNTH_NONIL : Elapsed time for 100 iterations: 0.66 secs.
;ALE_SUBSTNTH_REC : Elapsed time for 100 iterations: 0.7 secs.
;Pos: 6250
;REPLACENTH : Elapsed time for 100 iterations: 0.93 secs.
;ALE_SUBSTNTH_NONIL : Elapsed time for 100 iterations: 0.65 secs.
;ALE_SUBSTNTH_REC : Elapsed time for 100 iterations: 0.87 secs.
;Pos: 5000
;REPLACENTH : Elapsed time for 100 iterations: 0.75 secs.
;ALE_SUBSTNTH_NONIL : Elapsed time for 100 iterations: 0.63 secs.
;ALE_SUBSTNTH_REC : Elapsed time for 100 iterations: 1.08 secs.
;Pos: 3750
;REPLACENTH : Elapsed time for 100 iterations: 0.55 secs.
;ALE_SUBSTNTH_NONIL : Elapsed time for 100 iterations: 0.6 secs.
;ALE_SUBSTNTH_REC : Elapsed time for 100 iterations: 0.56 secs.
;Pos: 2500
;REPLACENTH : Elapsed time for 100 iterations: 0.36 secs.
;ALE_SUBSTNTH_NONIL : Elapsed time for 100 iterations: 0.58 secs.
;ALE_SUBSTNTH_REC : Elapsed time for 100 iterations: 0.38 secs.
;Pos: 1250
;REPLACENTH : Elapsed time for 100 iterations: 0.17 secs.
;ALE_SUBSTNTH_NONIL : Elapsed time for 100 iterations: 0.55 secs.
;ALE_SUBSTNTH_REC : Elapsed time for 100 iterations: 0.2 secs.
;Pos: 0
;REPLACENTH : Elapsed time for 100 iterations: 0 secs.
;ALE_SUBSTNTH_NONIL : Elapsed time for 100 iterations: 0.54 secs.
;ALE_SUBSTNTH_REC : Elapsed time for 100 iterations: 0.01 secs.



--

Marc'Antonio Alessi
http://xoomer.virgilio.it/alessi
(strcat "NOT a " (substr (ver) 8 4) " guru.")

--

 

For comparision, this is how it would be done in Common Lisp:

(setf (nth 3 lst) "6")

--

 

Thanks Martti,

A very sensible approach.

Regards,
Doug

 

That's one way, but in Auto/Visual LISP, LISTS are often used
for lack of any other built-in way to do indexed access to data
(e.g. vectors and matrices).

So, while (setf) would work if you were using lists to store data,
Common LISP's native support for indexed data access (vectors,
arrays, etc.), might be more well suited.

Interestingly, I've not seen anyone put forth a solution that uses
Windows/OLE SafeArrays, which could easily be faster than any
of these depending on the applicaiton.

 

Tony,

In theory, it could be faster. It certainly would be simple with VBA.
But converting the data back and forth from safearrays would seem
likely to kill any gains in efficiency. Why don't you post one? I
would enjoy seeing one. Including the conversion times and
depending on the size of the lists and the index position, I would
imagine it might be 10-20 times slower.

This is my poor stab at it:

(defun replacesa (ndx item lst / sa)
(if (<= 0 ndx (length lst))
(progn
(setq sa (vlax-make-safearray vlax-vbvariant (cons 0 (1-(length lst)))))
(vlax-safearray-fill sa lst)
(vlax-safearray-put-element sa ndx item)
(mapcar 'variant-value (vlax-safearray->list sa)))
lst))


Regards,
Doug

 

Convert the data back and forth ?

Depends on what purpose the list whose elements are
being replaced is being used for to start with.

E.g., is it being used as an 'array' of sorts? If so, then
one may be able to ditch the entire concept of using
lists and just use safearrays instead, and there's no back
and forth.

 

Doug,

I tried your replacesa but there is a problem
with some kind of lists (see below).

Cheers.

--

Marc'Antonio Alessi
http://xoomer.virgilio.it/alessi
(strcat "NOT a " (substr (ver) 8 4) " guru.")

--

--------------------------------------------------------------
Comando: (setq lst '("A" "B" "C" "D"))
("A" "B" "C" "D")

Comando: (replacesa 2 9999 Lst)
("A" "B" 9999 "D")

Comando: (setq lst '(0 1 2 3 ))
(0 1 2 3)

Comando: (replacesa 2 9999 Lst)
(0 1 9999 3)


Comando: (setq lst '((0 . "A") (1 . "B") (2 . "C") (3 . "D")))
((0 . "A") (1 . "B") (2 . "C") (3 . "D"))

Comando: (replacesa 2 9999 Lst)
Traccia all'indietro:
[0.56] (VL-BT)
[1.52] (ERRDUMP "vlax-safearray-fill non riuscito. Elenco di
inizializzazione
non valido. #<safearray...> ((0 . \"A\") (1 . \"B\") (2 . \"C\") (3 .
\"D\"))")
[2.47] (_call-err-hook #<SUBR @0334f3ac ERRDUMP> "vlax-safearray-fill non
riuscito. Elenco di inizializzazione non valido. #<safearray...> ((0 .
\"A\")
(1 . \"B\") (2 . \"C\") (3 . \"D\"))")
[3.41] (sys-error "vlax-safearray-fill non riuscito. Elenco di
inizializzazione
non valido. #<safearray...> ((0 . \"A\") (1 . \"B\") (2 . \"C\") (3 .
\"D\"))")
:ERROR-BREAK.36 nil
[4.33] (#<SUBR @02a5c03c safearray-fill> #<safearray...> ((0 . "A") (1 .
"B")
(2 . "C") (3 . "D")))
[5.28] (vlax-safearray-fill #<safearray...> ((0 . "A") (1 . "B") (2 . "C")
(3 .
"D")))
[6.22] (REPLACESA 2 9999 ((0 . "A") (1 . "B") (2 . "C") (3 . "D")))
[7.15] (#<SUBR @036f3a78 -rts_top->)
[8.12] (#<SUBR @02b32334 veval-str-body> "(replacesa 2 9999 Lst)" T #<FILE
internal>)
:CALLBACK-ENTRY.6 CALLBACK-ENTRY)
:ARQ-SUBR-CALLBACK.3 (nil 0)

 

Yes, then it gets really complicated:

(setf (aref array 2) "6")

Interesting idea, I'll have to try this next time when I start cursing
VisualLisp's lack of arrays...

--