[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: cl.el sort* efficiency

From: Stefan Monnier
Subject: Re: cl.el sort* efficiency
Date: Mon, 25 Dec 2006 18:10:33 -0500
User-agent: Gnus/5.11 (Gnus v5.11) Emacs/22.0.91 (gnu/linux)

> I don't know how representative I am, but it's pretty obvious to me that
> adding something like :key to sort might call the given function
> multiple times.  Certainly the alternative of allocating storage to keep
> around all retrieved key values is pretty heavyweight and in many cases
> not an optimization at all, so it's not something I would expect an
> implementation to do.

Actually, I do believe that when I was a CL user I expected that the sort
function would call the :key function only O(n) times rather than O(n log n)
times.  If I didn't want the allocation of an aux table I used something
like car-less-then-car for the comparison function.


reply via email to

[Prev in Thread] Current Thread [Next in Thread]