Re: Adding rassq-delete-all to lisp/subr.el.

[David Kastrup]

Lute Kamstra <address@hidden> writes:

> lisp/subr.el currently defines assq-delete-all.  What about providing
> rassq-delete-all as well?
>
> Lute.
>
>
> (defun rassq-delete-all (value alist)
>   "Delete from ALIST all elements whose cdr is `eq' to VALUE.
> Return the modified alist.
> Elements of ALIST that are not conses are ignored."
>   (let ((tail alist))
>     (while tail
>       (when (and (consp (car tail)) (eq (cadr tail) value))
>       (setq alist (delq (car tail) alist)))
>       (setq tail (cdr tail)))
>     alist))

That is not what the function does.  You are confusing cadr and cdar.

And I am not too fond of quadratic complexity algorithms.  It would
seem much better to write

(defun rassq-delete-all (value alist)
  "Delete from ALIST all elements whose cdr is `eq' to VALUE.
Return the modified alist.
Elements of ALIST that are not conses are ignored."
  (while (and (consp (car alist)) (eq (cdr (car alist)) value))
    (setq alist (cdr alist)))
  (prog1 alist
    (let ((tail alist))
      (while (setq tail (cdr tail))
        (if (and (consp (car tail))
                 (eq (cdr (car tail)) value))
            (setcdr alist (cdr tail))
          (setq alist tail))))))

If one takes
(defun checkit ()
  (setq x nil)
  (dotimes (i 100001) (push (cons (- i) i) x))
  (float-time
   (time-since (prog1 (current-time)
                 (dotimes (i 101)
                   (setq x (rassq-delete-all (* 100 i) x)))))))

The discrepancy seems pretty small after byte compilation, which seems
strange.

What makes a _significant_ difference is using (car (cdr...)) instead
of (cadr...): for some unfathomable reason, cadr introduces a
temporary binding to "x", and that is really expensive in the inner
loop.

-- 
David Kastrup, Kriemhildstr. 15, 44793 Bochum