Язык D в спортивном программировании

Revision ru1, by Gassa, 2018-07-28 20:46:53

Всем привет!

Недавно участнику yosupo задали вопрос о том, в чём преимущества языка программирования D в соревнованиях перед языком C++. Я регулярно использую D в соревнованиях (и при подготовке задач) с 2014 года, иногда вполне успешно. Так что хочу поделиться своим опытом. Постараюсь ограничиться только тем, что имеет значение для соревнований.

Общее ощущение такое. На D можно писать как на чистом C, когда нужен полный контроль над происходящим. А можно — как на Питоне, используя довольно мощную библиотеку. При этом D — компилируемый язык, так что в обоих случаях производительность сравнима с C++. Кроме того, после написания программы её гораздо проще отладить, чем аналогичную программу на C++.

В качестве примера давайте посмотрим на два решения одной недавней задачи. Первое решение реализуем примерно как на чистом 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;
}

Выглядит знакомо, да? Аналогичное решение можно сдать и на C, если только заменить строчку с import на соответствующий #include. Это не случайно: авторы постарались сделать так, чтобы, если программу, написанную на C, скомпилировать на D, то она либо не скомпилируется, либо будет работать так же.

Итак, мы читаем 2 * n чисел, каждое прочитанное число x преобразуем в 1 - 1 / x, перемножаем все результаты, после чего рассматриваем два случая.

Но можно не заниматься низкоуровневыми вещами типа цикла for, а также переменных для чтения и для хранения промежуточного результата. Вместо этого можно написать решение примерно так, как выглядит текст выше: прочитать две строки, разбить их по пробельным символам, каждый кусочек-строку преобразовать в double, затем преобразовать по формуле, а дальше схлопнуть получившуюся последовательность операцией умножения: из u, v, w, ... сделать u·v·w·.... Вот код:

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);
}

Фраза вида function !(args1) (args2) — это аналог function <args1> (args2) на C++: аргументы !(args1) известны во время компиляции, а аргументы (args2) — во время работы программы. Это, в частности, позволяет readf и writefln проверить соответствие типов ещё на стадии компиляции.

Здесь можно ещё заметить, что splitter и map — «ленивые» функции, и скомпилированный код делает операции примерно в том же порядке, что и выше: сначала производит все преобразования с первым числом, потом со вторым, потом перемножает первое и второе, потом берёт третье, и так далее.


У D нет какой-то одной мега-идеи, вокруг которой бы строился язык. Вместо этого есть много мелочей, которые, впрочем, в сумме дают совершенно отличное от C++ ощущение при написании программ. Разберём дальше несколько конкретных пунктов.

Итак, несколько преимуществ:

  • Поиск ошибок. Используя D, гораздо легче защититься от многих глупых багов. Например, по умолчанию проверяется выход за границы массива, и при локальном запуске программа от такого вылетит и сообщит номер строки. Вместе с тем, при компиляции с -boundscheck=off, как настроено на Codeforces, проверки исчезают и перестают тратить время. Другой пример — при вводе строки вместо целого числа программа падает с ошибкой и стек-трейсом, а не тихо работает дальше с неизвестно какими данными. Удобный отладочный вывод вида debug {writeln (a);} для более-менее любой переменной a тоже хорошо помогает при отладке (эта строчка будет скомпилирована только с -debug, который, опять же, выключен на сервере Codeforces).

  • Выбор стиля. Обычная императивная программа, цепочка преобразований над входными данными, метапрограммирование — всё это есть в D изначально. В C++ же, в силу возраста и обратной совместимости, авторам пришлось приклеивать новые парадигмы к уже существующим, что сказалось на их итоговом удобстве.

  • Библиотека. У стандартной библиотеки C++ есть слабые, громоздкие и неудобные места: работа со строками, функции высшего порядка, создание структур на лету при помощи pair и tuple. Конечно, C++ может всё, но некоторые вещи в других языках, включая D, гораздо удобнее.

Несколько бонусов из библиотеки:

  • BigInt: кажется, он есть уже во всех языках, кроме C++.

  • levenshteinDistanceAndPath.

  • распараллеливание: помните задачи в Google Code Jam или Facebook Hacker Cup, в которых решение работает всего в несколько раз дольше, чем нужно? Конечно, придётся отделить от решения ввод и вывод, но остальное делается одним волшебным вызовом parallel!

  • FFT: не самая оптимальная реализация, но иногда позволяет сдать задачу.

Несколько недостатков:

Многие недостатки имеют одну и ту же природу: язык не очень широко распространён. Это означает, что и на компилятор, и на стандартную библиотеку, и на сопутствующие инструменты пришлось на порядки меньше ресурсов, чем для C++.

  • Баги компилятора. Давным-давно, в 2014 году, участие в пятичасовом соревновании в среднем означало, что я должен написать один новый багрепорт. (Зато представьте то чувство, когда говоришь «моя программа не может быть неправильной, это всё компилятор виноват», и наконец оказываешься прав, а не как обычно!) Сейчас багов стало существенно меньше, но напороться на них, конечно, всё равно проще, чем найти баг в GCC.

  • Слабые места стандартной библиотеки. Например, структуры данных довольно сырые: есть хеш-таблица (аналог HashMap) и красно-чёрное дерево (аналог TreeSet), но нет удобных обёрток для HashSet и TreeMap. (Как и C++, D может всё, вопрос в нескольких лишних строках и удобстве.)

  • Доступность на соревнованиях. На онлайн-платформах, где решения можно сдавать на 10-20 языках, язык D обычно есть. (Кстати, соблюдём традицию: спасибо MikeMirzayanov! На этот раз за добавление и поддержку языка D на Codeforces.) Когда языков всего несколько, обычно это какое-то подмножество C, C++, Java, Pascal и Python — и ещё, может быть, любимый организаторами язык. На больших и важных соревнованиях это похоже на проблему курицы и яйца: пока на соревнованиях мало участников, использующих D, нет особого стимула его добавлять, а пока на языке D нельзя послать решение, нет особого стимула его изучать.


Если заинтересовались — взгляните на учебные ресурсы на сайте D: тур по языку и список литературы (многое просто доступно онлайн). Также буду рад ответить на конкретные вопросы в комментариях.

Tags dlang

History

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