The D programming language in competitive programming

Правка en3, от Gassa, 2018-07-28 20:56:37

Hi all!

This post is inspired by a question here which asks yosupo how using the D progamming language compares to using C++. I regularly use D where possible in contests (and problemsetting) since 2014, with some success. So I'd like to share my experience. I'll try to focus on stuff which is important in competitive programming.

The general feeling is as follows. You can write in D as in plain C when you need full control. You can also write more like in Python using the powerful standard library. However, D is a compiled language, so in both cases, the performance is similar to C++. Additionally, when the program is written, it is much easier to debug than a similar program in C++.

For an example, let us look at two solutions of a recent problem. The first solution is written like plain C:

import std.stdio;
int main () {
    int n, m, i;
    double c = 1.0, x;
    scanf ("%d%d", &n, &m);
    for (i = 0; i < n * 2; i++) {
        scanf ("%lf", &x);
        c *= 1 - 1 / x;
    }
    printf ("%.10f\n", c > 0 ? m / c - m : -1);
    return 0;
}

Looks familiar, eh? A very similar solution can be accepted in C if we just change the import line into the respective #include. It is on purpose: the authors tried their best so that, when a C program is compiled with D, it either throws a compile error or works the same.

So, we read 2 * n numbers, transform each x we read into 1 - 1 / x, multiply all results together, and finally, consider two cases.

But we can drop the lower-level stuff, like the for loop and the variables to read and store the intermediate results. Instead, we can write a solution which has more likeness to the text above: read two lines, split them at whitespace characters, transform each string piece into a double, then apply the formula, and after that, fold the resulting sequence by the multiply operation, transforming u, v, w, ... into u·v·w·.... Here's the code:

import std.algorithm, std.conv, std.stdio;
void main () {
    int n, m;
    readf !" %s %s " (n, m);
    auto c = (readln ~ readln)
        .splitter
        .map !(to!double)
        .map !(x => 1 - 1 / x)
        .fold !"a * b";
    writefln !"%.10f" (c > 0 ? m / c - m : -1);
}

A phrase like function !(args1) (args2) is analogous to function <args1> (args2) in C++: the arguments !(args1) are known at compile time, and the arguments (args2) at run time. In particular, this allows readf and writefln to check the types of the arguments at compile time.

Here, we can also note that splitter and map are “lazy” functions, so the compiled code acts in the order similar to the former solution: first makes all transformations with the first number, then with the second one, then multiplies the first one and the second, then takes the third number, and so on.


In D, there is no single mega-idea around which the language is built. Instead, there are plenty of minor features which together mean a world of difference compared to C++ when writing programs. Let us consider a few specific points below.

So, a few advantages:

  • Error checking. Using D, it is much easier to defend against many stupid bugs. For example, array bounds are checked by default, and when run locally, an out-of-bounds access will terminate and tell the line number. However, when compiling with -boundscheck=off, as it is the case on Codeforces, the checks disappear and no longer consume precious time. Another example: if we get a string in the input instead of an integer, the program immediately terminates with a stack trace instead of running further with corrupted data. The convenient debug output of the form debug {writeln (a);}, for mostly any variable a, is also very helpful when debugging (this line will be compiled only with -debug which, again, is turned off on Codeforces server).

  • Style choice. Be it an imperative program, a chain of transformations applied to the data, or metaprogramming, everything is in D from the start. On the contrary, in C++, due to its age and backward compatibility, the authors had to glue the new paradigms together with the ones already established, which harmed the overall usability.

  • Library. The standard library of C++ has weak, cumbersome, and unwieldy parts: string processing, higher order functions, making structures on-the-fly via pair and tuple. Sure, C++ can do anything, but some things are just much more convenient in other languages, D included.

A few bonuses from the library:

  • BigInt: seems like it's got its way into every language except C++.

  • levenshteinDistanceAndPath.

  • parallelism: remember the problems in Google Code Jam or Facebook Hacker Cup where a solution works just a few times slower than needed? We will of course have to separate input and output from the actual solution, but the rest is taken care of with just one magic call to parallel!

  • FFT: not the most optimal implementation, but sometimes sufficient to solve a problem.

A few drawbacks:

Many of the weaknesses have the same nature: the language is not very widespread. It means that the resources spent on compiler, the standard library, and the supporting tools were less by orders of magnitude than for C++.

  • Compiler bugs. Back in 2014, participating in a 5-hour contest, on average, meant I have to write one new bugreport. (On the positive side, imagine the feeling when you say “my program can't be wrong, it's all compiler's fault”, and happen to be right for a change!) Nowadays, there are a lot less bugs, but hitting another one is of course more probable than to find a bug in GCC.

  • Standard library weaknesses. For example, the containers library is somewhat crude: there is a hash table (same as HashMap) and a red-black tree (same as TreeSet), but no convenience wrappers for HashSet and TreeMap. (As is the case with C++, D can do anything, it's just the matter of writing a few more lines and convenience.)

  • Availability at competitions. On the platforms where 10-20 languages are available for solving problems, D is usually present. (By the way, as is the tradition: thanks to MikeMirzayanov! This time for adding and maintaining D on Codeforces.) When there are only few languages, they are most likely a subset of C, C++, Java, Pascal, Python, and maybe the organizers' language of choice. In big important competitions, it is like a chicken-egg problem: as long as there are just a few contestants using D, there is no compelling reason to add it, and as long as the contest does not allow D, there is no compelling reason to learn it.


If you got interested, take a look at the learning resources on D's site: the language tour and the list of books (many of these are just available online). I'd also be glad to answer specific questions in the comments.

Теги dlang

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en5 Английский Gassa 2018-07-30 11:11:21 11 added [cut]
ru4 Русский Gassa 2018-07-30 11:10:48 11 added [cut]
en4 Английский Gassa 2018-07-29 00:31:37 122
ru3 Русский Gassa 2018-07-29 00:29:24 125
en3 Английский Gassa 2018-07-28 20:56:37 0 (published)
ru2 Русский Gassa 2018-07-28 20:56:22 0 (опубликовано)
en2 Английский Gassa 2018-07-28 20:55:22 79
en1 Английский Gassa 2018-07-28 20:54:29 7767 Initial revision for English translation (saved to drafts)
ru1 Русский Gassa 2018-07-28 20:46:53 7706 Первая редакция (сохранено в черновиках)