David Kastrup <[EMAIL PROTECTED]> writes:
> Lute Kamstra <[EMAIL PROTECTED]> writes:
>
>> David Kastrup <[EMAIL PROTECTED]> 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.
_______________________________________________
Emacs-devel mailing list
[email protected]
http://lists.gnu.org/mailman/listinfo/emacs-devel
