I need to be quick about this, As I don't have much time today.
But the Standard Library mentioned that the contains() function is O(n).
Is there a better way to do this? (at least not linear time)
If the vector is sorted, you can use binary_search, which takes O(log 𝓃) time. Otherwise, O(𝓃) is the best you can theoretically achieve.
2 Likes
Have you considered alternative collections? A HashSet can do it in O(1).
8 Likes
Also check your dataset sizes (typical and worst-case). I'd rather have a simple and efficient O(n) with a smallish n than an O(1) with a big constant cost.
As always, benchmark.
8 Likes
I can't remember the exact talk, but several years ago there was a talk at CppCon showing the relative performance of different data structures. The big thing I took away was that linearly scanning std::vector (Vec) was faster than std::map (BTreeMap) up to a surprisingly large number of elements despite worse algoritmic complexity because modern CPUs really like scanning through memory sequentially.
6 Likes
Exactly ! I know people that abuse the O(x)-ness of their algorithms without realizing that in real life cache-trashiness is often more important than how many loops you imbricate. Basically once you've pulled a cache line what you do inside it is O(zero), and smart programmers take advantage of that.
6 Likes
This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.