1

Topic: QSet, speed of search of the container

In one of algorithms we have keys, keys it is the integer numbers, each new key should be unique, therefore for assignment of a new key the global counter on 1 simply increases. In the course of operation some keys appear are remote, as a result there is a set of integer numbers from a range [1, 32000] (for example) which really are present not all (for example from them only 1000 numbers really is). It is necessary to sort out all these numbers. We added all of them in QSet <int> (hash-set) then search organized one of two methods: QSet <int> indices =...; for (int i = 0; i <32000; ++ i) {if (indices.contains (i)) {int corrent_index = i;//some code}} the second method: QSet <int> indices =...; for (QSet <int>:: iterator it = indices.begin (); it! = indices.end (); ++ it) {int corrent_index = *it;//some code} it would Seem, in the second a variant we have a smaller cycle in 20 times. However time samplings show that the second cycle on time more than in 2 times more slowly the first. It QSet <int> such slow? Or I not so made something? Wanted to try std:: unordered_set, but at us support 11 standards is disconnected, and quickly I it cannot include - there the order of 800 errors connected with constexpr... PS. Tried to remove unnecessary particulars but if it is necessary - I can explain more in detail, as what for becomes. If very much  is a part of implementation of algorithm of selection of areas on the binary image. We try to accelerate it, optimization of an identification of indexes already made (through disjoint set union, there the tree is used, amortized complexity O (a (n)) that is almost a constant). Actually it also is indexes.

2

Re: QSet, speed of search of the container

Hello, the Smith, you wrote: for (QSet <int>:: iterator it = indices.begin (); it! = indices.end (); ++ it) And if QSet <int>:: const_iterator? (See help: "Const iterators are slightly faster, and can improve code readability.") But it I so, bad shot...  on Yandex. A disk

3

Re: QSet, speed of search of the container

Hello, Anton Batenev, you wrote: AB> And if QSet <int>:: const_iterator? (See help: "Const iterators are slightly faster, and can improve code readability.") AB> But it I so, bad shot... Also save result of a call indices.end () before a cycle. It is possible still  the second variant to understand that really wastes time.

4

Re: QSet, speed of search of the container

Hello, the Smith, you wrote: QSet <int> indices =...; for (QSet <int>:: iterator it = indices.begin (); it! = indices.end (); ++ it) {> int corrent_index = *it;//some code}> it would Seem, in the second a variant we have a smaller cycle in 20 times. However time samplings show that the second cycle on time more than in 2 times more slowly the first. It is strange. It QSet <int> such slow? Or I not so made something? Try so: QSet <int> indices =...; for (QSet <int>:: iterator it = indices.begin (), itEnd = indices.end (); it! = itEnd; ++ it) {int corrent_index = *it;//some code} [/ccode]

5

Re: QSet, speed of search of the container

Hello, the Smith, you wrote: Wanted to try std:: unordered_set and why it is not simple std:: set?

6

Re: QSet, speed of search of the container

Different O-big

7

Re: QSet, speed of search of the container

Hello, reversecode, you wrote: R> different O-big Yes, std:: set has logarithmic time of an insertion, and unordered_set a constant on the average. In exchange std:: set it is arranged, and other order does not guarantee, orderliness in any way does not help with our case, but handling time is critical.

8

Re: QSet, speed of search of the container

Hello, the Smith, you wrote: R>> different O-big Yes, std:: set has logarithmic time of an insertion, and unordered_set a constant on the average. In exchange std:: set it is arranged, and other order does not guarantee, orderliness in any way does not help with our case, but handling time is critical. It is all clearly. But my experience prompts something to me that all these moments on this data set with the registration that the data - integrals - are not of great importance...

9

Re: QSet, speed of search of the container

Try from  take there should to be under any versions of the standard and

10

Re: QSet, speed of search of the container

I answer in a root as it is the answer to some posts. Made const_iterator and remembered indices.end () not to pull it in a cycle (it would seem, it should , but is fine, remembered manually). All the same the operating time surprises: One of reports on an operating time: count = 5977 (max_index) 3322 (indices.size) - the full search almost 6000 , and hash-set almost in 2 times is less point1 dt = 2.2303e-05 - the full search by a cycle with index stock-taking in set point2 dt = 5.9156e-05 - search by the constant iterator on hash-set Again, search on set appeared almost in 2 times more slowly. Certainly, volume reduction this time not essential, but quits that iteration procedure on QSet' at least in 4 times more slowly iterations on integer numbers. Here one more report: count = 83 (max_index) 4 (indices.size) point1 dt = 6.87e-07 point2 dt = 1.453e-06 the set Volume in 20 times is less, and time all the same appeared in 2 times more at iteration on set... Still an example (in the previous it can so to appear that because of very small volumes an overhead charge for cycle initialization superimposed advantage): count = 2434 (max_index) 310 (indices.size) point1 dt = 7.236e-06 point2 dt = 1.0598e-05 At search reduction almost in 7 times time operation grew, well though not in 2 times, but it is all the same essential... It is very strange, or the hash-set of really many overhead charge attracts, or I somewhere am very rather strong ... Check up on  Qt' implementation QSet' I can not (in 11 standard to us it is impossible, the project for 10 minutes I will not correct to collect with-std=c ++ 11)... It is possible to try to make the implementation of set, but it is doubtful that the bicycle overtakes library (if only at Qt there is no jamb, everyone happens). PS. Version Qt at us 4.8

11

Re: QSet, speed of search of the container

Hello, niXman, you wrote: X> Hello, the Smith, you wrote: R>>> different O-big> Yes, std:: set has logarithmic time of an insertion, and unordered_set a constant on the average. In exchange std:: set it is arranged, and other order does not guarantee, orderliness in any way does not help with our case, but handling time is critical. X> it is all clearly. But my experience prompts something to me that all these moments on this data set with the registration that the data - integrals - are not of great importance... These given not integrals, it is indexes. Our algorithm follows article the link, to each again found object the index, sometimes indexes is appropriated it is necessary to identify, thus there is one of them (which - the algorithm of an identification defines, for us there works disjoint-set-union, therefore it is impossible to tell, for example, that is always selected smaller of two). These indexes then in QSet also have been added, and everyone was put so much time, how many other indexes have been identified, therefore and it was necessary  a hash-set not to be engaged each time in search in already typed indexes (it would be possible to add in std:: vector but then we would have many repeating numbers that breaks algorithm)

12

Re: QSet, speed of search of the container

Hello, the Smith, you wrote: I Answer in a root as it is the answer to some posts. Made const_iterator and remembered indices.end () not to pull it in a cycle (it would seem, it should , but is fine, remembered manually). All the same the operating time surprises: I hope that results are resulted for  assembly.

13

Re: QSet, speed of search of the container

Hello, solano, you wrote: S> Hello, the Smith, you wrote:>> I Answer in a root as it is the answer to some posts.>> Made const_iterator and remembered indices.end () not to pull it in a cycle (it would seem, it should , but is fine, remembered manually).>> All the same the operating time surprises: S> I hope that results are resulted for  assembly. Certainly. The reliznaja assembly, optimization-O3. I will try now still with-O2 just in case...

14

Re: QSet, speed of search of the container