[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: heap.el -- new release
From: |
Toby Cubitt |
Subject: |
Re: heap.el -- new release |
Date: |
Sat, 27 May 2006 19:04:32 +0200 |
User-agent: |
Mutt/1.5.11 |
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: address@hidden
web: www.dr-qubit.org
pgpx5fSNV7amx.pgp
Description: PGP signature