s3yoonpark's blog

Why is Python faster than C++ in this example?
By s3yoonpark, history, 19 months ago, In English

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?

  • Vote: I like it
  • -29
  • Vote: I do not like it

»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by s3yoonpark (previous revision, new revision, compare).

→ Reply
»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by s3yoonpark (previous revision, new revision, compare).

→ Reply
»
19 months ago, # |
  Vote: I like it +2 Vote: I do not like it

vector in c++, set in python.

You can delete this blog.

→ Reply
  • »
    »
    19 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      19 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 in operation 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.

      → Reply
      • »
        »
        »
        »
        19 months ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        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!

        → Reply