Re: How to delete all nil properties from a plist?

[Emanuel Berg <embe8573@student.uu.se>]

"Pascal J. Bourguignon" <pjb@informatimago.com>
writes:

>>> This is horrible. Again, you can't prevent
>>> yourself writing O(n²) code when O(n) would
>>> do perfectly.
>>
>> Is it `append' or `butlast' that is linear as well?
>
> Both.

OK!

It would be useful to have a list with the time
complexities of all the list operators. Because here
(with `append' and `butlast') it isn't clear from what
those functions do that they are linear. On the
contrary: if we think of an open bike chain in
a workshop, then to put another link at either end
isn't linear, it is O(1), as is removing a link from
either end.

So I think my algorithm is actually linear (but not
the implementation you saw) if only I replaced those
functions with manually re-linking the items (because
if the list is built manually, the last item could be
stored, and then linked further to in constant time
which would imply appending to the list as that item
is already part of the list, the last part) - I don't
know how to do that right now, perhaps I'll be back if
I don't find something else to do...

-- 
underground experts united
http://user.it.uu.se/~embe8573