[Pkg] The Trunk: Collections-ul.458.mcz

commits at source.squeak.org commits at source.squeak.org
Sat Sep 10 17:46:40 UTC 2011


Levente Uzonyi uploaded a new version of Collections to project The Trunk:
http://source.squeak.org/trunk/Collections-ul.458.mcz

==================== Summary ====================

Name: Collections-ul.458
Author: ul
Time: 10 September 2011, 7:31:57.991 pm
UUID: 9cba8397-d730-d94a-9805-193df105f29b
Ancestors: Collections-ul.457

Inlined and enhanced SortedCollection's quicksort implementation #sort:to: and moved it to ArrayedCollection as #quickSortFrom:to:by:. It beats our merge sort implementation (by 25-30%) if comparision is cheap enough. Even though methods are inlined by hand, the restructured code is more readable and easier to understand than the previous version. A wide enough browser window is suggested for reading it.

=============== Diff against Collections-ul.457 ===============

Item was added:
+ ----- Method: ArrayedCollection>>quickSortFrom:to:by: (in category 'sorting') -----
+ quickSortFrom: from to: to by: sortBlock
+ 	"Sort elements i through j of self to be nondescending according to sortBlock using an in-place quicksort with simple median-of-three partitioning with guaranteed O(log(n)) space usage."
+ 
+ 	| i j |
+ 	i := from.
+ 	j := to.
+ 	[
+ 		| k l dij temp ij di dj n |
+ 		"The prefix d means the data at that index."
+ 		"Sort di,dj."
+ 		di := self at: i.
+ 		dj := self at: j.
+ 		(sortBlock ifNil: [ di <= dj ] ifNotNil: [ sortBlock value: di value: dj ]) ifFalse: [
+ 			temp := self at: i. self at: i put: (self at: j); at: j put: temp.
+ 			temp := di. di := dj. dj := temp ].
+ 		(n := j + 1  - i) <= 2 ifTrue: [ ^self ].
+ 		"More than two elements."
+ 		ij := (i + j) // 2.  "ij is the midpoint of i and j."
+ 		dij := self at: ij.  "Sort di,dij,dj.  Make dij be their median."
+ 		(sortBlock ifNil: [ di <= dij ] ifNotNil: [ sortBlock value: di value: dij ])
+ 			ifTrue: [
+ 				(sortBlock ifNil: [ dij <= dj ] ifNotNil: [ sortBlock value: dij value: dj ]) ifFalse: [
+ 					temp := self at: j. self at: j put: (self at: ij); at: ij put: temp.
+ 					dij := dj ] ]
+ 			ifFalse: [
+ 				temp := self at: i. self at: i put: (self at: ij); at: ij put: temp.
+ 				dij := di ].
+ 		n = 3 ifTrue: [ ^self ].
+ 		"More than three elements."
+ 		"Find k>i and l<j such that dk,dij,dl are in reverse order.
+ 		Swap k and l.  Repeat this procedure until k and l pass each other."
+ 		k := i.
+ 		l := j.
+ 		[
+ 			[ k <= (l := l - 1) and: [ 
+ 				sortBlock ifNil: [ dij <= (self at: l) ] ifNotNil: [ sortBlock value: dij value: (self at: l) ] ] ] whileTrue.  "i.e. while dl succeeds dij"
+ 			[ (k := k + 1) <= l and: [
+ 				sortBlock ifNil: [ (self at: k) <= dij ] ifNotNil: [ sortBlock value: (self at: k) value: dij ] ] ] whileTrue.  "i.e. while dij succeeds dk"
+ 			k <= l ] whileTrue: [ temp := self at: k. self at: k put: (self at: l); at: l put: temp. ].
+ 		"Now l<k (either 1 or 2 less), and di through dl are all less than or equal to dk through dj. Sort the larger segment in this method and call another quicksort for the smaller segment. This ensures O(log(n)) space usage."
+ 		i < l 
+ 			ifFalse: [
+ 				k < j
+ 					ifFalse: [ ^self ]
+ 					ifTrue: [ i := k ] ]
+ 			ifTrue: [
+ 				k < j
+ 					ifFalse: [ j := l ]
+ 					ifTrue: [
+ 						l - i <  (j - k)
+ 							ifTrue: [ 
+ 								self quickSortFrom: i to: l by: sortBlock.
+ 								i := k ]
+ 							ifFalse: [
+ 								self quickSortFrom: k to: j by: sortBlock.
+ 								j := l ] ] ].
+ 		i < j ] whileTrue!

Item was changed:
  ----- Method: SortedCollection>>reSort (in category 'private') -----
  reSort
+ 
+ 	firstIndex < lastIndex ifTrue: [ 
+ 		array quickSortFrom: firstIndex to: lastIndex by: sortBlock ]!
- 	self sort: firstIndex to: lastIndex!

Item was removed:
- ----- Method: SortedCollection>>sort:to: (in category 'private') -----
- sort: i to: j 
- 	"Sort elements i through j of self to be nondescending according to
- 	sortBlock."
- 
- 	| di dij dj tt ij k l n |
- 	"The prefix d means the data at that index."
- 	(n := j + 1  - i) <= 1 ifTrue: [^self].	"Nothing to sort." 
- 	 "Sort di,dj."
- 	di := array at: i.
- 	dj := array at: j.
- 	(self should: di precede: dj)
- 		ifFalse: 
- 			[array swap: i with: j.
- 			 tt := di.
- 			 di := dj.
- 			 dj := tt].
- 	n > 2
- 		ifTrue:  "More than two elements."
- 			[ij := (i + j) // 2.  "ij is the midpoint of i and j."
- 			 dij := array at: ij.  "Sort di,dij,dj.  Make dij be their median."
- 			 (self should: di precede: dij)
- 			   ifTrue: 
- 				[(self should: dij precede: dj)
- 				  ifFalse: 
- 					[array swap: j with: ij.
- 					 dij := dj]]
- 			   ifFalse:
- 				[array swap: i with: ij.
- 				 dij := di].
- 			n > 3
- 			  ifTrue:  "More than three elements."
- 				["Find k>i and l<j such that dk,dij,dl are in reverse order.
- 				Swap k and l.  Repeat this procedure until k and l pass each other."
- 				 k := i.
- 				 l := j.
- 				 [[l := l - 1.  k <= l and: [self should: dij precede: (array at: l)]]
- 				   whileTrue.  "i.e. while dl succeeds dij"
- 				  [k := k + 1.  k <= l and: [self should: (array at: k) precede: dij]]
- 				   whileTrue.  "i.e. while dij succeeds dk"
- 				  k <= l]
- 				   whileTrue:
- 					[array swap: k with: l]. 
- 	"Now l<k (either 1 or 2 less), and di through dl are all less than or equal to dk
- 	through dj.  Sort those two segments."
- 				self sort: i to: l.
- 				self sort: k to: j]]!



More information about the Packages mailing list