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

[Lute Kamstra]

David Kastrup <address@hidden> writes:

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

Yup, I noticed.

> And I am not too fond of quadratic complexity algorithms.

Me neither, but I was lazy and adapted assq-delete-all.

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

Nice.  I find this rewrite a bit easier to understand, though:

(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)))
  (let ((tail alist) tail-cdr)
    (while (setq tail-cdr (cdr tail))
      (if (and (consp (car tail-cdr))
               (eq (cdr (car tail-cdr)) value))
          (setcdr tail (cdr tail-cdr))
        (setq tail tail-cdr))))
  alist)

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

delq in defined in C and it's only called 101 times.

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

Strange, (cadr ...) is just a defsubst for (car (cdr ...)).  So
compiled it should make no difference.

Lute.