Блог пользователя Gassa

Автор Gassa, история, 6 лет назад, По-русски

Всем привет!

Недавно участнику 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++.

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

  • Проголосовать: нравится
  • +312
  • Проголосовать: не нравится

»
6 лет назад, # |
Rev. 5   Проголосовать: нравится +8 Проголосовать: не нравится

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

Остается надеяться, что когда-нибудь это внесут в стандарт, здесь блог от авторов, репозиторий с имплементацией.

А еще, судя по этому:

Operations with very long integers. This file is part of GCC.

в GCC уже есть вот этот wide-int. Кто-нибудь знает, как этим пользоваться и возможно ли этим пользоваться? Заголовочный файл, похоже, называется hwint.h.

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    Функции *mpz*, вероятно, обеспечивают интерфейс с библиотекой GMP. В Википедии пишут, что GMP нужна, чтобы собирать GCC.

    Однако GMP не является частью GCC. В любом случае, в нескольких версиях MinGW, которые у меня есть, нету ни wide int-ов, ни функций *mpz*. Так что, скорее всего, они не будут доступны «из коробки» под Windows, то есть, в частности, на Codeforces и Polygon.

    Насколько я знаю, GMP — это стандарт для тех случаев, когда нужна длинная арифметика на C, ну или на любом другом языке, для которого есть обёртка (чтобы вернуться к теме, вот обёртка для D).

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    На самом деле никто не мешает майнтайнерам джаджа сделать доступным для использования 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

    #include <boost/multiprecision/cpp_int.hpp>
    #include <iostream>
    using namespace std;
    using namespace boost::multiprecision;
    
    int main()
    {
        int128_t v = 1;
        for (int i = 1; i <= 30; ++i) { v *= i; }
        cout << v << endl; // 30!
    
        cpp_int u = 1;
        for (int i = 1; i <= 100; ++i) { u *= i; }
        cout << u << endl; // 100!
    }
    
»
6 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

Thanks for sharing about D language but I have to say, seeing that compact solution for 1010A made me question my life decisions.

»
6 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

А нормальная IDE есть?

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    Вроде официальный список здесь: https://wiki.dlang.org/IDEs

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Из сред я использовал Code::Blocks (писали проекты с детьми) и Visual Studio с плагином Visual D (просто проверял, что работает). Более полный список — по ссылке в комментарии выше.

    Но вообще я любитель минималистичных IDE, и обычно пользуюсь Far Manager — текстовый редактор подходит для очень многих языков :) .

»
6 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

What about IDE for this language? Do you have recommendations?

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 :) .

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

»
6 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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.