I saw a question online recently which basically asked whether big-O notation always holds true in practice. For example, in theory, searching through a vector for an item should be O(n) whereas searching a map should be O(log n). Right?<\/p>\n
Let’s imagine we create a vector with 100,000 random integers in it. We then sort the vector, and run two different searches on it. The first search starts at the beginning, compares the element against the value we’re searching for, and simply keeps incrementing until we find it. A naive search you might say. Without resorting to std:: algorithms, how might you improve it?<\/p>\n
A worthy idea might be a recursive binary, or bisection, search. We might, for example, make 15 bisections to find a value in the upper quadrant of our range, compared to, say 75,000 comparisons in the brute force approach.<\/p>\n
That’s fairly safe to say that the binary search is going to be much faster, right?<\/p>\n
Not necessarily. See the results below:<\/p>\n
100000 random numbers generated, inserted, and sorted in a vector:\r\n\u00a00.018477s wall, 0.010000s user + 0.000000s system = 0.010000s CPU (54.1%)\r\n\r\nLinear search iterations: = 75086, time taken:\r\n\u00a00.000734s wall, 0.000000s user + 0.000000s system = 0.000000s CPU (n\/a%)\r\n\r\nBinary search iterations: 17, time taken:\r\n\u00a00.001327s wall, 0.000000s user + 0.000000s system = 0.000000s CPU (n\/a%)<\/pre>\nAre you surprised to see that the binary search took (very) slightly longer<\/strong> than the brute force approach?<\/p>\n
Welcome to the world of modern processors. What’s going on there is a healthy dose of branch prediction<\/strong> and plenty of valid processor cache hits<\/strong> which actually makes the brute force approach viable.<\/p>\n
I guess the moral of this story is, as always, don’t optimise prematurely – because you might actually be making things worse! Always profile your hot spots and work empirically rather than on what you think you know about algorithm efficiency.<\/p>\n
The code used here is reproduced below – it should compile on VS 2015, clang and g++ without issue. You’ll need Boost for the timers. You may see wildly different timings depending on optimisation levels and other factors :)<\/p>\n
\r\n#include <iostream>\r\n#include <vector>\r\n#include <random>\r\n#include <algorithm>\r\n#include <string>\r\n\r\n#include "boost\/timer\/timer.hpp"\r\n\r\nconst int MAX_VAL = 100'000;\r\n\r\ntemplate <typename T>\r\nT LinearSearch(typename std::vector<T>::iterator begin,\r\n\u00a0\u00a0\u00a0 typename std::vector<T>::iterator end, T value)\r\n{\r\n\u00a0\u00a0\u00a0 \/\/ While not ostensibly efficient, branch prediction and CPU cache for the\r\n\u00a0\u00a0\u00a0 \/\/ contiguous vector data should make this go like greased lightning :)\r\n\u00a0\u00a0\u00a0 size_t counter{0};\r\n\u00a0\u00a0\u00a0 while (begin < end)\r\n\u00a0\u00a0\u00a0 {\r\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 if (*begin >= value)\r\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 {\r\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 std::cout << "\\nLinear search iterations: = " << counter;\r\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 return *begin;\r\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 }\r\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 ++begin;\r\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 ++counter;\r\n\u00a0\u00a0\u00a0 }\r\n\u00a0\u00a0\u00a0 return 0;\r\n}\r\n\r\ntemplate <typename T>\r\nT BinarySearch(typename std::vector<T>::iterator begin,\r\n\u00a0\u00a0\u00a0 typename std::vector<T>::iterator end, T value)\r\n{\r\n\u00a0\u00a0\u00a0 \/\/ The return value is not exact... just interested in getting close to the\r\n\u00a0\u00a0\u00a0 \/\/ value.\r\n\u00a0\u00a0\u00a0 static size_t counter{0};\r\n\u00a0\u00a0\u00a0 size_t mid = (end - begin) \/ 2;\r\n\u00a0\u00a0\u00a0 ++counter;\r\n\u00a0\u00a0\u00a0 if (begin >= end)\r\n\u00a0\u00a0\u00a0 {\r\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 std::cout << "\\nBinary search iterations: " << counter;\r\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 return *begin;\r\n\u00a0\u00a0\u00a0 }\r\n\u00a0\u00a0\u00a0 if (*(begin + mid) < value)\r\n\u00a0\u00a0\u00a0 {\r\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 return BinarySearch(begin + mid + 1, end, value);\r\n\u00a0\u00a0\u00a0 }\r\n\u00a0\u00a0\u00a0 else if (*(begin + mid) > value)\r\n\u00a0\u00a0\u00a0 {\r\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 return BinarySearch(begin, begin + mid - 1, value);\r\n\u00a0\u00a0\u00a0 }\r\n\u00a0\u00a0\u00a0 else\r\n\u00a0\u00a0\u00a0 {\r\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 std::cout << "\\nBinary search iterations: " << counter;\r\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 return value;\r\n\u00a0\u00a0\u00a0 }\r\n}\r\n\r\nint main()\r\n{\r\n\u00a0\u00a0\u00a0 \/\/ Fill a vector with MAX_VAL random numbers between 0 - MAX_VAL\r\n\u00a0\u00a0\u00a0 std::vector<unsigned int> vec;\r\n\u00a0\u00a0\u00a0 vec.reserve(MAX_VAL);\r\n\r\n\u00a0\u00a0\u00a0 {\r\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 boost::timer::auto_cpu_timer tm;\r\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 std::random_device randomDevice;\r\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 std::default_random_engine randomEngine(randomDevice());\r\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 std::uniform_int_distribution<unsigned int> uniform_dist(0, MAX_VAL);\r\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 for (int n = 0; n < MAX_VAL; ++n)\r\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 {\r\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 vec.emplace_back(uniform_dist(randomEngine));\r\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 }\r\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 \/\/ Sort the vector\r\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 std::sort(vec.begin(), vec.end());\r\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 std::cout << MAX_VAL\r\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 << " random numbers generated, inserted, and sorted"\r\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 " in a vector:" << std::endl;\r\n\u00a0\u00a0\u00a0 }\r\n\r\n\u00a0\u00a0\u00a0 {\r\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 boost::timer::auto_cpu_timer tm2;\r\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 LinearSearch(\r\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 vec.begin(), vec.end(), static_cast<unsigned int>(MAX_VAL * 0.75));\r\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 std::cout << ", time taken:" << std::endl;\r\n\u00a0\u00a0\u00a0 }\r\n\u00a0\u00a0\u00a0 {\r\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 boost::timer::auto_cpu_timer tm2;\r\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 BinarySearch(vec.begin(), vec.end() - 1,\r\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 static_cast<unsigned int>(MAX_VAL * 0.75));\r\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 std::cout << ", time taken:" << std::endl;\r\n\u00a0\u00a0\u00a0 }\r\n\r\n\u00a0\u00a0\u00a0 return 0;\r\n}\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"I saw a question online recently which basically asked whether big-O notation always holds true in practice. For example, in theory, searching through a vector for an item should be O(n) whereas searching a map should be O(log n). Right? Let’s imagine we create a vector with 100,000 random integers in it. We then sort … <\/p>\n