#TUNING by cg
class: SelectionInListModelView
changed: #selectElements:ifAnyAbsent:
with many elements to select, this degraded to a O(n^2)
algorithm; making it very slow when the list size * selection size
was large. Changed to an O(n) algorithm.
--- a/SelectionInListModelView.st Mon Mar 18 11:32:31 2019 +0100
+++ b/SelectionInListModelView.st Thu Mar 28 09:13:28 2019 +0100
@@ -1,3 +1,5 @@
+"{ Encoding: utf8 }"
+
"
COPYRIGHT (c) 1999 by eXept Software AG
All Rights Reserved
@@ -2619,13 +2621,35 @@
!
selectElements:aCollectionOfElements ifAnyAbsent:exceptionalValue
- |indices|
-
- indices := aCollectionOfElements collect:[:each |
- self identityIndexOf:each.
- ].
- (indices includes:0) ifTrue:[
- ^ exceptionalValue value
+ |indices setOfElements searchStart|
+
+ aCollectionOfElements size > 20 ifTrue:[
+ setOfElements := aCollectionOfElements asIdentitySet.
+ indices := (1 to:list size) select:[:idx |
+ setOfElements includes:(list at:idx).
+ ].
+ (indices size < aCollectionOfElements size) ifTrue:[
+ ^ exceptionalValue value
+ ].
+ ] ifFalse:[
+ "/ another O(n^2) algorithm...
+ "/ tuned to be O(n) IFF the elements come in sorted
+ searchStart := 1.
+ indices := aCollectionOfElements collect:[:each |
+ |idx|
+
+ idx := list identityIndexOf:each startingAt:searchStart.
+ idx == 0 ifTrue:[
+ searchStart ~~ 1 ifTrue:[
+ idx := list identityIndexOf:each startingAt:1.
+ ].
+ idx == 0 ifTrue:[
+ ^ exceptionalValue value
+ ].
+ ].
+ searchStart := idx+1.
+ idx.
+ ].
].
self selection:indices
!