Блог пользователя CodingKnight

Автор CodingKnight, 4 года назад, По-английски

Hello Codeforces,

It is sometimes required in competitive programming problems at run-time to measure elapsed time between two events on a real-time scale such as milliseconds. It is possible in C++ to do that using the std::chrono library classes and functions. The following is a C++ timer class that simplifies doing this operation.

#include <bits/stdc++.h>
using namespace std;
using namespace chrono;

class timer: high_resolution_clock {
    const time_point start_time;
public:
    timer(): start_time(now()) {}
    rep elapsed_time() const { return duration_cast<milliseconds>(now()-start_time).count(); } };

The timer class inherits the base class std::chrono::high_resolution_clock. A private std::chrono::time_point constant variable start_time is used to store the initial point of time at which the timer object was created using the class constructor function. The class features a constant public member function elapsed_time() whose call returns a non-negative integer which measures the elapsed time in milliseconds since the creation of the timer object.

The following is a sample example for using the timer class.

const int T = 1000;
timer t; // create a timer object

int main() {
    while (t.elapsed_time() < T) {
        // do something
    }
}

Your constructive comments and feedback are welcome and appreciated.

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How can it help in a contest?

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    The while loop in the sample program stops when elapsed time is larger than or equal to T. Suppose that T is set to a value that is slightly smaller than the time-limit for the problem. It should be then possible to guarantee that the submitted solution does not get TLE (Time-Limit Exceed) Verdict.

    • »
      »
      »
      4 года назад, # ^ |
      Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

      How can you guarantee that? Let us suppose on some iteration t.elapsed_time() returned value very close to T, the loop proceeded and resulted in... TLE :)

      Edit: I have just remembered my co-worker argued one day that passed tests == no bugs in a program ;)

      • »
        »
        »
        »
        4 года назад, # ^ |
        Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

        It should be guranteed that TLE is avoided if the upper-bound on the execution time of a single iteration is known, and is less than the time-limit of the problem.

»
4 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Probably the simplest way to kill your solution is to make system function calls in a loop :)

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    It is assumed that the no such call is made intentionally. Nonetheless, the // do something loop block in the sample program should do exit(0), break; or return 0; before the elapsed time reaches T if the solution is found and no further iteration is needed.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I meant _clock::now() (it is resolved into a system function call and you call it regularly in the loop).

      • »
        »
        »
        »
        4 года назад, # ^ |
        Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

        I agree with you. The execution time for each std::chrono::high_resolution_clock::now() function call inside the time_elapsed() function should be much smallar than the lower-bound on the execution time of a single iteration of the // do something block.