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

Автор ruslanjan, история, 4 года назад, По-русски

Tекущие языки по типу C++, Java или Python создавались не для олимпиад и уж точно не для точной оценки решения системой. Помимо того что эти языки разные (скорость, наличие или отсутствие управление памяти) они еще и несут за собой багаж функции которые вовсе не нужны для олимпиад, к примеру импортирование библиотек (C++, Python, Java), пакеты (Java с ее package) и т.п.

В чем же проблема?

Не так просто придумать задачу в которой ни один язык не будет иметь преимущества (Обычно на это забивают взяв C++ за основу). Сделаете задачу на длинку тогда Python и Java будет иметь преимущество а участники с плюсами будут лишние минуты тратить на реализацию или дали задачу которая требует аккуратно реализации привет java. И таких примеров много, можно сказать что каждый язык это инструмент и нужно подбирать для задачи нужный но будем реалистичнее многие машинально выучили свои шаблоны для алгоритмов и оптимизации (например cin.tie(NULL) в C++ или реализация своего ридера в java) и они не могут быть перемещены между языками уж слишком они различны.

Это не только проблема участников

Помимо жури также страдают и создатели систем тестирование. Запуск чужого кода на языке не рассчитанного на запуск в песочнице как javascript создает проблемы с безопасностью в тестирующих системах и не легкой задачей подсчета памяти и времени. Об уязвимостях можно писать отдельную статью, так что вот неполный список с чем надо бороться: Бесконечна компиляция (в C++, да есть такой баг), Создание потоков, Создание подпроцессов, Выход в интернет, Доступ к файлам, Превышение Памяти. Каждый из них может уронить воркер, систему или даже получить решение. Это крайне сложная задача

Эти языки не пригодятся

Вы будите правы сказав что эти языки применяют однако как их используют в соревновательном программирование ни как не подходит для проектов, например в C++ никто не заботится о освобождению памяти. В итоге придется учить язык как будто сначала. Изучается только то что необходимо для олимпиад (но все равно это даст буст в программирование).

Все прогают на C++ какая разница?

Если вы пишите на C++ тогда сразу читайте "Рецепт панацеи". Для вас будет не разница а больше возможностей :)

Рецепт панацеи

Панацея — Новый язык, специально разработанный для соревнование который будет включать возможности многих языков. Вот вам его код решения возведения в степень.

Основная идея

// Вообще STRONG_TYPING включен по умолчанию
#enable STRONG_TYPING
#define ll int

int bp(int a, int b) {
    if (!b)
        return 1;
    if (b&1)
        return a;
    int x = bp(a, b/2);
    return x*x;
}

int p, q;
scanf("%d %d", &p, &q);
printf("%d", bp(p, q));

Кажется знакомым? Синтаксис будет взят у C++ и Java (Питонщики не расстраивайтесь :3 ). Ключевой идей будет #enable этот препроцессор будет задавать какой режим или функция будут использоваться программой к примеру будет ли она строго типизированная или динамическая. По сути собирая набор #enable вы получаете свой язык для решения конкретной задачи.

Список режимов и доступных(Будет дорабатываться):

  • #enable FUCNTIONAL_PROGRAMMING — Функции становятся не мутабельны т.е. нельзя изменить передаваемую переменную. Некоторые встроеные функции становятся не доступными (их заменяют другие) Когда нужно писать аккуратно.
  • #enable DYNAMIC_TYPING — нельзя влючать одновременно с STRONG_TYPING.
  • #enable STRONG_TYPING — включен по умолчанию.
  • #enable NO_TYPE_CONVERSION — не будет приведение типов — 1.0 + int(2) -> error. Когда нужно писать очень аккуратно
  • #define так же доступен

Пример с динамической типизацией:

#enable DYNAMIC_TYPING

// в DYNAMIC_TYPING можно указать тип если вы к примеру перешли с из STRONG_TYPING в DYNAMIC_TYPING
def bp(a, int b) { // def нужен что бы указать что это функция но (int bp()) тоже правильно
    if (!b)
        return 1;
    if (b&1)
        return a;
    let x = bp(a, b/2); // let - объявление переменной
    return x*x;
}

let p, q;
p = int(readItem()) // Функция считывает до пробела или переноса и возвращает `String`
q = int(readItem())
print(bp(p, q));

Как оценивать? Он же будет медленным

Да возможно будет но мы больше не будет оценивать время, теперь мы будем оценивать количество инструкций т.к. наш язык будет работать на виртуальной машине. А об этом подробнее в Структуре языка

Структура языка Кратко

  • Нету компиляции только проверка типов
  • объекты и примитивы
  • возможность создавать свои структуры через struct Type {}
  • встроеные api функции для io
  • встроенная библиотека std с реализованными алгоритмами как в c++ написанная на этом же языке
  • Управление памятью как C++. Режимы и дополнительные функции например динамической типизации доступные через препроцессор #enable THING
  • Имеет все возможности C++, Java, Python используемые в соревнованиях.
  • Возможность писать богатые чекеры, интеракторы а также дополнительные функции для конкретной задачи
  • У каждой операцией над примитивами будет свой вес а их сумма количество инструкций. например int + int имеет вес 1 а int/int имеет вес 2.

Преимущества

  • На много безопаснее для системы чем C++. можно сказать что полностью но багов никто не отменял
  • Система будет намного быстрее без проверок безопасности и компиляции.
  • Возможность соревноваться по количеству инструкций а так же ставить балы по ним. Как в игре "TIS-100"
  • Возможность писать богатые чекеры, интеракторы а также дополнительные функции для конкретной задачи. Это сделает задачи более интересными и даст больше свободы авторам задач
  • Использовать лучшее от всех языков.
  • Сразу понятен тем кто пишет на java или c++.
  • С++ код будет почти валидным.
  • Решения не будет страдать от Wall Time Limit
  • В количество инструкций будет входить только ваше решение, IO не будет учитываться как многие другие вещи вне вашем контроле в других языках.

Итог

Возможно отдельный язык покажется лишним но для проверяющих систем это будет больший прыжком в качестве тестирования.

P.S. Это черновик нового языка. Идеи предложения принимаются.

P.S.S. Если это будет интересной идеи то разработаю более подробный план и приступлю к реализации.

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

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

а почему не проще сделать систему с передачей данных как на ioi/topcoder, а ограничения по времени разными?

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

    Это решит проблему IO но теперь надо компилировать целый проект а не один фаил а значит иметь более сложную проверяющую систему а также такая система может показаться сложной начинающим.

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

Неясно, как с этим языком сочетаются автоматические оптимизации. Они позволяют ускорять решения в десятки раз.

Например, inlining функций: считать вызов функции за одну операцию или за ноль (потому что можно встроить)? А может вообще в зависимости от количества аргументов? А если функция рекурсивна? Или иногда рекурсивна, а иногда нет?

Или выделение общих подвыражений. Такой код:

int x = (a + b) / 2;
int y = (a + b) * 2; 

считаем за шесть инструкций (четыре бинарных операции и два присваивания) или за пять (потому что закэшировали a + b)?

Если полностью запретить оптимизации, то будет очень неудобно писать. А если разрешить, то надо либо их явно выписывать, либо не давать точных гарантий на количество инструкций.

А если уж не даём точных гарантий, то можно просто добавить инструментирование в существующие компиляторы, что-то вроде gprof — компилятор добавляет счётчики операций в ассемблерные инструкции на этапе компиляции и эти счётчики можно потом изучать.

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

    Интересная вопрос про оптимизации. Оптимизации в этом языке не такая продвинутая т.к. он прощает многие вещи. Т.е оптимизатор будет не так сильно влиять и будет только применим топорным оптимизация. Пока я точно не знаю что сможет сделать оптимизатор с учетом разных режимов. В оптимизаторе точно будет кеширование как в вашем примере и замена последовательных выражений над одной переменной в одно. Оптимизатор будет улучшать. Только самое очевидное что сделает его более понятным.

    Вызов функции стоит 0 и return стоит 0(операции внутри будут добавлять инструкций). Inline функций не будет т.к. нет нужды.

    У интерпретаторах будет команда вывода количества инструкций по строчно и по блокам в виде. Т.е. будет нарисован код с права количество инструкций в ascii или будет плагин в ide показывающий количество инструкций.

»
4 года назад, # |
Rev. 2   Проголосовать: нравится -8 Проголосовать: не нравится
  1. Как предполагается написать, например, это на новом языке? Или это будет запрещено и надо изворачиваться, чтобы эффективно делать низкоуровневые вещи?

  2. Если не будет нормального оптимизатора, то программы придется раздувать некрасивым кодом, отнимающим кучу времени, а если будет, то кто (и как) его разработает? Даже у gcc случается такое, а тут что-то новое и сложное, очень сомневаюсь, что выйдет не сильно хуже

  3. Я так понимаю, в большинстве случаев он будет некомпилируемым, ограничения станут маленькими, чтобы не ждать результат по несколько десятков минут, не получится ли так, что не будет возможности увидеть разницу между условно $$$O(N^2)$$$ с константой $$$1/64$$$ и $$$O(NlogN)$$$ с константой 20?

  4. Какой вообще смысл участнику включать условно "режим плюсов", а не "режим питона"? Если окажется меньше действий (за счет оптимизатора, например), то выглядит как будто проблема с преимуществом языков никуда не делась.

  • »
    »
    4 года назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится
    1. Оценивается не скорость а количество инструкций. Прошу заметить не ассемблерных а скорее вес каждой операции. Вам не придётся писать низкоуровневые вещи т.к. решение O(log n) будет почти O(log n).
    2. Оптимизатор будет но он будет по проще но не в ущерб решениям. Если ваше решение O(n) оптимизатор не сделает магическое O(1). Набор оптимизации будет только оптимизировать базовые вещи на первый этапах языка. Например кешировать уже вычисленные выражения, сокращение выражений и т.п.
    3. если он не компилируемый не значит что он медленный. JavaScript вполне себе быстрый.
    4. Разница в том что теперь все возможности есть у одного языка. Посети вы будете пенять правила языка под себя. В C++ нельзя включить динамическую типизацию, придётся учить другой язык (python)
    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится -8 Проголосовать: не нравится
      1. Повторю блог по ссылке — количество итераций при том подходе отличается — гарантированные 64 для double и максимальной точности в случае использования этого хака и около 150 при подсчете "по обычному".

      2. Тогда код вида int s = 0; for (size_t i = 0; i < 100; ++i) { s += a[i] * (i < 50 ? 2 : 1); } надо разбивать на 2 цикла, чтобы получить меньше действий. Понятно, что в несинтетическом примере может быть "размакаронивание" кода сильно бОльших масштабов

      3. То есть ни ограничения, ни рантайм существенно не изменятся? Звучит фантастично, конечно, потому что выглядит, как будто просто написать транслятор питона в этот язык можно (ну потому что условные __dict__ в язык ввести можно без проблем, раз уж там честная динамическая типизация, None сделать объектом специальной структуры и тд. вообще Имеет все возможности C++, Java, Python используемые в соревнованиях. почти что предполагает полную поддержку python кмк, кроме импортов, которые легко добавить и многопоточности, с которой, думаю, тоже можно что-то придумать), а в cython, например, нельзя.
      4. Тут скорее про то, что кажется хочется использовать вообще все возможности, какие есть.

      Кстати

      def f(a) {
      //
      }
      Type type;
      f(type);
      

      Передача идет по ссылке или по значению? Как передать по другому? Сколько инструкций в копировании?

      Как работает копирование, например,

      struct Type2 {
      Type1 x;  // Тоже структура
      y;  // Нестрого типизированное поле
      };
      
      Type2 value;
      value.z = Type();  // Еще одно поле, которого нет определения
      

      Как в этом же примере выставить в x null/None?

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

        В 1 И 2 Я не уверен что это критично.

        4 Всеми возможностями не попользуешься, как например пакетный менеджер в питоне или наследование в c++

        3 тут будет зависеть от реализации. У меня есть 2 варианта. Первый написать свой интепритатор на плюсах. А второй это взять Jsvascript или Lua (т.к. они очень быстрые) добавить им проверку типов для строгой типизации (typescript XD ) и все остально.

        Структуры будут копироваться но можно передать по ссылке используя такой вариант записи ‘func(&type)’ или включить передачу по ссылке по умолчанию.

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

      т.к. решение O(log n) будет подсети O(log n) это и странно, часто в зависимости от констант какие-то решения могут заходить, а какие-то нет. Некоторые решения n log n будут работать за меньшее число операций чем линейные, и как их тогда сравнивать ?

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

        N не будет настолько маленькой

        p.s там опечатка подсети -> почти

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

          насколько большой ? можешь ли примерно оценить число операций у какой-нибудь фибоначиевой кучи? и чтобы N действительно стал меньше, чем N log N

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

            Вроде дефолтный пример на это — sparse table

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

              не совсем, прекалк всеравно n log n пилишь ведь , или ты про что?

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

                ну там делают просто $$$10^7$$$ запросов, чтобы было не запихать дерево отрезков, а элементов все равно $$$10^5$$$. Чтобы $$$O(NlogN)$$$ было нормально, а $$$O(QlogN)$$$ было плохо, но $$$O(Q)$$$ нормально