55 " |
55 " |
56 ! |
56 ! |
57 |
57 |
58 examples |
58 examples |
59 " |
59 " |
60 when many individual elements are to be added, it may be |
60 when many elements are to be added, it may be better to add them |
61 better to add them all unsorted & resort the collection completely. |
61 all en-bloeque instead of individually. |
62 The reason is that for each individual #add:, the contents has to be |
62 The reason is that for each individual #add:, the contents has to be |
63 moved around, to create an empty slot for the new element. |
63 shifted, to create an empty slot for the new element. |
64 |
64 |
65 timing example: |
65 timing example: |
66 |
66 |
67 |o rnd| |
67 |o rnd| |
68 |
68 |
69 o := SortedCollection new. |
69 o := SortedCollection new. |
70 rnd := Random new. |
70 rnd := Random new. |
71 1000 timesRepeat:[ |
71 10000 timesRepeat:[ |
72 o add:rnd next. |
72 o add:rnd next. |
73 ] |
73 ] |
74 |
74 |
75 takes 438 ms on a DS3100 (admitted: this is a very slow machine ;-) |
75 takes 1365 ms on a P5 (admitted: this is a fast machine ;-) |
76 In contrast: |
76 In contrast: |
77 |
77 |
78 |o rnd| |
78 |o rnd| |
79 |
79 |
80 o := OrderedCollection new. |
80 o := OrderedCollection new. |
81 rnd := Random new. |
81 rnd := Random new. |
82 1000 timesRepeat:[ |
82 10000 timesRepeat:[ |
83 o add:rnd next. |
83 o add:rnd next. |
84 ]. |
84 ]. |
85 o := o asSortedCollection |
85 o := o asSortedCollection |
86 |
86 |
87 takes 332 ms on the same machine. |
87 takes 383 ms on the same machine. |
88 Things become more drastic with more elements; with 10000 elements, |
|
89 the times are: 15418 ms vs. 4332 ms. |
|
90 |
88 |
91 If you already have a big sortedCollection at hand, adding multiple |
89 If you already have a big sortedCollection at hand, adding multiple |
92 items may be better done with #addAll:, which resorts all elements, if |
90 items may be better done with #addAll:, which resorts all elements, if |
93 the number of added items is more than some threshold number. |
91 the number of added items is more than some threshold number. |
94 Building some big collection: |
92 Building some big collection: |
95 |
93 |
96 |o rnd c| |
94 |o rnd c| |
97 |
95 |
98 o := OrderedCollection new. |
96 o := OrderedCollection new. |
99 rnd := Random new. |
97 rnd := Random new. |
|
98 10000 timesRepeat:[ |
|
99 o add:rnd next. |
|
100 ]. |
|
101 o := o asSortedCollection. |
|
102 |
|
103 adding 1000 elements individually to it: |
|
104 |
100 1000 timesRepeat:[ |
105 1000 timesRepeat:[ |
101 o add:rnd next. |
106 o add:rnd next. |
102 ]. |
107 ]. |
103 o := o asSortedCollection. |
108 |
104 |
109 takes 258 ms |
105 adding 1000 elements to it: |
|
106 |
|
107 1000 timesRepeat:[ |
|
108 o add:rnd next. |
|
109 ]. |
|
110 |
|
111 takes 3121 ms |
|
112 (because the elements have to be shifted around for each added element); |
110 (because the elements have to be shifted around for each added element); |
113 |
111 |
114 while adding them with: |
112 while adding them en-bloque with: |
115 |
113 |
116 c := OrderedCollection new. |
114 c := OrderedCollection new. |
117 1000 timesRepeat:[ |
115 1000 timesRepeat:[ |
118 c add:rnd next. |
116 c add:rnd next. |
119 ]. |
117 ]. |
120 o addAll:o |
118 o addAll:o |
121 |
119 |
122 taks ms |
120 takes 71 ms |
123 " |
121 " |
124 ! ! |
122 ! ! |
125 |
123 |
126 !SortedCollection class methodsFor:'initialization'! |
124 !SortedCollection class methodsFor:'initialization'! |
127 |
125 |