yshen94's blog

performance difference bewteen array and vector
By yshen94, 2 months ago, In English

really curious about the performance difference bewteen array and vector.

for 2023A — Concatenation of Arrays,

I passed the test using array as in #287237470 while failed the test using vector as in #287234748. The error shows "exit code: -1073741819 (STATUS_ACCESS_VIOLATION), checker exit code: 0, verdict: RUNTIME_ERROR"

maybe I am quite new in Codeforces. will be digging deeper into the performance difference.

  • Vote: I like it
  • 0
  • Vote: I do not like it

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

Your cmp function is broken. The comparator should return false on elements that you consider equivalent: it should be return x.x+x.y < y.x+y.y;.

That is probably part of the reason for the runtime error, not some minute performance difference.

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

    You are right, appreciate your explanation. but why cannot I have an equivalent sign?

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

      C++ comparator should define the < sign. Using this, we automatically get the other two cases: x > y = !(x < y) and x == y = !(x < y) && !(x > y)

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

        the comparator issue only applies to vectors right?. in #287237470, it passes with a <=

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

          no, both causes undefined behavior, you just got lucky on the submission with array.

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

          Hacked. The C++ standard requires the comparator to follow strict weak ordering, and violating it is an undefined behavior. I don't exactly know what happens inside the sort function when it's violated, but it seems like it leads to accessing to an out of bound of the range you have given, and it doesn't always cause runtime error. I ran stress testing with your code and found some RT cases but they mostly failed to hack. Trying with almost the same test multiple times worked.

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

I made the same mistake that my comparator returns true if elements are equivalent. After receiving a runtime error I passed the code for ChatGPT for debugging. It immediately pinpointed the bug.. Most of the time, AI tools help me debug really quickly.

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

    why were the first 3 testcases passed successfully?

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

      Might be because equality comparison in never used in these tc

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

        there might be other reasons, because if I test 1 2 2 1 it passes

        → Reply