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

[Lute Kamstra <Lute.Kamstra.lists@xs4all.nl>]

David Kastrup <dak@gnu.org> writes:

> Lute Kamstra <Lute.Kamstra.lists@xs4all.nl> writes:
>
>> David Kastrup <dak@gnu.org> writes:
>>
>>> And I am not too fond of quadratic complexity algorithms.
>>
>> Me neither, but I was lazy and adapted assq-delete-all.
>>
>>> 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.
>
> Ah, right.  If we removed all elements piecemeal, this would be
> different.

No, that would still run in linear time.  To get quadratic behavior,
you can do this:

(defun checkit ()
  (setq x nil)
  (dotimes (i 100000)
    (push '(a . a) x)
    (push '(b . b) x))
  (float-time
   (time-since
    (prog1 (current-time)
      (rassq-delete-all 'a x)))))

Lute.