--- a/RunArray.st Sat May 11 12:47:55 1996 +0200
+++ b/RunArray.st Sat May 11 13:27:54 1996 +0200
@@ -86,22 +86,34 @@
documentation
"
This implements an array which uses runs to minimise the amount
- of data that it holds. Basically it should be used if you know that an array
- is going to contain a lot of runs of exactly the same data.
+ of data that it holds.
+ Basically it should be used if you know that an array is going to contain
+ a lot of runs of exactly the same data.
- The user should not be able to see the difference between an Array and a RunArray. This has a
+ RunArrays are used by the Text class to keep character attributes
+ (which we expect to remain constant for longer character ranges).
Notice:
there is only a space saving if there are really runs (i.e. multiple
elements which compare same).
Otherwise, an Array is more compact.
+ [instance variables:]
+ runs <Array> contains the runs, consisting of
+ length/value entries.
+
+ [implementation note:]
+ structure-wise, it would have been more intuitive, to keep
+ instances of Run objects (as done in CompressedOrderedCollection)
+ instead of alternating length/values in the `runs' collection.
+ However, doing this means that lots of additional memory is required.
+ Here, we choose the more space efficient way.
[author:]
Claus Gittinger
[see also:]
- Array OrderedCollection CompressedorderedCollection
+ Array OrderedCollection CompressedOrderedCollection
"
!
@@ -109,95 +121,65 @@
"
this eats up a lot of memory ...
... but its relatively fast:
- [exBegin]
+ [exBegin]
|coll|
coll := OrderedCollection new.
Transcript showCr:(
- Time millisecondsToRun:[
- 100000 timesRepeat:[coll add:'hello'].
- 100000 timesRepeat:[coll add:'world'].
- ]
+ Time millisecondsToRun:[
+ 100000 timesRepeat:[coll add:'hello'].
+ 100000 timesRepeat:[coll add:'world'].
+ ]
).
coll inspect.
- [exEnd]
+ [exEnd]
this is very space efficient ...
- ... but much slower:
- [exBegin]
- |coll|
-
- coll := RunArray new.
- Transcript showCr:(
- Time millisecondsToRun:[
- 100000 timesRepeat:[coll add:'hello'].
- 100000 timesRepeat:[coll add:'world'].
- ]
- ).
- coll inspect.
- [exEnd]
-
-
- this is very space efficient ...
- ... AND much faster:
- [exBegin]
+ ... (and even slightly faster):
+ [exBegin]
|coll|
coll := RunArray new.
Transcript showCr:(
- Time millisecondsToRun:[
- coll add:'hello' withCount:100000.
- coll add:'world' withCount:100000.
- ]
+ Time millisecondsToRun:[
+ 100000 timesRepeat:[coll add:'hello'].
+ 100000 timesRepeat:[coll add:'world'].
+ ]
).
coll inspect.
- [exEnd]
+ [exEnd]
- this is very space INEFFICIENT (a real memory pig ;-) ...
- ... and much slower:
- [exBegin]
+ this is very space efficient ...
+ ... AND much faster:
+ [exBegin]
|coll|
coll := RunArray new.
Transcript showCr:(
- Time millisecondsToRun:[
- 1 to:1000 do:[:i | coll add:i].
- ]
+ Time millisecondsToRun:[
+ coll add:'hello' withOccurrences:100000.
+ coll add:'world' withOccurrences:100000.
+ ]
).
coll inspect.
- [exEnd]
+ [exEnd]
- things like this are VERY slow:
- [exBegin]
+ this is very space INEFFICIENT (a real memory pig ;-) ...
+ ... and much slower:
+ [exBegin]
|coll|
coll := RunArray new.
- 1 to:1000 do:[:i | coll add:i].
Transcript showCr:(
- Time millisecondsToRun:[
- 1000 to:1 by:-2 do:[:i | coll removeIndex:i].
- ]
- )
- [exEnd]
-
- much faster with OCs (although these are not optimal for this, too):
- [exBegin]
- |coll|
-
- coll := OrderedCollection new.
- 1 to:1000 do:[:i | coll add:i].
- Transcript showCr:(
- Time millisecondsToRun:[
- 1000 to:1 by:-2 do:[:i | coll removeIndex:i].
- ]
- )
- [exEnd]
-
- in general, such things are better done by constructing a new collection
- from scratch (use #select: or #collect:)
+ Time millisecondsToRun:[
+ 1 to:1000 do:[:i | coll add:i].
+ ]
+ ).
+ coll inspect.
+ [exEnd]
"
! !
@@ -799,5 +781,5 @@
!RunArray class methodsFor:'documentation'!
version
- ^ '$Header: /cvs/stx/stx/libbasic2/RunArray.st,v 1.1 1996-05-11 10:47:55 cg Exp $'
+ ^ '$Header: /cvs/stx/stx/libbasic2/RunArray.st,v 1.2 1996-05-11 11:27:54 cg Exp $'
! !