emacs-devel
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Help with recursive destructive function


From: Stefan Monnier
Subject: Re: Help with recursive destructive function
Date: Fri, 04 May 2018 21:18:56 -0400
User-agent: Gnus/5.13 (Gnus v5.13) Emacs/27.0.50 (gnu/linux)

>   (cond ((listp (cdr thing))
>        (dotimes (i (length thing))

You don't want that:

>          (cond ((stringp (nth i thing))
>                 (setf (nth i thing) (upcase (nth i thing))))
>                ((listp (nth i thing))
>                 (walk (nth i thing))))))

Each `nth i` will take time O(i) so you have an O(n^2) complexity right there.

You want to do something more like

    (let ((xs thing))
      (while (consp xs)
        (let ((x (car xs)))
          (cond
           ((stringp x) (setf (car xs) (upcase x)))
           ((listp x) (walk x)))
          (setq xs (cdr xs)))))


-- Stefan




reply via email to

[Prev in Thread] Current Thread [Next in Thread]