]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | [/ |
2 | Copyright (c) 2008-2009 Joachim Faulhaber | |
3 | ||
4 | Distributed under the Boost Software License, Version 1.0. | |
5 | (See accompanying file LICENSE_1_0.txt or copy at | |
6 | http://www.boost.org/LICENSE_1_0.txt) | |
7 | ] | |
8 | ||
9 | [section Implementation] | |
10 | ||
11 | The [link boost_icl.interface previous section] gave an overview over the interface | |
12 | of the *icl* outlining | |
13 | [link boost_icl.interface.class_templates class templates], | |
14 | [link boost_icl.interface.associated_types associated types] | |
15 | and polymorphic | |
16 | [link boost_icl.interface.function_synopsis functions and operators]. | |
17 | In preparation to the | |
18 | [link boost_icl.function_reference next section], | |
19 | that describes the *icl's* polymorphic functions in | |
20 | more detail together with ['*complexity characteristics*], | |
21 | this section summarizes some general information on | |
22 | implementation and performance. | |
23 | ||
24 | [h5 STL based implementation] | |
25 | ||
26 | The *implementation* of the *icl's* containers is based on | |
27 | [*std::set] and [*std::map]. So the underlying data structure of | |
28 | interval containers is a red black tree of intervals or | |
29 | interval value pairs. | |
30 | The element containers __icl_set__ and __icl_map__ are wrapper | |
31 | classes of `std::set` and `std::map`. | |
32 | Interval containers are then using __icl_sets__ of intervals | |
33 | or __icl_maps__ of interval value pairs as implementing | |
34 | containers. | |
35 | So all the ['*complexity characteristics*] of icl containers | |
36 | are based on and limited by the ['*red-black tree implementation*] | |
37 | of the underlying std::AssociativeContainers. | |
38 | ||
39 | ||
40 | [section Iterative size] | |
41 | ||
42 | Throughout the documentation on complexity, | |
43 | big /O/ expressions like __On__ or __Omlgn__ refer to container sizes | |
44 | /n/ and /m/. In this documentation these sizes ['*do not*] denote | |
45 | to the familiar `size` function that returns | |
46 | the ['*number of elements*] of a container. Because for an interval container | |
47 | `` | |
48 | interval_set<int> mono; | |
49 | mono += interval<int>::closed(1,5); // {[1 ... 5]} | |
50 | mono.size() == 5; // true, 5 elements | |
51 | mono.interval_count() == 1; // true, only one interval | |
52 | `` | |
53 | ||
54 | it's size and the number of contained intervals is usually different. | |
55 | To refer uniformly to a /size/ that matters for iteration, which is | |
56 | the decisive kind of size concerning algorithmic behavior there is a function | |
57 | `` | |
58 | bool T::iterative_size()const; // Number of entities that can be iterated over. | |
59 | `` | |
60 | for all element and interval containers of the icl. So for | |
61 | complexity statements throughout the icl's documentation | |
62 | the sizes will be `iterative_sizes` and big /O/ expressions like | |
63 | __Omlgn__ will refer to sizes | |
64 | `` | |
65 | n = y.iterative_size(); | |
66 | m = x.iterative_size(); | |
67 | `` | |
68 | for containers `y` and `x`. | |
69 | Note that ``iterative_size`` refers to the primary entities, | |
70 | that we can iterate over. For interval containers these | |
71 | are intervals or segments. ``Itervative_size`` never refers | |
72 | to element iteration for interval containers. | |
73 | ||
74 | [endsect][/ Iterative size] | |
75 | ||
76 | ||
77 | [section Complexity] | |
78 | ||
79 | [h4 Complexity of element containers] | |
80 | ||
81 | Since ['element containers] __icl_set__ and __icl_map__ are only extensions of | |
82 | stl::set and stl::map, their complexity characteristics are | |
83 | accordingly. So their major operations insertion (addition), | |
84 | deletion and search are all using logarithmic time. | |
85 | ||
86 | [h4 Complexity of interval containers] | |
87 | ||
88 | The operations on ['interval containers] behave differently | |
89 | due to the fact that intervals unlike elements can overlap | |
90 | any number of other intervals in a container. As long as | |
91 | intervals are relatively small or just singleton, interval | |
92 | containers behave like containers of elements. | |
93 | For large intervals however time consumption of operations | |
94 | on interval containers may be worse, because most or all | |
95 | intervals of a container may have to be visited. | |
96 | As an example, time complexity of __biLAddition__ on | |
97 | interval containers is briefly discussed. | |
98 | ||
99 | More information on ['*complexity characteristics*] | |
100 | of *icl's* functions is contained in section | |
101 | [link boost_icl.function_reference Function Reference] | |
102 | ||
103 | ||
104 | [h5 Time Complexity of Addition] | |
105 | ||
106 | The next table | |
107 | gives the time complexities for the overloaded | |
108 | `operator +=` on interval containers. | |
109 | The instance types of `T` are given as column headers. | |
110 | Instances of type parameter `P` are denoted in | |
111 | the second column. | |
112 | The third column contains the specific kind of complexity statement. | |
113 | If column three is empty ['*worst case*] complexity is given | |
114 | in the related row. | |
115 | ||
116 | ||
117 | [table Time Complexity of Addition: | |
118 | [[] [`P`] [][interval\nset][separate\ninterval\nset][split\ninterval\nset][interval\nmap][split\ninterval\nmap]] | |
119 | [/ 1operation 2granul. 3case 4itvset 5se_itvset 6sp_itvset 7itv_map 8sp_itvmap] | |
120 | [[`T& operator +=(T& object, const P& addend)`] [`T::element_type`] [] [__Olgn__] [__Olgn__] [__Olgn__] [__Olgn__] [__Olgn__] ] | |
121 | [[] [`T::segment_type`] [best case] [__Olgn__] [__Olgn__] [__Olgn__] [__Olgn__] [__Olgn__] ] | |
122 | [[] [] [worst case] [__On__] [__On__] [__On__] [__On__] [__On__] ] | |
123 | [[] [] [amortized] [__Olgn__] [__Olgn__] [] [] [] ] | |
124 | [[] [`interval_sets`] [] [__Omlgnpm__] [__Omlgnpm__] [__Omlgnpm__] [ ] [ ] ] | |
125 | [[] [`interval_maps`] [] [ ] [ ] [ ] [__Omlgnpm__] [__Omlgnpm__] ] | |
126 | ] | |
127 | ||
128 | Adding an /element/ or | |
129 | /element value pair/ is always done in /logarithmic time/, | |
130 | where /n/ is the number of intervals in the interval container. | |
131 | The same row of complexities applies to the insertion | |
132 | of a /segment/ (an interval or an interval value pair) | |
133 | in the ['*best case*], where the inserted segment does overlap | |
134 | with only a ['*small*] number of intervals in the container. | |
135 | ||
136 | In the ['*worst case*], where the inserted segment overlaps with | |
137 | all intervals in the container, the algorithms | |
138 | iterate over all the overlapped segments. | |
139 | Using inplace manipulations of segments and | |
140 | hinted inserts, it is possible to perform | |
141 | all necessary operations on each iteration step | |
142 | in /constant time/. | |
143 | This results in ['*linear worst case time*] complexity for | |
144 | segment addition for all interval containers. | |
145 | ||
146 | After performing | |
147 | a worst case addition | |
148 | for an __itv_set__ or a __sep_itv_sets__ | |
149 | adding an interval that overlaps /n/ | |
150 | intervals, we | |
151 | need /n/ non overlapping additions of | |
152 | /logarithmic time/ before we can launch | |
153 | another __On__ worst case addition. | |
154 | So we have only a ['*logarithmic amortized | |
155 | time*] for the addition of an interval or interval value pair. | |
156 | ||
157 | For the addition of ['*interval containers*] complexity is __Omlgnpm__. | |
158 | So for the ['*worst case*], where the container sizes /n/ and /m/ | |
159 | are equal and both containers cover the same ranges, | |
160 | the complexity of container addition is ['*loglinear*]. | |
161 | For other cases, that occur frequently in real world applications | |
162 | performance can be much better. | |
163 | If the added container `operand` is much smaller than | |
164 | `object` and the intervals in `operand` are relatively | |
165 | small, performance can be /logarithmic/. | |
166 | If /m/ is small compared with /n/ and intervals in `operand` | |
167 | are large, performance tends to be /linear/. | |
168 | ||
169 | [endsect][/ Complexity] | |
170 | ||
171 | [section Inplace and infix operators] | |
172 | ||
173 | For the major operations /addition, subtraction, intersection/ | |
174 | of *icl* containers and for /symmetric difference/ | |
175 | inplace `operator`s `+= |=, -=, &=` and `^=` | |
176 | are provided. | |
177 | ||
178 | For every ['*inplace*] operator | |
179 | `` | |
180 | T& operator o= (T& object, const P& operand) | |
181 | `` | |
182 | the *icl* provides corresponding ['*infix*] operators. | |
183 | `` | |
184 | T operator o (T object, const P& operand){ return object o= operand; } | |
185 | T operator o (const P& operand, T object){ return object o= operand; } | |
186 | `` | |
187 | ||
188 | From this implementation of the infix `operator o` | |
189 | the compiler will hopefully use return value optimization | |
190 | [@http://en.wikipedia.org/wiki/Return_value_optimization (RVO)] | |
191 | creating no temporary object and performing one copy of | |
192 | the first argument `object`. | |
193 | ||
194 | [caution | |
195 | Compared to the /inplace/ `operator o=` every use of an | |
196 | /infix/ `operator o` requires ['*one extra copy*] | |
197 | of the first argument `object` that passes a container.] | |
198 | ||
199 | Use infix operators only, if | |
200 | ||
201 | * efficiency is not crucial, e.g. the containers copied are small. | |
202 | * a concise and short notation is more important than efficiency in your context. | |
203 | * you need the result of operator `o=` as a copy anyway. | |
204 | ||
205 | [h5 Time Complexity of infix `operators o`] | |
206 | ||
207 | The time complexity of all infix operators of the *icl* | |
208 | is biased by the extra copy of the `object` argument. | |
209 | So all infix `operators o` are at least | |
210 | /linear/ in `n = object.iterative_size()`. | |
211 | Taking this into account, the complexities of all | |
212 | infix operators can be determined | |
213 | from the corresponding inplace `operators o=` they depend | |
214 | on. | |
215 | ||
216 | [endsect][/ Inplace and infix operators] | |
217 | ||
218 | ||
219 | ||
220 | [endsect][/ Implementation] | |
221 |