std::vector vs sorted std::vector vs std::set

In this short article I’m going to make a comparison between std::vector, sorted std::vector and std::set. However, I’m going to focus only on one aspect – which collection is faster during lookup.

Looks like the answer is rather trivial – std::map and sorted std::vector offer access to any element in O(log n) time while unsorted std::vector offers linear finding. To be precise – std::vector + std::find as std::vector doesn’t have built-in find function. Indeed, sorted collections are winners… Or maybe the answer is not so trivial?

Disclaimer

First of all, this is not a definitive answer which collection is faster in that particular case. The test results strongly depends on underlying hardware, especially CPU model and memory. In my case it is Intel’s i7. So if you would like to know how it behaves on your hardware, you need to make such tests on your own. Fortunately, the source code is available here so there is no need to write them once again.

Test procedure

The test procedure is rather simple. Fill out given collection with random data and then ask for some randomly generated items. The latter operations will be checked against execution time.

Please note that the results should not be interpreted as absolute values, rather they should be compared to each other.

1 element

Action Time for unoptimized Time for O2 Time for O3
Unsorted std::vector lookup 170 ms 8 ms 9 ms
Sorted std::vector lookup 169 ms 4 ms 4 ms
std::set lookup 174 ms 4 ms 5 ms

10 elements

Action Time for unoptimized Time for O2 Time for O3
Unsorted std::vector lookup 207 ms 7 ms 7 ms
Sorted std::vector lookup 240 ms 12 ms 10 ms
std::set lookup 259 ms 7 ms 7 ms

100 elements

Action Time for unoptimized Time for O2 Time for O3
Unsorted std::vector lookup 1 115 ms 56 ms 56 ms
Sorted std::vector lookup 384 ms 16 ms 17 ms
std::set lookup 449 ms 12 ms 11 ms

1k elements

Action Time for unoptimized Time for O2 Time for O3
Unsorted std::vector lookup 9 964 ms 408 ms 408 ms
Sorted std::vector lookup 546 ms 59 ms 59 ms
std::set lookup 589 ms 60 ms 61 ms

10k elements

Action Time for unoptimized Time for O2 Time for O3
Unsorted std::vector lookup 99 537 ms 4 269 ms 4 473 ms
Sorted std::vector lookup 708 ms 86 ms 96 ms
std::set lookup 742 ms 120 ms 121 ms

100k elements

Action Time for unoptimized Time for O2 Time for O3
Unsorted std::vector lookup
Sorted std::vector lookup 864 ms 138 ms 136 ms
std::set lookup 959 ms 207 ms 213 ms

1 000k elements

Action Time for unoptimized Time for O2 Time for O3
Unsorted std::vector lookup
Sorted std::vector lookup 1 073 ms 191 ms 195 ms
std::set lookup 1 725 ms 702 ms 706 ms

Conclusions

The unoptimized build offers significantly worse performance. There is no difference between O2 and O3 in this particular case.

Sorted std::vector is faster than std::set when the collection size is large, > 1k. The bigger collection, the more significant difference.

When a collection size is small, no more than 20 items, one can notice some anomalies. For example, linear searching unsorted collection may be faster than binary search. However, it may strongly depend on underlying hardware.

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *