[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Adding rassq-delete-all to lisp/subr.el.
From: |
Lute Kamstra |
Subject: |
Re: Adding rassq-delete-all to lisp/subr.el. |
Date: |
Thu, 21 Apr 2005 19:33:21 +0200 |
User-agent: |
Gnus/5.11 (Gnus v5.11) Emacs/22.0.50 (gnu/linux) |
David Kastrup <address@hidden> writes:
> Lute Kamstra <address@hidden> writes:
>
>> David Kastrup <address@hidden> 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.