Timing A Function in C++

Recently, I encountered the following question:

Write a function that returns true if it has been called 3 times in 3 seconds.

I have used a traditional C-style approach (in C++) without using a queue:

#include<iostream>
#include<ctime>
#include<unistd.h>

using namespace std;

time_t start;
int count;

bool being_called(time_t call_time) {
	count++;
	if (call_time - 3 <= start) {
		return !(count < 3);
	} else {
		start = call_time;
		count = 1;
		return false;
	}
}

int main() {
	start = time(NULL);
	cout << boolalpha << being_called(time(NULL)) << endl;
	cout << boolalpha << being_called(time(NULL)) << endl;
	cout << "=====" << endl;
	sleep(4);
	cout << boolalpha << being_called(time(NULL)) << endl;
	cout << boolalpha << being_called(time(NULL)) << endl;
	cout << boolalpha << being_called(time(NULL)) << endl;
	cout << boolalpha << being_called(time(NULL)) << endl;
	return 0;
}

This works perfectly well and it actually solves the problem. However, there are other alternatives.

Precision

time_t time (time_t* timer) returns a Unix time, which is simply an integer value. Since it is an integer, $t = 1.0001$ would be recorded in the same way as $t = 1.9888$. This is not very good as if we call the function at $t_1 = 0.011$, $t_2 = 3.511$, $t_3 = 3.611$, then the function returns true and the flaw is obvious. This is verified in the last section.

This can be solved with a int gettimeofday(struct timeval *tv, struct timezone *tz) in sys/time.h. The struct timeval *tv contains seconds and microseconds of the current time. The precision is slightly improved, despite the fact that there will still be some errors when dealing with doubles.

A Better Approach

To solve this, we can use a queue for this problem by checking the size of the queue and popping an element if the time created is more than 3 seconds ago. While this may be solved without a queue, this data structure is the right choice here. I could have used chrono and a queue<high_resolution_clock::time_point>. chrono has extremely rich functionality compared to ctime.

#include<iostream>
#include<chrono>
#include<thread>
#include<queue>

using namespace std;
using namespace std::chrono;

queue<high_resolution_clock::time_point> call_queue;

bool being_called(high_resolution_clock::time_point call_time) {
	call_queue.push(call_time);
	while(duration_cast<seconds>(call_time - call_queue.front()).count() > 3) {
		call_queue.pop();
	}
	if (call_queue.size() >= 3) {
		return true;
	}
	return false;
}

int main() {
	using namespace literals::chrono_literals;
	high_resolution_clock c;
	cout << boolalpha << being_called(c.now()) << endl;
	cout << boolalpha << being_called(c.now()) << endl;
	cout << "=====" << endl;
	this_thread::sleep_for(4s);
	cout << boolalpha << being_called(c.now()) << endl;
	cout << boolalpha << being_called(c.now()) << endl;
	cout << boolalpha << being_called(c.now()) << endl;
	cout << boolalpha << being_called(c.now()) << endl;
	return 0;
}

One should notice that C++14 is required to access std::literals::chrono_literals. There is a difference between a duration cast and plain duration. duration<double, milli>, for example, requires a milli ratio type to process the time. On the other hand, duration cast is useful for getting the whole integral number of seconds of time, like the above case. For a better precision, we can do the following.

bool being_called(high_resolution_clock::time_point call_time) {
	call_queue.push(call_time);
	while (duration<double, milli>(call_time - call_queue.front()).count() > 3000.0) {
		call_queue.pop();
	}
	if (call_queue.size() >= 3) {
		return true;
	}
	return false;
}

Verifying the Guess

Previously, we made the following guess:

This is not very good as if we call the function at $t_1 = 0.011$, $t_2 = 3.511$, $t_3 = 3.611$, then the function returns true and the flaw is obvious.

#include<iostream>
#include<chrono>
#include<thread>
#include<queue>

using namespace std;
using namespace std::chrono;

queue<high_resolution_clock::time_point> call_queue;

bool being_called(high_resolution_clock::time_point call_time) {
	call_queue.push(call_time);
	while (duration<double, milli>(call_time - call_queue.front()).count() > 3000.0) {
		call_queue.pop();
	}
	if (call_queue.size() >= 3) {
		return true;
	}
	return false;
}

int main() {
	using namespace literals::chrono_literals;
	high_resolution_clock c;
	cout << "=====" << endl;
	this_thread::sleep_for(11ms);
	high_resolution_clock::time_point t = c.now();
	cout << boolalpha << being_called(c.now()) << endl;
	cout << "=====" << endl;
	this_thread::sleep_for(3500ms);
	cout << boolalpha << being_called(c.now()) << endl;
	cout << "=====" << endl;
	this_thread::sleep_for(100ms);
	cout << boolalpha << being_called(c.now()) << endl;
	cout << "=====" << endl;
	cout << "Time elapsed: " << 
		duration<double, milli>(c.now() - t).count() << "ms" << endl;
	return 0;
}

=====
false
=====
false
=====
false
=====
Time elapsed: 3624.28ms