Re: [PATCH] Avoid `SCM_VALIDATE_LIST ()'

[Han-Wen Nienhuys]

Neil Jerram escreveu:
> 2008/9/1 Ludovic Courtès <address@hidden>:
>> Hello,
>>
>> This is a followup to this discussion:
>>
>>  http://thread.gmane.org/gmane.lisp.guile.devel/7194
>>
>> The attached patch changes several list-related functions
> 
> reverse!, memq, memv, member, filter, filter!
> SRFI-1: concatenate, concatenate!, member, remove, remove!
> 
>> so that they
>> don't validate their input with `SCM_VALIDATE_LIST ()' since it's O(n).
> 
> I'm afraid I don't get your rationale, because all these functions are
> O(n) anyway.  (For reverse*, filter* and concatenate* I believe this
> is obvious.  For mem* and remove*, they should always be O(n) in
> practice because it would be stupid to design a list structure where
> the element being looked for or removed was not equally likely to be
> anywhere along the list.)

All these functions are O(n), but by prefixing the list check
you're doubling the running time (eg. in the case of reverse!). 

If you are doing memq? for something you already know to 
somewhere in front of the list, the list? check will slow
it down much worse.

-- 
 Han-Wen Nienhuys - address@hidden - http://www.xs4all.nl/~hanwen