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:
>
>> 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.
>
> This only uses `cons', `cdr', and `nreverse', so it is
> linear, right? ("linear" only from going thru the
> input list.)

Being O(n) doesn't come automatically by using only cons cdr and
nreverse.  It depends on the structure of the algorithm!
http://discrete.gr/complexity/

> (require 'cl)
>
> (defun plist-drop-nil-props (l)
>   (let ((new)
>         (nil-prop)
>         (prop) )
>     (cl-loop for x in l

Here you are doing the loop body once for each element in the list l.
Therefore you will be repeating the loop body (length l) times.
The complexity of your algorithm will therefore be:

    O( (* (length l) (complexity-of loop-body) )

>              do (if (setq prop (not prop))
>                     (if x
                        (setq new (cons x new))
>                       (setq nil-prop t))

NEVER put the then on the same line as the test!

>                   (if x
>                       (if nil-prop
                          (setq nil-prop nil)
>                         (setq new (cons x new))   )
>                     (setq new (cdr new) ))))

Fortunately, your loop body contains a fixed number of instruction, that
doesn't depend on the length of the list or on any other value that
depend on the length of the list.  Therefore it is O(1)
and O( (* (length l) O(1)) ) = O(length l)

>     (nreverse new) ))

(length new) is also bound by (length l), so the complexity of
(nreverse new) is O(length l).

O(length l) + O(length l) = O(length l).

> constant: cons, cdr, nreverse

No. your call to nreverse is O(length l).


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