Jun 12, 2017

Codility: Does the Technology Influences the Score?

How fair is the Codility's score system when the same algorithm is implemented using a fast and slow technology like C++ and JavaScript ? look here the test.

C++ is faster than JavaScript for many reasons, perhaps the biggest is due to the fact that C++ code is compiled into CPU instructions and then executed. JavaScript on the other hand is interpreted, so there are more layers between the code and CPU execution, and this consequently takes more time.

Are C++ developers getting higher scores in the same problem in comparison with the JavaScript ones for the same algorithm? the short answer is no! and this is great! but in some cases... perhaps!

A test was done using the MaxCounters problem, you can check it here. The same algorithm was implemented using C++ and JavaScript and submitted two times, as follows:

JavaScript


function solution(N, A) {
        var counters = new Array(N).fill(0);
 var biggest = 0;

 for (var x = 0; x < A.length; x++) {
  if (A[x] <= N) {
   counters[A[x] - 1]++;
   if (biggest < counters[A[x] - 1])
    biggest = counters[A[x] - 1];
  } else
   counters.fill(biggest);
 }

 return counters;
}

C++


#include <iostream>
#include <vector>
using namespace std;

vector<int> solution(int N, vector<int> A) {
 vector<int> counters (N);
 int biggest = 0;

 for (int x = 0; x < A.size(); x++) {
  if (A[x] <= N) {
   counters[A[x] - 1]++;
   if (biggest < counters[A[x] - 1])
    biggest = counters[A[x] - 1];
  } 
  else
   fill (counters.begin(),counters.end(),biggest);
 }
 
 return counters;
}

The algorithm is not the best in terms of performance, because this way we could see how much time it took and the maximum allowed by Codility for the problem. And here is the short answer, both got the same score:


That is great, so the score system is fair, right? Let's analyze a little more:

JavaScript - First and Second submission result



As we can see, on the first submit the Codility's server took 2.12s to run and on the second 2.13s. The large_random2 test uses random numbers, and also the server may be overloaded with many others tests, so it's normal to change a little bit the execution time, although the 0.99s limit seems to remain the same. But on the extreme_large test we can see that the Codility's score system somehow compensates that 'slow execution moment' on the server, raising the limit from 1.02s to 1.04s, which is nice/fair. Now let's see how the C++ performed:


A similar situation happens here, at the first submission the Codility's server took 3.73s to execute the extreme_large test versus 3.70s on the second try, but pay attention to the large_random2 test, now things get very interesting, the algorithm reproved due to 0.02s (total 0.13s) slower than the 0.11s maximum limit, and the difference between the extreme_large tests was 0.03s, but the limits seems to not change for the C++ test.

Conclusion

As expected C++ performs faster than JavaScript, and the Codility's score system seems to compensate their servers performance when evaluate the tests raising the limits applied to each performance test, at least for the JavaScript language. 

When the slow or just not the best approach is used in slow languages like JavaScript the difference between the execution time and the maximum allowed for the test are high, so you can easily say 'yes, my algorithm sucks', but on the other hand, for the C++ tests, the difference between the 'slow/not the best' approach were just 20 milisencods. Perhaps 20ms couldn't be a problem if you get a server with low execution time and pass the test? we could take advantage of this to score better than other languages? the random numbers tests can take 20ms less and pass the test? well, it's a possibility, so... who knows?!

0 comentários :

Post a Comment