84 ! |
84 ! |
85 |
85 |
86 documentation |
86 documentation |
87 " |
87 " |
88 This implements an array which uses runs to minimise the amount |
88 This implements an array which uses runs to minimise the amount |
89 of data that it holds. Basically it should be used if you know that an array |
89 of data that it holds. |
90 is going to contain a lot of runs of exactly the same data. |
90 Basically it should be used if you know that an array is going to contain |
91 |
91 a lot of runs of exactly the same data. |
92 The user should not be able to see the difference between an Array and a RunArray. This has a |
92 |
|
93 RunArrays are used by the Text class to keep character attributes |
|
94 (which we expect to remain constant for longer character ranges). |
93 |
95 |
94 Notice: |
96 Notice: |
95 there is only a space saving if there are really runs (i.e. multiple |
97 there is only a space saving if there are really runs (i.e. multiple |
96 elements which compare same). |
98 elements which compare same). |
97 Otherwise, an Array is more compact. |
99 Otherwise, an Array is more compact. |
98 |
100 |
|
101 [instance variables:] |
|
102 runs <Array> contains the runs, consisting of |
|
103 length/value entries. |
|
104 |
|
105 [implementation note:] |
|
106 structure-wise, it would have been more intuitive, to keep |
|
107 instances of Run objects (as done in CompressedOrderedCollection) |
|
108 instead of alternating length/values in the `runs' collection. |
|
109 However, doing this means that lots of additional memory is required. |
|
110 Here, we choose the more space efficient way. |
99 |
111 |
100 [author:] |
112 [author:] |
101 Claus Gittinger |
113 Claus Gittinger |
102 |
114 |
103 [see also:] |
115 [see also:] |
104 Array OrderedCollection CompressedorderedCollection |
116 Array OrderedCollection CompressedOrderedCollection |
105 " |
117 " |
106 ! |
118 ! |
107 |
119 |
108 examples |
120 examples |
109 " |
121 " |
110 this eats up a lot of memory ... |
122 this eats up a lot of memory ... |
111 ... but its relatively fast: |
123 ... but its relatively fast: |
112 [exBegin] |
124 [exBegin] |
113 |coll| |
125 |coll| |
114 |
126 |
115 coll := OrderedCollection new. |
127 coll := OrderedCollection new. |
116 Transcript showCr:( |
128 Transcript showCr:( |
117 Time millisecondsToRun:[ |
129 Time millisecondsToRun:[ |
118 100000 timesRepeat:[coll add:'hello']. |
130 100000 timesRepeat:[coll add:'hello']. |
119 100000 timesRepeat:[coll add:'world']. |
131 100000 timesRepeat:[coll add:'world']. |
120 ] |
132 ] |
121 ). |
133 ). |
122 coll inspect. |
134 coll inspect. |
123 [exEnd] |
135 [exEnd] |
124 |
136 |
125 |
137 |
126 this is very space efficient ... |
138 this is very space efficient ... |
127 ... but much slower: |
139 ... (and even slightly faster): |
128 [exBegin] |
140 [exBegin] |
129 |coll| |
141 |coll| |
130 |
142 |
131 coll := RunArray new. |
143 coll := RunArray new. |
132 Transcript showCr:( |
144 Transcript showCr:( |
133 Time millisecondsToRun:[ |
145 Time millisecondsToRun:[ |
134 100000 timesRepeat:[coll add:'hello']. |
146 100000 timesRepeat:[coll add:'hello']. |
135 100000 timesRepeat:[coll add:'world']. |
147 100000 timesRepeat:[coll add:'world']. |
136 ] |
148 ] |
137 ). |
149 ). |
138 coll inspect. |
150 coll inspect. |
139 [exEnd] |
151 [exEnd] |
140 |
152 |
141 |
153 |
142 this is very space efficient ... |
154 this is very space efficient ... |
143 ... AND much faster: |
155 ... AND much faster: |
144 [exBegin] |
156 [exBegin] |
145 |coll| |
157 |coll| |
146 |
158 |
147 coll := RunArray new. |
159 coll := RunArray new. |
148 Transcript showCr:( |
160 Transcript showCr:( |
149 Time millisecondsToRun:[ |
161 Time millisecondsToRun:[ |
150 coll add:'hello' withCount:100000. |
162 coll add:'hello' withOccurrences:100000. |
151 coll add:'world' withCount:100000. |
163 coll add:'world' withOccurrences:100000. |
152 ] |
164 ] |
153 ). |
165 ). |
154 coll inspect. |
166 coll inspect. |
155 [exEnd] |
167 [exEnd] |
156 |
168 |
157 |
169 |
158 this is very space INEFFICIENT (a real memory pig ;-) ... |
170 this is very space INEFFICIENT (a real memory pig ;-) ... |
159 ... and much slower: |
171 ... and much slower: |
160 [exBegin] |
172 [exBegin] |
161 |coll| |
173 |coll| |
162 |
174 |
163 coll := RunArray new. |
175 coll := RunArray new. |
164 Transcript showCr:( |
176 Transcript showCr:( |
165 Time millisecondsToRun:[ |
177 Time millisecondsToRun:[ |
166 1 to:1000 do:[:i | coll add:i]. |
178 1 to:1000 do:[:i | coll add:i]. |
167 ] |
179 ] |
168 ). |
180 ). |
169 coll inspect. |
181 coll inspect. |
170 [exEnd] |
182 [exEnd] |
171 |
|
172 |
|
173 things like this are VERY slow: |
|
174 [exBegin] |
|
175 |coll| |
|
176 |
|
177 coll := RunArray new. |
|
178 1 to:1000 do:[:i | coll add:i]. |
|
179 Transcript showCr:( |
|
180 Time millisecondsToRun:[ |
|
181 1000 to:1 by:-2 do:[:i | coll removeIndex:i]. |
|
182 ] |
|
183 ) |
|
184 [exEnd] |
|
185 |
|
186 much faster with OCs (although these are not optimal for this, too): |
|
187 [exBegin] |
|
188 |coll| |
|
189 |
|
190 coll := OrderedCollection new. |
|
191 1 to:1000 do:[:i | coll add:i]. |
|
192 Transcript showCr:( |
|
193 Time millisecondsToRun:[ |
|
194 1000 to:1 by:-2 do:[:i | coll removeIndex:i]. |
|
195 ] |
|
196 ) |
|
197 [exEnd] |
|
198 |
|
199 in general, such things are better done by constructing a new collection |
|
200 from scratch (use #select: or #collect:) |
|
201 " |
183 " |
202 ! ! |
184 ! ! |
203 |
185 |
204 !RunArray class methodsFor:'instance creation'! |
186 !RunArray class methodsFor:'instance creation'! |
205 |
187 |