Всем привет!
Недавно участнику 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++.
распараллеливание: помните задачи в 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: тур по языку и список литературы (многое просто доступно онлайн). Также буду рад ответить на конкретные вопросы в комментариях.