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

[Pascal J. Bourguignon]

Emanuel Berg <embe8573@student.uu.se> writes:

> "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.

Depends on what end of the chain you hold.

To make it easier, imagine this bike chain, but 10 km long, obviously,
you have one end in hand, and the other is stored three workshop beyond.
To find this other end, you have to go thru each link.  O(n).


There is no such list of complexities because:

1- it is obvious. When you've studied lisp, you have implemented most of
   them.

2- in most cases, the algorithms are not specified, so an implementation
   would be free to provide something more efficient, if it was possible.

3- there is some expectations on the part of CL users, and sometimes an
   implementation may use a worse algorithm. Then its users will
   complain and a better algorithm is implemented.  So mostly all
   implementations have similar time and space complexities.

Nonetheless, if you find it would be useful to have such a list, you can
establish it.

There are 636 functions in CL. 

If you research the best algorithms for each, noting the time and space
complexities, and finding what complexities and (approximate) actual
factors each implementation provide, for 2 functions each day, you will
be done in less than a year.


> 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...

Absolutely.

Also, notice that doing that, or consing onto the beginning of the list
and calling nreverse when you're done are equivalent time-complexity
wise.  There may be some difference re: cache in actual contemporaneous
computers but it can be seen only on very long lists.


-- 
__Pascal Bourguignon__                 http://www.informatimago.com/
“The factory of the future will have only two employees, a man and a
dog. The man will be there to feed the dog. The dog will be there to
keep the man from touching the equipment.” -- Carl Bass CEO Autodesk