Всем привет!
Недавно участнику yosupo задали вопрос о том, в чём преимущества языка программирования D в соревнованиях перед языком C++. Я регулярно использую D в соревнованиях (и при подготовке задач) с 2014 года, иногда вполне успешно (например, программа на D принесла мне победу в AZsPCs: Alphabet City). Так что хочу поделиться своим опытом. Постараюсь ограничиться только тем, что имеет значение для соревнований.
Общее ощущение такое. На 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: тур по языку и список литературы (многое просто доступно онлайн). Также буду рад ответить на конкретные вопросы в комментариях.
Остается надеяться, что когда-нибудь это внесут в стандарт, здесь блог от авторов, репозиторий с имплементацией.
А еще, судя по этому:
в GCC уже есть вот этот wide-int. Кто-нибудь знает, как этим пользоваться и возможно ли этим пользоваться? Заголовочный файл, похоже, называется hwint.h.
Функции
*mpz*
, вероятно, обеспечивают интерфейс с библиотекой GMP. В Википедии пишут, что GMP нужна, чтобы собирать GCC.Однако GMP не является частью GCC. В любом случае, в нескольких версиях MinGW, которые у меня есть, нету ни wide int-ов, ни функций
*mpz*
. Так что, скорее всего, они не будут доступны «из коробки» под Windows, то есть, в частности, на Codeforces и Polygon.Насколько я знаю, GMP — это стандарт для тех случаев, когда нужна длинная арифметика на C, ну или на любом другом языке, для которого есть обёртка (чтобы вернуться к теме, вот обёртка для D).
На самом деле никто не мешает майнтайнерам джаджа сделать доступным для использования Boost.Multiprecision и анонсировать это. Тогда в C++, как и бм во всех остальных предоставляемых языках, будет длинная арифметика на той же самой библиотеке GMP/MPIR. Выглядит это примерно так: https://www.boost.org/doc/libs/1_66_0/libs/multiprecision/doc/html/boost_multiprecision/tut/ints/cpp_int.html
Thanks for sharing about D language but I have to say, seeing that compact solution for 1010A made me question my life decisions.
А нормальная IDE есть?
Вроде официальный список здесь: https://wiki.dlang.org/IDEs
Из сред я использовал Code::Blocks (писали проекты с детьми) и Visual Studio с плагином Visual D (просто проверял, что работает). Более полный список — по ссылке в комментарии выше.
Но вообще я любитель минималистичных IDE, и обычно пользуюсь Far Manager — текстовый редактор подходит для очень многих языков :) .
What about IDE for this language? Do you have recommendations?
I myself used Code::Blocks (wrote projects with students) and Visual Studio with Visual D plugin (just checked it works). A more complete list can be found at the language site.
That said, I like minimalist IDEs, and commonly use Far Manager: a text editor suits the majority of possible languages :) .
though poseidon is also a very good choice as it's written in D itself but it's for big projects and is not exactly cross platform(windows/linux) only. i had my numerical computing course in D itself.
Thank you for sharing knowledge about the D on Codeforces. I will use my knowledge and expertise of the D to attract many females and future employers.