From: Ole Arndt <ole@su...>  20090404 00:15:11

Hello, 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). 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 rembered that the same code went into sbcl. I looked, and voila, the same behavior. I haven't investigated later but here is a test case: (let* ((size 100) (heap (makearray size :adjustable t :fillpointer 0)) (unsorted (loop for i below size collect (random size))) (sorted (sort (copylist unsorted) #'>=)) heapsorted) (map nil #'(lambda (val) (sbimpl::heapinsert heap val)) unsorted) (setf heapsorted (loop for i below size collect (sbimpl::heapextractmaximum heap))) (values (equal sorted heapsorted) sorted heapsorted)) NIL (99 99 98 98 98 97 96 95 92 92 91 91 88 88 86 86 86 85 84 84 84 84 83 82 80 77 74 74 73 69 69 67 67 66 65 64 62 59 59 57 57 56 56 55 55 53 51 51 51 50 48 47 47 46 45 44 43 43 42 42 41 41 39 33 33 33 31 30 27 26 26 26 25 25 24 23 23 23 23 23 22 22 22 21 21 20 19 18 16 14 11 7 7 4 4 3 2 1 1 1) (99 99 98 98 98 97 96 95 92 92 91 88 88 86 86 86 85 84 84 84 83 82 80 77 91 74 74 73 69 67 67 66 65 64 84 69 62 59 59 57 57 56 56 55 55 53 51 51 51 50 48 47 47 46 45 44 43 43 42 42 41 41 39 33 33 33 31 30 27 26 26 26 25 25 24 23 23 23 23 23 22 22 22 21 21 20 19 18 16 14 11 7 7 4 4 3 2 1 1 1) Ole  Ole Arndt http://www.sugarshark.com 
From: Ole Arndt <ole@su...>  20090405 23:06:38

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/buffercontent5724j4r  /usr/lib64/sbcl/src/code/timer.lisp 20090216 23:16:20.000000000 +0100 +++ /tmp/buffercontent5724j4r 20090406 00:42:20.471244961 +0200 @@ 16,7 +16,7 @@ (declaim (inline heapparent heapleft heapright)) (defun heapparent (i)  (ash i 1)) + (ash (1 i) 1)) (defun heapleft (i) (1+ (ash i 1))) Ole  Ole Arndt http://www.sugarshark.com 
From: Gábor Melis <mega@re...>  20090406 08:54:33

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/buffercontent5724j4r  > /usr/lib64/sbcl/src/code/timer.lisp 20090216 23:16:20.000000000 > +0100 +++ /tmp/buffercontent5724j4r 20090406 00:42:20.471244961 > +0200 @@ 16,7 +16,7 @@ > (declaim (inline heapparent heapleft heapright)) > > (defun heapparent (i) >  (ash i 1)) > + (ash (1 i) 1)) > > (defun heapleft (i) > (1+ (ash i 1))) > > > Ole Thanks for the patch, committed as 1.0.27.2. 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 heapleft, heapright functions but forgot to bring heapparent in sync with them. What prompted the [half] fix is that in timer 0.4.0 (heapleft 0) is 0. Cheers, Gabor 