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. Если это будет интересной идеи то разработаю более подробный план и приступлю к реализации.
а почему не проще сделать систему с передачей данных как на ioi/topcoder, а ограничения по времени разными?
Это решит проблему IO но теперь надо компилировать целый проект а не один фаил а значит иметь более сложную проверяющую систему а также такая система может показаться сложной начинающим.
Неясно, как с этим языком сочетаются автоматические оптимизации. Они позволяют ускорять решения в десятки раз.
Например, inlining функций: считать вызов функции за одну операцию или за ноль (потому что можно встроить)? А может вообще в зависимости от количества аргументов? А если функция рекурсивна? Или иногда рекурсивна, а иногда нет?
Или выделение общих подвыражений. Такой код:
считаем за шесть инструкций (четыре бинарных операции и два присваивания) или за пять (потому что закэшировали
a + b
)?Если полностью запретить оптимизации, то будет очень неудобно писать. А если разрешить, то надо либо их явно выписывать, либо не давать точных гарантий на количество инструкций.
А если уж не даём точных гарантий, то можно просто добавить инструментирование в существующие компиляторы, что-то вроде
gprof
— компилятор добавляет счётчики операций в ассемблерные инструкции на этапе компиляции и эти счётчики можно потом изучать.Интересная вопрос про оптимизации. Оптимизации в этом языке не такая продвинутая т.к. он прощает многие вещи. Т.е оптимизатор будет не так сильно влиять и будет только применим топорным оптимизация. Пока я точно не знаю что сможет сделать оптимизатор с учетом разных режимов. В оптимизаторе точно будет кеширование как в вашем примере и замена последовательных выражений над одной переменной в одно. Оптимизатор будет улучшать. Только самое очевидное что сделает его более понятным.
Вызов функции стоит 0 и return стоит 0(операции внутри будут добавлять инструкций). Inline функций не будет т.к. нет нужды.
У интерпретаторах будет команда вывода количества инструкций по строчно и по блокам в виде. Т.е. будет нарисован код с права количество инструкций в ascii или будет плагин в ide показывающий количество инструкций.
Как предполагается написать, например, это на новом языке? Или это будет запрещено и надо изворачиваться, чтобы эффективно делать низкоуровневые вещи?
Если не будет нормального оптимизатора, то программы придется раздувать некрасивым кодом, отнимающим кучу времени, а если будет, то кто (и как) его разработает? Даже у gcc случается такое, а тут что-то новое и сложное, очень сомневаюсь, что выйдет не сильно хуже
Я так понимаю, в большинстве случаев он будет некомпилируемым, ограничения станут маленькими, чтобы не ждать результат по несколько десятков минут, не получится ли так, что не будет возможности увидеть разницу между условно $$$O(N^2)$$$ с константой $$$1/64$$$ и $$$O(NlogN)$$$ с константой 20?
Какой вообще смысл участнику включать условно "режим плюсов", а не "режим питона"? Если окажется меньше действий (за счет оптимизатора, например), то выглядит как будто проблема с преимуществом языков никуда не делась.
Повторю блог по ссылке — количество итераций при том подходе отличается — гарантированные 64 для double и максимальной точности в случае использования этого хака и около 150 при подсчете "по обычному".
Тогда код вида
int s = 0; for (size_t i = 0; i < 100; ++i) { s += a[i] * (i < 50 ? 2 : 1); }
надо разбивать на 2 цикла, чтобы получить меньше действий. Понятно, что в несинтетическом примере может быть "размакаронивание" кода сильно бОльших масштабов__dict__
в язык ввести можно без проблем, раз уж там честная динамическая типизация, None сделать объектом специальной структуры и тд. вообщеИмеет все возможности C++, Java, Python используемые в соревнованиях.
почти что предполагает полную поддержку python кмк, кроме импортов, которые легко добавить и многопоточности, с которой, думаю, тоже можно что-то придумать), а в cython, например, нельзя.Тут скорее про то, что кажется хочется использовать вообще все возможности, какие есть.
Кстати
Передача идет по ссылке или по значению? Как передать по другому? Сколько инструкций в копировании?
Как работает копирование, например,
Как в этом же примере выставить в
x
null/None?В 1 И 2 Я не уверен что это критично.
4 Всеми возможностями не попользуешься, как например пакетный менеджер в питоне или наследование в c++
3 тут будет зависеть от реализации. У меня есть 2 варианта. Первый написать свой интепритатор на плюсах. А второй это взять Jsvascript или Lua (т.к. они очень быстрые) добавить им проверку типов для строгой типизации (typescript XD ) и все остально.
Структуры будут копироваться но можно передать по ссылке используя такой вариант записи ‘func(&type)’ или включить передачу по ссылке по умолчанию.
т.к. решение O(log n) будет подсети O(log n)
это и странно, часто в зависимости от констант какие-то решения могут заходить, а какие-то нет. Некоторые решения n log n будут работать за меньшее число операций чем линейные, и как их тогда сравнивать ?N не будет настолько маленькой
p.s там опечатка подсети -> почти
насколько большой ? можешь ли примерно оценить число операций у какой-нибудь фибоначиевой кучи? и чтобы N действительно стал меньше, чем N log N
Вроде дефолтный пример на это — sparse table
не совсем, прекалк всеравно n log n пилишь ведь , или ты про что?
ну там делают просто $$$10^7$$$ запросов, чтобы было не запихать дерево отрезков, а элементов все равно $$$10^5$$$. Чтобы $$$O(NlogN)$$$ было нормально, а $$$O(QlogN)$$$ было плохо, но $$$O(Q)$$$ нормально