4
Anakata
4y

Started with Codeforces. Some solutions in Python exceeded time limit at test #25. Wrote the same code in C++ but this time it exceeded time limit in test #33.

What’s the solution to this ? Replacing cin/cout with scanf/printf doesn’t seem to make much of a difference.

Comments
  • 1
    @pythonInRelay
    What?
    Shouldn't loops vastly outperform Foreach+lambda, at least in most languages?
  • 0
    @M1sf3t
    Well yeah, but it has overhead because of the additional function-calls.
  • 0
    @M1sf3t
    It heavily depends on the optimisations your compiler does,
    But in general, calling a function always adds a certain base-overhead, no matter the function-body because a new stack-frame need to be created, register-state need to be saved and other shit.
    Some compilers might optimise this overhead away, with things like tail-call optimisation.
  • 0
    @M1sf3t For most cases no. Foreach can be done in exactly two CPU cycles, assign item pointer = next pointer; branch if last operation is 0 (worst case there's an extra cycle if the whole thing is not null-terminated). For loop needs to check a whole lot of other things, run a user-defined index increment, check for break or continue, access item based on some index, potentially skip a bunch of items or go back to a skipped item, ...
  • 1
    The biggest problem usually are nested loops in my experience.

    A simple loop vs a lambda should be so little difference that almost anything else should affect it more.

    Make sure to try to meshure exactly where it takes time.
  • 0
    If you're getting a time limit exceeded check your algorithm. The stuff you mentioned makes a minimal difference at best compared to using the right algorithm.
Add Comment