On Sat, May 27, 2006 at 11:34:25AM -0400, Stefan Monnier wrote: > Your code has some problem w.r.t efficiency. The heap data-structure is > interesting for its complexity properties (e.g. heap-delete-root should be > O(log N)), but your code doesn't enjoy those properties:
Hmmm...yes, you're absolutely right, of course. I wrote heap.el quite a while ago when I was still more familiar with c than lisp, and didn't understand the complexity cost of vconcat in a functional language. > This is O(N) as well. > I.e. you shouldn't resize your array all the time. You should allow it to > be larger than the number of elements it holds, and only resize it every > once in a while (by reducing/increasing its size by a constant factor). To be honest, I haven't looked at the core of the code in heap.el in ages. I thought it was doing that already! Shouldn't be too difficult to fix. Toby Cubitt -- PhD Student Quantum Information Theory group Max Planck Institute for Quantum Optics Garching, Germany email: [EMAIL PROTECTED] web: www.dr-qubit.org
pgpG8Qv7nnfJu.pgp
Description: PGP signature
_______________________________________________ gnu-emacs-sources mailing list [email protected] http://lists.gnu.org/mailman/listinfo/gnu-emacs-sources
