diff -r f1dd82a47855 -r 03d29bf8c5bb OrderedCollection.st --- a/OrderedCollection.st Fri Apr 13 14:07:28 2018 +0200 +++ b/OrderedCollection.st Fri Apr 13 15:20:37 2018 +0200 @@ -312,6 +312,7 @@ ! ! + !OrderedCollection methodsFor:'accessing'! at:anInteger @@ -749,11 +750,11 @@ Return a collection containing the removed elements. Performance: - this is an O(N) algorithm (the receiver's elements are scanned once)." + this is an O(N) algorithm (the receiver's elements are scanned once)." "/ this is a q&d implementation (possibly slow). - |removed element + |removedElements element srcIndex "{ Class: SmallInteger }" dstIndex "{ Class: SmallInteger }" lastIdx "{ Class: SmallInteger }"| @@ -764,35 +765,35 @@ lastIdx := lastIndex. [ - srcIndex > lastIdx - or:[ aBlock value:(contentsArray at:srcIndex) ] + srcIndex > lastIdx + or:[ aBlock value:(contentsArray at:srcIndex) ] ] whileFalse:[ - srcIndex := srcIndex + 1. + srcIndex := srcIndex + 1. ]. srcIndex > lastIdx ifTrue:[ - "/ nothing removed - ^ #() + "/ nothing removed + ^ #() ]. "/ now srcIndex is the index of element, which is the first to be removed - removed := OrderedCollection new. - removed add:(contentsArray at:srcIndex). + removedElements := OrderedCollection new. + removedElements add:(contentsArray at:srcIndex). dstIndex := srcIndex. srcIndex := srcIndex + 1. srcIndex to:lastIdx do:[:idx| - element := contentsArray at:idx. - (aBlock value:element) ifTrue:[ - removed add:element - ] ifFalse:[ - contentsArray at:dstIndex put:element. - dstIndex := dstIndex + 1. - ]. + element := contentsArray at:idx. + (aBlock value:element) ifTrue:[ + removedElements add:element + ] ifFalse:[ + contentsArray at:dstIndex put:element. + dstIndex := dstIndex + 1. + ]. ]. contentsArray from:dstIndex to:lastIdx put:nil. lastIndex := dstIndex - 1. - ^ removed + ^ removedElements " |coll| @@ -809,76 +810,76 @@ coll1 := OrderedCollection withAll:(1 to:1000). Transcript show:' (1000) - '; showCR:( - Time millisecondsToRun:[ - 100 timesRepeat:[ coll1 copy removeAllSuchThat:[:el | el == 500] ] - ]). + Time millisecondsToRun:[ + 100 timesRepeat:[ coll1 copy removeAllSuchThat:[:el | el == 500] ] + ]). coll2 := OrderedCollection withAll:(1 to:10000). Transcript show:' (10000) - '; showCR:( - Time millisecondsToRun:[ - 100 timesRepeat:[ coll2 copy removeAllSuchThat:[:el | el == 5000] ] - ]). + Time millisecondsToRun:[ + 100 timesRepeat:[ coll2 copy removeAllSuchThat:[:el | el == 5000] ] + ]). coll2 := OrderedCollection withAll:(1 to:50000). Transcript show:' (50000) - '; showCR:( - Time millisecondsToRun:[ - 100 timesRepeat:[ coll2 copy removeAllSuchThat:[:el | el == 25000] ] - ]). + Time millisecondsToRun:[ + 100 timesRepeat:[ coll2 copy removeAllSuchThat:[:el | el == 25000] ] + ]). Transcript showCR:'small number of elements removed:'. coll1 := OrderedCollection withAll:(1 to:1000). Transcript show:' (1000) - '; showCR:( - Time millisecondsToRun:[ - 100 timesRepeat:[ coll1 copy removeAllSuchThat:[:el | el between:500 and:550] ] - ]). + Time millisecondsToRun:[ + 100 timesRepeat:[ coll1 copy removeAllSuchThat:[:el | el between:500 and:550] ] + ]). coll2 := OrderedCollection withAll:(1 to:10000). Transcript show:' (10000) - '; showCR:( - Time millisecondsToRun:[ - 100 timesRepeat:[ coll2 copy removeAllSuchThat:[:el | el between:5000 and:5050] ] - ]). + Time millisecondsToRun:[ + 100 timesRepeat:[ coll2 copy removeAllSuchThat:[:el | el between:5000 and:5050] ] + ]). coll2 := OrderedCollection withAll:(1 to:50000). Transcript show:' (50000) - '; showCR:( - Time millisecondsToRun:[ - 100 timesRepeat:[ coll2 copy removeAllSuchThat:[:el | el between:25000 and:25050] ] - ]). + Time millisecondsToRun:[ + 100 timesRepeat:[ coll2 copy removeAllSuchThat:[:el | el between:25000 and:25050] ] + ]). Transcript showCR:'many elements removed:'. coll1 := OrderedCollection withAll:(1 to:1000). Transcript show:' (1000) - '; showCR:( - Time millisecondsToRun:[ - 100 timesRepeat:[ coll1 copy removeAllSuchThat:[:el | el even] ] - ]). + Time millisecondsToRun:[ + 100 timesRepeat:[ coll1 copy removeAllSuchThat:[:el | el even] ] + ]). coll2 := OrderedCollection withAll:(1 to:10000). Transcript show:' (10000) - '; showCR:( - Time millisecondsToRun:[ - 100 timesRepeat:[ coll2 copy removeAllSuchThat:[:el | el even] ] - ]). + Time millisecondsToRun:[ + 100 timesRepeat:[ coll2 copy removeAllSuchThat:[:el | el even] ] + ]). coll2 := OrderedCollection withAll:(1 to:50000). Transcript show:' (50000) - '; showCR:( - Time millisecondsToRun:[ - 100 timesRepeat:[ coll2 copy removeAllSuchThat:[:el | el even] ] - ]). + Time millisecondsToRun:[ + 100 timesRepeat:[ coll2 copy removeAllSuchThat:[:el | el even] ] + ]). " " - compiled bytecode bytecode/new (no jitter) - no element removed: - (1000) - 10 20 20 - (10000) - 70 240 200 - (50000) - 390 1190 940 - small number of elements removed: - (1000) - 10 30 20 - (10000) - 160 300 260 - (50000) - 700 1540 1180 - many elements removed: - (1000) - 10 20 30 - (10000) - 130 290 260 - (50000) - 720 1470 1300 + compiled bytecode bytecode/new (no jitter) + no element removed: + (1000) - 10 20 20 + (10000) - 70 240 200 + (50000) - 390 1190 940 + small number of elements removed: + (1000) - 10 30 20 + (10000) - 160 300 260 + (50000) - 700 1540 1180 + many elements removed: + (1000) - 10 20 30 + (10000) - 130 290 260 + (50000) - 720 1470 1300 " "Modified: 8.2.1997 / 19:19:00 / cg" !