[AUCTeX-devel] Re: [AUCTeX-diffs] Changes to reftex/lisp/reftex-base.el, v

[David Kastrup]

Ralf Angeli <address@hidden> writes:

> CVSROOT:      /sources/auctex
> Module name:  reftex
> Changes by:   Ralf Angeli <angeli>    08/06/07 11:17:14
>
> +(defun reftex-remove-if (predicate list)
> +  "Nondestructively remove all items from LIST which satisfy PREDICATE."
> +  (let (result)
> +    (dolist (elt list)
> +      (unless (funcall predicate elt)
> +     (add-to-list 'result elt t)))
> +    result))
> +

No, that's bad.  Since it also uniquifies the list.  add-to-list is an
O(n) operation, so this becomes O(n^2).

Try rather
(let (result)
  (dolist (elt list (nreverse result))
    (unless (funcall predicate elt)
      (push elt result))))

This is O(n).

-- 
David Kastrup, Kriemhildstr. 15, 44793 Bochum