# HG changeset patch
# User Claus Gittinger <cg@exept.de>
# Date 1553760808 -3600
# Node ID d446c3eccc4159839ed8975de9d5710beffc9923
# Parent  171e12f06b7098d5b766c58208dedaac2605567c
#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.

diff -r 171e12f06b70 -r d446c3eccc41 SelectionInListModelView.st
--- 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
 !