Hi, I just saw this:
Heap>>privateRemoveAt: index "Remove the element at the given index and make sure the sorting order is okay" | removed | removed := array at: index. array at: index put: (array at: tally). array at: tally put: nil. tally := tally - 1. index > tally ifFalse:[ "Use #downHeapSingle: since only one element has been removed" self downHeapSingle: index]. ^removed
This means that an element removal triggers a new sort phase... (even a simplified one costs) I think this could be more efficient:
Heap>>privateRemoveAt: index "Remove the element at the given index and make sure the sorting order is okay" | removed | removed := array at: index. tally := tally - 1. array replaceFrom: index to: tally with: array startingAt: index + 1. array at: tally + 1 put: nil. indexUpdateBlock ifNotNil: [ index to: tally do: [:i | self updateObjectIndex: i]]. ^removed
Did I miss a good reason justifying to re-sort ?
Nicolas
On Thu, 30 Sep 2010, Nicolas Cellier wrote:
Hi, I just saw this:
Heap>>privateRemoveAt: index "Remove the element at the given index and make sure the sorting order is okay" | removed | removed := array at: index. array at: index put: (array at: tally). array at: tally put: nil. tally := tally - 1. index > tally ifFalse:[ "Use #downHeapSingle: since only one element has been removed" self downHeapSingle: index]. ^removed
This means that an element removal triggers a new sort phase... (even a simplified one costs)
This method just restores the heap invariant, it doesn't sort the heap. It has O(log(n)) time complexity.
I think this could be more efficient:
Heap>>privateRemoveAt: index "Remove the element at the given index and make sure the sorting order is okay" | removed | removed := array at: index. tally := tally - 1. array replaceFrom: index to: tally with: array startingAt: index + 1. array at: tally + 1 put: nil. indexUpdateBlock ifNotNil: [ index to: tally do: [:i | self updateObjectIndex: i]]. ^removed
Did I miss a good reason justifying to re-sort ?
The method comment is a bit misleading because the method doesn't really sort the heap.
Levente
Nicolas
2010/9/30 Levente Uzonyi leves@elte.hu:
On Thu, 30 Sep 2010, Nicolas Cellier wrote:
Hi, I just saw this:
Heap>>privateRemoveAt: index "Remove the element at the given index and make sure the sorting order is okay" | removed | removed := array at: index. array at: index put: (array at: tally). array at: tally put: nil. tally := tally - 1. index > tally ifFalse:[ "Use #downHeapSingle: since only one element has been removed" self downHeapSingle: index]. ^removed
This means that an element removal triggers a new sort phase... (even a simplified one costs)
This method just restores the heap invariant, it doesn't sort the heap. It has O(log(n)) time complexity.
I think this could be more efficient:
Heap>>privateRemoveAt: index "Remove the element at the given index and make sure the sorting order is okay" | removed | removed := array at: index. tally := tally - 1. array replaceFrom: index to: tally with: array startingAt: index +
array at: tally + 1 put: nil. indexUpdateBlock ifNotNil: [ index to: tally do: [:i | self updateObjectIndex: i]]. ^removed
Did I miss a good reason justifying to re-sort ?
The method comment is a bit misleading because the method doesn't really sort the heap.
Levente
Ah yes, of course, my mistake... It's equivalent to a tree. I was blinded by the assumption that #do: would enumerate in sort order, which it does not (but we don't care, we won't enumerate past the #first). Hmm gonna have a class comment to document...
Nicolas
Nicolas
squeak-dev@lists.squeakfoundation.org