On Lunes 06 Abril 2009, Ole Arndt wrote:
> Ole Arndt <ole@...> writes:
> > I have been playing around with graph search algorithms tonight,
> > comparing my fibonnaci heap implementation against a binary heap
> > implementation I lifted from Zach Beanes timer.lisp (who apparently
> > in turn lifted it from the AIMA source code).
> Zach wrote me that he actually wrote it all by himself, after CLR's
> description. The AIMA code stems from the same source, as one can see
> in the comments. I didn't realize this and jumped to wrong
> conclusions. I want to apologize for publicly making this assertion.
> > With a heap size below 20, everything seems OK, with a bigger
> > number of items in the heap I started to get errors. With more than
> > 100 items in the heap, the algorithm fails every time.
> > I remembered that the same code went into sbcl. I looked, and
> > voila, the same behavior.
> Here comes the trivial fix:
> diff -u /usr/lib64/sbcl/src/code/timer.lisp
> /tmp/buffer-content-5724j4r ---
> /usr/lib64/sbcl/src/code/timer.lisp 2009-02-16 23:16:20.000000000
> +0100 +++ /tmp/buffer-content-5724j4r 2009-04-06 00:42:20.471244961
> +0200 @@ -16,7 +16,7 @@
> (declaim (inline heap-parent heap-left heap-right))
> (defun heap-parent (i)
> - (ash i -1))
> + (ash (1- i) -1))
> (defun heap-left (i)
> (1+ (ash i 1)))
Thanks for the patch, committed as 188.8.131.52.
However, the above test does not fail for me on timer 0.4.0 that went
into sbcl. That's because at the time of lifting it I changed the
heap-left, heap-right functions but forgot to bring heap-parent in sync
with them. What prompted the [half] fix is that in timer 0.4.0
(heap-left 0) is 0.