[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

> 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

Attachment: pgpx5fSNV7amx.pgp
Description: PGP signature

reply via email to

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