Спор между "так символов меньше" + "программисту очевидно" + "незачем усложнять язык" и "строгая типизация лучше слабой" + "больше проверок компиляции лучше" + "код гораздо больше читается, чем пишется" можно продолжать бесконечно.
Я вот во втором лагере. Данный пример вижу так:
Если вы не используете венгерскую нотацию в том или ином виде, то там будет не number, а какое-нибудь другое название.
Например, есть ли ошибка в следующем коде, если он компилируется и не падает?
long long timeout_min =
((long long)read_config("timeout_sec") + 59) / 60;
Ответ: а фиг его знает.
Если там возвращается double (потому что в JSON только вещественные числа) — то, наверное, тут хотели округлить секунды вверх до минут. А вот если там случайно возвращается сишная строка, то вы только что взяли в качестве количества секунд значение указателя. И никаких предупреждений компилятора не получили даже на самом высоком уровне предупреждений.
Разумеется, если протестируете, что таймаут у вас корректно работает, вы сразу обнаружите ошибку. Если протестируете. Или хотя бы выведете на экран.
Но тогда, мне кажется, почём зря приближаемся к другому краю спектра с полным отключением статического анализа типов, как в Python. Да, можно код протестировать, но мне больше нравится получать ошибки компиляции, даже если приходится больше набирать или больше думать.
> И совсем уж нубовский вопрос: какое такое сакральное преимущество даёт C++ системном программировании что бы это нельзя было сделать на си?
Ни один язык не даёт сакральных преимуществ над другим. Даже если (что не так в случае Си и C++) является строгим надмножеством другого; не всегда больше возможностей — это хорошо.
А конкретная команды в конкретном проекте делает выбор, исходя из ситуации. Язык, тулчейн, стиль кода, архитектура...
Код соответствует стандарту С++, если он компилируется компилятором С++.
Каким из компиляторов? Они, бывает, отличаются и добавляют свои собственные расширения. А ещё поведение отличается между ОС, потому что помимо компилятора есть стандартная библиотека и протекающие абстракции.
Уточнение к любым моим советам из интервью: они, конечно же, в основном основаны на моём опыте. Мне много где сильно повезло с обстоятельствами. Если у вас другие обстоятельства, какие-то мои рекомендации могут оказаться лично вам даже вредны (sic!)
Например, я слышал мнение, что олимпиады (не только школьные) как социальный лифт работают гораздо лучше и надёжнее, чем попытки пробиться на зарубежные стажировки и устроиться хоть на какую-нибудь позицию в какие-то случайные компании в небольшом городе. Не уверен, что услышал правильно, но звучит правдоподобно.
А именно - прёмная комиссия ВУЗа на основании результатов ЕГЭ абитуриента приняла решение о том, что человек соответствует тому, чтобы обучаться в ВУЗе, способен усвоить учебную программу, и стать специалистом при условии прохождения учебной программы;
Приёмная комиссия ВУЗа (если речь про бакалавриат) никаких решений уже давно не принимает. За год (или чуть меньше) до поступления публикуется список льгот, которые дают различные олимпиады, список необходимых ЕГЭ — всё. Летом просто сортируются публичные списки подавших документы по определённым правилам и зачисляются верхние строчки, пока не закончатся места.
Есть, конечно, небольшие тонкости с несколькими волнами (в прошлые годы), онлайн-согласиями на зачисление (последние два года), а также иностранными студентами, целевыми местами и местами по особой квоте, но принципиально картина не меняется: вуз юридически никак не может влиять на то, поступит к ним конкретный человек или нет.
Если не ошибаюсь, только два вуза могут проводить собственные экзамены — МГУ и СПбГУ, причём делает это только МГУ. Плюс можно проводить отдельный конкурс на "творческие специальности", куда программирование не относится. Некоторые вузы (вроде МФТИ) устраивают "собеседование" с абитуриентами, но это юридически не влияет на то, будет ли студент зачислен на определённую программу обучения. Вот что там происходит с разделением на потоки/группы внутри программы или будут ли на собеседовании переубеждать поступить в другое место (это я уже фантазирую) — другое дело.
во-первых, какой смысл в печати числа, занимающего несколько страниц? Человек все равно его воспринимает лишь на уровне "ух, какое большое".
Для развлечения или сверки реализации с какой-нибудь эталонной. Наверное, для принятия бизнес-решений действительно не нужно больше десятка-другого точных знаков, хотя я не специалист.
во-вторых, библиотека GMP, которую уже упоминали в комментариях, доступна и в питоне.
Так я же не против библиотек. Я против догмы "в двоичной системе всё точно будет быстрее" — нет, не всегда будет.
Сравнение длин там нужно не для скорости, а для корректности: короткое число 99 меньше длинного 123, хотя лексикографически оно больше. Числа, записанные как строчки, надо сравнивать не совсем лексикографически.
Обычно все-таки вывод занимает незначительную долю в тех расчетах, для которых требуется bignum.
Да, зависит от задачи, всё верно.
И почему тормозит вывод еще нужно смотреть
Он не просто тормозит, он у меня минуту работает. А вот если выводить как print(bin(x)) — то пару секунд.
Я не спец в CPython, но файл с названием longintrepr выглядит многообещающе: вот тут нам сообщают, что всё действительно хранится в двоичной системе счисления (точнее, с основанием 2**30), а вот тут парой вложенных циклов переводят число из одной системы счисления в другую перед выводом в строку. Даже на Кнута сослались.
Вывод: вывод длинного числа в CPython работает за квадратичное от длины числа время. 10**12 операций — это не шутка, даже если соптимизировать в десяток-сотню раз.
Красивое элегантное решение, но оно мне не подойдёт, так как приходится сравнивать числа поцфыорно (если можно так сказать).
Можно в цикле то же самое написать. Ну и раз уж у вас всё равно цифры хранятся как строчки — то можно сначала сравнить по длине, а потом просто как строчки при помощи <, он поддерживается std::string. Правда, тут надо аккуратно с инвариантами.
Если у меня задача, в которой надо зачем-то посчитать большое десятичное число (обычно в развлекательных/учебных целях), то перестаёт устраивать, потому что у меня перестаёт работать вывод ответа на экран. Например, запустите на питоне вот такой код:
x = 10 ** 1000000 + 4
print(x % 10)
print(x)
Само число x из миллиона знаков посчиталось быстрее, чем за секунду, равно как и его остаток от деления на 10. А вот вывод этого числа целиком занимает некоторое время, потому что идёт перевод из двоичной системы в десятичную неэффективным способом.
Школа — она про многостороннее развитие и социализацию.
Очень сильно зависит от школы. И социализация тоже очень зависит от того, с кем именно социализируешься. У меня в трёх школах (включая, кстати, очень счастливо законченный десять лет назад экстернат) были довольно разные коллективы. В кружах тоже разные коллективы. В разных лагерях — разные традиции. В ЛКШ по вечерам одним способом треплются, в матлагере другим, в смене "Орлёнка" — про третье.
Это очень круто и интересно, но нельзя жить одним.
Мне кажется, гореть в первую очередь программированием очень даже можно. Какие-нибудь хобби при этом — вещь безусловно полезная, тут согласен.
Мне кажется, в реализации много мест, которые можно и нужно сделать гораздо аккуратнее. Даже если считать, что хранение по десятичным разрядам — это окей с точки зрения быстродействия и поддержания инвариантов.
Из алгоритмического:
Убрать поле _size — либо оно всегда равно _value.size(), либо это что-то непонятное. Незачем усложнять инвариант класса. Можно забыть случайно обновить, а так код короче станет.
Строго описать допустимые комбинации значений для оставшихся полей. При наивной реализации очень легко огрести от ведущих нулей, знакового нуля, вычитания чисел похожей длины.
Из C++-специфичного:
Использовать member initialization list в конструкторе вместо переприсваивания полей.
Не начинать переменные с _ — это допустимо для полей, но, например, для глобальных переменных — неопределённое поведение (undefined behavior, UB).
Принимать строки по константным ссылкам, где можно. Или по значению и перемещать. В конструкторе, например, сейчас лишнее копирование.
Можно сделать user-defined literal.
Для тестов удобно взять какую-нибудь библиотеку юнит-тестов вроде onqtam doctest.
Дальше посмотрел на код вашей библиотеки на GitHub:
Вместо своих методов swap можно использовать стандартный std::swap. К тому же их совершенно незачем делать методами, могли бы быть свободными функциями, причём видимыми только внутри .cpp. А для этого их стоит заключить в unnamed namespace.
Функцию сравнения чисел можно написать гораздо короче и проще, если использовать паттерн вроде if (x != y) return x < y;.
Кажется, что есть много дублирования кода между разными функциями сравнения, сложения и вычитания. Концептуально случаев очень мало, но у вас, мне кажется, многовато получилось.
Если основывать на системе счисления, не являющейся степенью десятки, то придётся переводить в десятичную систему и обратно. Наивный подход будет работать за квадратичное время, получим как в Python или Java: вычисления мгновенные, а вот вывод числа на миллион разрядов невозможен. Является ли это проблемой — зависит от задачи.
Как я понял — нет, потому что компилятор попытается соптимизировать цикл целиком, распределить регистры автоматически и не справится догадаться, как лучше. А если делаем через функции, то это форсирует нахождение первых аргументов в определённых регистрах (по ABI), что является нехилой подсказкой.
Жаль, что ничего не упомянули про машинное обучение в целом. Хотя бы на уровне "garbage in, garbage out", сбора и чистки данных, разделения train/test/cross-validation. А без этого заниматься нейросетями очень странно, мне кажется.
"Нейросеть" — это же вообще не главное, хотя и звучит из каждого утюга. Это лишь один из доступных инструментов машинного обучения. Если просто взять нейросеть и попытаться как-то самостоятельно впихнуть в случайную задачу вроде распознавания рукописных цифр (особенно не зная слова "MNIST"), то наверняка ничего не получится.
Я вот лет десять назад прочитал про нейросети, закодил, сделал очень большой (как мне казалось) набор из целых десять примеров на каждую рукописную цифру, обучил и загрустил, что у меня плохо работает. Я даже слов "датасет", "переобучение" или "train/test" не знал. Думал, где-то баги. Мне и в голову не могло прийти, что а) данных надо сильно больше; б) данные надо нормализовывать и чистить; в) надо аккуратно выбирать архитектуру, чтобы модель была и не слишком простая, и не чрезмерно сложная.
В комментариях на HackerNews заметили, что есть официальный ответ от Facebook: "Signal даже не пытался запустить эту рекламную компанию, а скриншоты вообще сделаны в марте, когда аккаунт блокировали на несколько дней из-за проблем с оплатой".
Да и скриншоты, говорят, это подтверждают, но интерфейс запутанный и легко можно подумать, что отказали в размещении рекламы, а не проблемы с оплатой.
Следующий обязательный шаг и популярная абстракция — массивы и строки — уже убьёт всех начинающих программистов на Си из-за а) неопределённого поведения при выходе за границу; б) необходимости руками возиться с памятью.
Умение отлаживать систему, которая умеет либо полностью работать, либо иногда необъяснимо падать с вероятность 1% в непонятном месте вполне переносимо с сишного UB на многопоточные приложения, распределённые системы и области с большими данными. Например, какие-нибудь сложные алгоритмы могут упасть после недели работы. Или если у вас десяток тысяч серверов и какая-нибудь коллизия хэшей с вероятностью 0.001% (а из-за масштабов каждый час что-нибудь да падает).
Скорее даже не умение отлаживать, а умение такое писать: чётко следовать заданной модели, не применять "очевидные рассуждения" на самом деле выходящие за рамки модели (вроде "очевидной" sequential consistency) и, когда всё-таки случилась беда, не пугаться происходящего безумия.
Спор между "так символов меньше" + "программисту очевидно" + "незачем усложнять язык" и "строгая типизация лучше слабой" + "больше проверок компиляции лучше" + "код гораздо больше читается, чем пишется" можно продолжать бесконечно.
Я вот во втором лагере. Данный пример вижу так:
Если вы не используете венгерскую нотацию в том или ином виде, то там будет не
number
, а какое-нибудь другое название.Например, есть ли ошибка в следующем коде, если он компилируется и не падает?
Ответ: а фиг его знает.
Если там возвращается
double
(потому что в JSON только вещественные числа) — то, наверное, тут хотели округлить секунды вверх до минут. А вот если там случайно возвращается сишная строка, то вы только что взяли в качестве количества секунд значение указателя. И никаких предупреждений компилятора не получили даже на самом высоком уровне предупреждений.Разумеется, если протестируете, что таймаут у вас корректно работает, вы сразу обнаружите ошибку. Если протестируете. Или хотя бы выведете на экран.
Но тогда, мне кажется, почём зря приближаемся к другому краю спектра с полным отключением статического анализа типов, как в Python. Да, можно код протестировать, но мне больше нравится получать ошибки компиляции, даже если приходится больше набирать или больше думать.
> И совсем уж нубовский вопрос: какое такое сакральное преимущество даёт C++ системном программировании что бы это нельзя было сделать на си?
Ни один язык не даёт сакральных преимуществ над другим. Даже если (что не так в случае Си и C++) является строгим надмножеством другого; не всегда больше возможностей — это хорошо.
А конкретная команды в конкретном проекте делает выбор, исходя из ситуации. Язык, тулчейн, стиль кода, архитектура...
Каким из компиляторов? Они, бывает, отличаются и добавляют свои собственные расширения. А ещё поведение отличается между ОС, потому что помимо компилятора есть стандартная библиотека и протекающие абстракции.
Ill-Formed No Diagnostics Required куда делся?
Уточнение к любым моим советам из интервью: они, конечно же, в основном основаны на моём опыте. Мне много где сильно повезло с обстоятельствами. Если у вас другие обстоятельства, какие-то мои рекомендации могут оказаться лично вам даже вредны (sic!)
Например, я слышал мнение, что олимпиады (не только школьные) как социальный лифт работают гораздо лучше и надёжнее, чем попытки пробиться на зарубежные стажировки и устроиться хоть на какую-нибудь позицию в какие-то случайные компании в небольшом городе. Не уверен, что услышал правильно, но звучит правдоподобно.
На близкую тему: на самом деле ISO вообще не предназначен для USB и там нужна особая магия от создателей образов.
Приёмная комиссия ВУЗа (если речь про бакалавриат) никаких решений уже давно не принимает. За год (или чуть меньше) до поступления публикуется список льгот, которые дают различные олимпиады, список необходимых ЕГЭ — всё. Летом просто сортируются публичные списки подавших документы по определённым правилам и зачисляются верхние строчки, пока не закончатся места.
Есть, конечно, небольшие тонкости с несколькими волнами (в прошлые годы), онлайн-согласиями на зачисление (последние два года), а также иностранными студентами, целевыми местами и местами по особой квоте, но принципиально картина не меняется: вуз юридически никак не может влиять на то, поступит к ним конкретный человек или нет.
Если не ошибаюсь, только два вуза могут проводить собственные экзамены — МГУ и СПбГУ, причём делает это только МГУ. Плюс можно проводить отдельный конкурс на "творческие специальности", куда программирование не относится. Некоторые вузы (вроде МФТИ) устраивают "собеседование" с абитуриентами, но это юридически не влияет на то, будет ли студент зачислен на определённую программу обучения. Вот что там происходит с разделением на потоки/группы внутри программы или будут ли на собеседовании переубеждать поступить в другое место (это я уже фантазирую) — другое дело.
Для развлечения или сверки реализации с какой-нибудь эталонной. Наверное, для принятия бизнес-решений действительно не нужно больше десятка-другого точных знаков, хотя я не специалист.
Так я же не против библиотек. Я против догмы "в двоичной системе всё точно будет быстрее" — нет, не всегда будет.
А в GMP просто используют более сложный алгоритм перевода между системами счисления с разделяй-и-властвуй и наверняка быстрым делением из того же GMP: https://github.com/alisw/GMP/blob/2bbd52703e5af82509773264bfbd20ff8464804f/mpn/generic/get_str.c#L307 . Я ожидаю O(n log^2 n) и ещё кучу неасимптотических оптимизаций сверху. Так что результат вполне ожидаемый.
Сравнение длин там нужно не для скорости, а для корректности: короткое число
99
меньше длинного123
, хотя лексикографически оно больше. Числа, записанные как строчки, надо сравнивать не совсем лексикографически.Да, зависит от задачи, всё верно.
Он не просто тормозит, он у меня минуту работает. А вот если выводить как
print(bin(x))
— то пару секунд.Я не спец в CPython, но файл с названием
longintrepr
выглядит многообещающе: вот тут нам сообщают, что всё действительно хранится в двоичной системе счисления (точнее, с основанием 2**30), а вот тут парой вложенных циклов переводят число из одной системы счисления в другую перед выводом в строку. Даже на Кнута сослались.Вывод: вывод длинного числа в CPython работает за квадратичное от длины числа время. 10**12 операций — это не шутка, даже если соптимизировать в десяток-сотню раз.
Можно в цикле то же самое написать. Ну и раз уж у вас всё равно цифры хранятся как строчки — то можно сначала сравнить по длине, а потом просто как строчки при помощи
<
, он поддерживаетсяstd::string
. Правда, тут надо аккуратно с инвариантами.Устраивает, потому что вывод работает.
Если у меня задача, в которой надо зачем-то посчитать большое десятичное число (обычно в развлекательных/учебных целях), то перестаёт устраивать, потому что у меня перестаёт работать вывод ответа на экран. Например, запустите на питоне вот такой код:
Само число
x
из миллиона знаков посчиталось быстрее, чем за секунду, равно как и его остаток от деления на 10. А вот вывод этого числа целиком занимает некоторое время, потому что идёт перевод из двоичной системы в десятичную неэффективным способом.Очень сильно зависит от школы. И социализация тоже очень зависит от того, с кем именно социализируешься. У меня в трёх школах (включая, кстати, очень счастливо законченный десять лет назад экстернат) были довольно разные коллективы. В кружах тоже разные коллективы. В разных лагерях — разные традиции. В ЛКШ по вечерам одним способом треплются, в матлагере другим, в смене "Орлёнка" — про третье.
Мне кажется, гореть в первую очередь программированием очень даже можно. Какие-нибудь хобби при этом — вещь безусловно полезная, тут согласен.
Мне кажется, в реализации много мест, которые можно и нужно сделать гораздо аккуратнее. Даже если считать, что хранение по десятичным разрядам — это окей с точки зрения быстродействия и поддержания инвариантов.
Из алгоритмического:
Убрать поле
_size
— либо оно всегда равно_value.size()
, либо это что-то непонятное. Незачем усложнять инвариант класса. Можно забыть случайно обновить, а так код короче станет.Строго описать допустимые комбинации значений для оставшихся полей. При наивной реализации очень легко огрести от ведущих нулей, знакового нуля, вычитания чисел похожей длины.
Из C++-специфичного:
Использовать member initialization list в конструкторе вместо переприсваивания полей.
Не начинать переменные с
_
— это допустимо для полей, но, например, для глобальных переменных — неопределённое поведение (undefined behavior, UB).Принимать строки по константным ссылкам, где можно. Или по значению и перемещать. В конструкторе, например, сейчас лишнее копирование.
Можно сделать user-defined literal.
Для тестов удобно взять какую-нибудь библиотеку юнит-тестов вроде onqtam doctest.
Дальше посмотрел на код вашей библиотеки на GitHub:
Вместо своих методов
swap
можно использовать стандартныйstd::swap
. К тому же их совершенно незачем делать методами, могли бы быть свободными функциями, причём видимыми только внутри.cpp
. А для этого их стоит заключить в unnamed namespace.Функцию сравнения чисел можно написать гораздо короче и проще, если использовать паттерн вроде
if (x != y) return x < y;
.Кажется, что есть много дублирования кода между разными функциями сравнения, сложения и вычитания. Концептуально случаев очень мало, но у вас, мне кажется, многовато получилось.
Если основывать на системе счисления, не являющейся степенью десятки, то придётся переводить в десятичную систему и обратно. Наивный подход будет работать за квадратичное время, получим как в Python или Java: вычисления мгновенные, а вот вывод числа на миллион разрядов невозможен. Является ли это проблемой — зависит от задачи.
Как я понял — нет, потому что компилятор попытается соптимизировать цикл целиком, распределить регистры автоматически и не справится догадаться, как лучше. А если делаем через функции, то это форсирует нахождение первых аргументов в определённых регистрах (по ABI), что является нехилой подсказкой.
Жаль, что ничего не упомянули про машинное обучение в целом. Хотя бы на уровне "garbage in, garbage out", сбора и чистки данных, разделения train/test/cross-validation. А без этого заниматься нейросетями очень странно, мне кажется.
"Нейросеть" — это же вообще не главное, хотя и звучит из каждого утюга. Это лишь один из доступных инструментов машинного обучения. Если просто взять нейросеть и попытаться как-то самостоятельно впихнуть в случайную задачу вроде распознавания рукописных цифр (особенно не зная слова "MNIST"), то наверняка ничего не получится.
Я вот лет десять назад прочитал про нейросети, закодил, сделал очень большой (как мне казалось) набор из целых десять примеров на каждую рукописную цифру, обучил и загрустил, что у меня плохо работает. Я даже слов "датасет", "переобучение" или "train/test" не знал. Думал, где-то баги. Мне и в голову не могло прийти, что а) данных надо сильно больше; б) данные надо нормализовывать и чистить; в) надо аккуратно выбирать архитектуру, чтобы модель была и не слишком простая, и не чрезмерно сложная.
В комментариях на HackerNews заметили, что есть официальный ответ от Facebook: "Signal даже не пытался запустить эту рекламную компанию, а скриншоты вообще сделаны в марте, когда аккаунт блокировали на несколько дней из-за проблем с оплатой".
Да и скриншоты, говорят, это подтверждают, но интерфейс запутанный и легко можно подумать, что отказали в размещении рекламы, а не проблемы с оплатой.
UB вполне может быть: бесконечный цикл без побочных эффектов.
Следующий обязательный шаг и популярная абстракция — массивы и строки — уже убьёт всех начинающих программистов на Си из-за а) неопределённого поведения при выходе за границу; б) необходимости руками возиться с памятью.
Умение отлаживать систему, которая умеет либо полностью работать, либо иногда необъяснимо падать с вероятность 1% в непонятном месте вполне переносимо с сишного UB на многопоточные приложения, распределённые системы и области с большими данными. Например, какие-нибудь сложные алгоритмы могут упасть после недели работы. Или если у вас десяток тысяч серверов и какая-нибудь коллизия хэшей с вероятностью 0.001% (а из-за масштабов каждый час что-нибудь да падает).
Скорее даже не умение отлаживать, а умение такое писать: чётко следовать заданной модели, не применять "очевидные рассуждения" на самом деле выходящие за рамки модели (вроде "очевидной" sequential consistency) и, когда всё-таки случилась беда, не пугаться происходящего безумия.