[squeak-dev] Why do Heap re-sort when it removes elements ?
Nicolas Cellier
nicolas.cellier.aka.nice at gmail.com
Thu Sep 30 12:16:34 UTC 2010
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
More information about the Squeak-dev
mailing list
|