So I am solving question 3 from here https://www.olympiad.org.uk/papers/2016/bio/bio16-exam.pdf
I have two pieces of code, one in Python and one in C++. C++ -> https://pastebin.com/bHkhZcZ6 Python -> https://pastebin.com/8G4BZQx6
Although the both pieces of code seem to be employing the same logic, the Python one seems to be a lot faster than C++.
An example test case could be -> 614700 3643 90149 -> (It should output 18)
Please can someone tell me why this is the case?
Auto comment: topic has been updated by s3yoonpark (previous revision, new revision, compare).
Auto comment: topic has been updated by s3yoonpark (previous revision, new revision, compare).
vector in c++, set in python.
You can delete this blog.
That makes that much of a huge difference? What data structure should be used in c++ then? I already tried using a set, there is no notable performance improvement. https://pastebin.com/F6WBh0YY
c++ std::vector is a dynamically resized contiguous array.
your
find()operation is O(N) for a length-N vector.python set is a hash-set.
your
inoperation is O(1) for a size-N set.there are more nuances to the time complexity of hashing and collisions but for your purposes, yes the lookup for a hashset is much faster.
Oh I see why it would make a difference.
Then, how should I modify my C++ code so that it runs quickly?
EDIT: I used an unordered_set and it worked. Thanks a lot!