Re: delete command weirdness

Barry Margolin <barmar@[EMAIL PROTECTED]
> writes:

> In article <7cod79135p.fsf@[EMAIL PROTECTED]
>,
>  pjb@[EMAIL PROTECTED]
 (Pascal J. Bourguignon) wrote:
>
>> Mark Wooding <mdw@[EMAIL PROTECTED]
> writes:
>> > Unfortunately there's no part of a cons cell to hack that will make
it
>> > look like NIL. 
>> 
>> (defun make-it-look-like-nil (cons) 
>>     (rplaca cons nil)
>>     (rplacd cons nil)
>>     cons)
>> 
>> (let ((cons (cons 1 2)))
>>    (print (and (eq (car 'nil) (car cons))
>>                (eq (cdr 'nil) (cdr cons))))
>>    (make-it-look-like-nil cons)
>>    (print (and (eq (car 'nil) (car cons))
>>                (eq (cdr 'nil) (cdr cons)))))
>> 
>> prints:
>> 
>> NIL 
>> T 
>> 
>> 
>> Therefore:
>> 
>> (defun look-like-nil-p (object)
>>    (ignore-errors   
>>       (and (eq (car 'nil) (car object))
>>            (eq (cdr 'nil) (cdr object)))))
>> 
>> ;-)
>
> Question: How many legs does a person have, if you call an arm a leg?
> Answer: 2 -- calling an arm a leg doesn't make it a leg.

Yes, that's the difference between making a cons cell look like nil,
and making a cons cell become the symbol nil.

>> > As others have mentioned, the purpose of DELETE is to be fast, not to
>> > mutate your list in some carefully described way.  
>> 
>> I don't think that "being fast" is any criterion for DELETE.  It may
>> help to remeber that DELETE works also on vectors (including strings).
>> 
>> In anycase, it will always be O(length(seq)) in time.  What we can do
>> is to make it O(1) in _space_ vs. O(length(seq)) for REMOVE.
>
> REMOVE on a vector has to copy the entire vector (except the removed 
> elements).  DELETE only has to copy starting from the first match.  So 
> while they're both O(length(vector)), DELETE will do fewer copies unless

> you're deleting the first element.  Also, since DELETE is simply 
> ****fting elements within the same array, it should have excellent 
> locality, hence fewer cache misses than REMOVE, which must copy between 
> arrays that are likely to be far apart in memory.
>
> An interesting point about REMOVE on a list is that the result is 
> permitted to share the unmodified tail (i.e. everything after the last 
> match) with the original.  But in order to do this, I think you need to 
> make two p***** -- first you have to search for the last match, then you

> have to copy everything (except the matching elements) leading up to it.
 
> Still O(n), but the coefficient is doubled -- O() notation doesn't tell 
> all.

True, the constants are usually what matter.

-- 
__Pascal Bourguignon__