Comments 87
Непонятно, почему scanf или подобные функции работают медленнее. Автор точно сравнивал с широко используемыми вариантами? Кстати, я бы вообще начал с того, что нашёл исходник какой-то известной функции, делающей то же самое, если уж нельзя по каким-то причинам использовать стандартную библиотеку.
Непонятно, почему scanf или подобные функции работают медленнее.
Потому что у них требование выдавать абсолютно точный ответ (число, ближайшее к написанному). Эта задача, в общем случае, не решаема без софтварных флоатов повышенной точности, например. Собственно, вся сложность чтения вещественных чисел состоит именно в этом, а не в разборе символов, который пишется за один вечер.
Как может функция чтения вещественных чисел выдать число с точностью выше написанного? Сама придумает недостающие значащие разряды?
Я так понимаю, суть не в "точности выше написанного", а в отсутствии потерь точности при преобразовании в строку и обратно.
Ну, так если распознал/разобрал все цифры в строке, то и ничего не потерял, верно? Или я чего-то не понимаю? Что имел в виду комментатор выше?
Число пишут в десятичной системе, а хранится оно в двоичной. Последние знаки часто невозможно сохранить точно, но можно компенсировать это избыточностью.
Число в одной системе счисления всегда точно конвертируется в число в другой системе счисления. В чем проблема то? Вообще то все числа, на минуточку, хранятся в двоичном коде, а выводятся на экран в десятичном. Почему со всеми остальными числами проблем нет, а тут вдруг они появились? Не хватает разрядности под мантиссу? Ну так надо взять число бОльшей разрядности, дабл вместо флоат.
Так я и говорю, что
можно компенсировать это избыточностью
По поводу
Ну так надо взять число бОльшей разрядности, дабл вместо флоат.
а если у нас уже double? Вот мы и приходим к софтварным костылям.
В дабл 52 бита под мантиссу, это примерно 16 десятичных разрядов. Кому в микроконтроллере может понадобится точность с 15-ю знаками после запятой? В какой задаче с микроконтроллером может потребоваться выводить в строку числа с такими разрядностями? При такой огромной точности самый нормальный и простой костыль - просто откинуть младшие разряды.
При такой огромной точности самый нормальный и простой костыль — просто откинуть младшие разряды.
Вот именно. Но для стандартной библиотеки такие костыли запрещены.
И какие же там костыли разрешены? Мне очень интересно стало) Пользователь пытается записать 20-разрядное число на место 16-разрядного. Что, интересно, функция будет с этим делать? Тут вообще то вариантов всего 2: сообщить пользователю что он дурак и ничего не делать и сообщить пользователю что он дурак и откинуть младшие разряды. Иных вариантов впихнуть невпихуемое не существует.
Иных вариантов впихнуть невпихуемое не существует.
На наивный взгляд, есть третий вариант: найти два соседних представимых числа, между которыми попадает заданное, и выбрать из них то, которое ближе.
То что 20-разрядное число не впихнуть в 16 разрядов — это понятно, проблема в другом, когда пытаются впихнуть 4 разряда в 16. Казалось бы, чего тут сложного, но стоит один раз прочитав условные 0.003 записать их же обратно как 0.0029999999999999...
0,0029999999... получаются в результате математических операций с округлением. Причем здесь это? В статье и в комментариях речь идет о другом. О преобразовании строки "3е-3" в вещественное число 3е-3.
Притом, что ввод-вывод — это тоже операция с округлением. Ну нет среди возможных значений double такого числа как 3е-3!
Это кто вам такую чушь сказал?
Ну вот так это работает. Есть 2.99999999999999919508830714676E-3 (0x3F689374BC6A7EF8) и следом за ним 3.00000000000000006245004513517E-3 (...EFA), на один бит различаются. Или как вы это себе представляли, почему нельзя, чтобы не было?
Ну, во первых, между 8 и А есть еще 9. Это так, к слову.
А во вторых, 3.00000000000000006245004513517E-3 это и есть 3е-3. Я же писал ранее, 52 разряда дабл - это 16 десятичных разрядов. Все остальное, что в них не поместилось - это мусорные данные.
Вам надо почитать про представление floating Point в двоичной виде. В частности, про представление мантисы в виде 1/2 + 1/4 +1/8....
между 8 и А есть еще 9
0x3F689374BC6A7EF9 = 2.99999999999999962876917614096E-3
0x3F689374BC6A7EFA = 3.00000000000000006245004513517E-3
У первого числа погрешность 3e-19, у второго - 6e-20.
А Вы предлагаете всегда вниз округлять.
UPD: Могу писать раз в час. На ответ ниже: похоже, что-то недопонял.
проблема в том, что нет вещественного числа 3e-3 (вещественного в смысле float, вещественное в смысле Re есть :-)). есть оооочень близкое к нему другое(!) вещественное число потому что 1/1000 = b1/b1111101000=(1/b1000)/b1111101=b1/(b10*b10*b10*b101*b101*b101)- и это бесконечная периодическая дробь, которая будет округлена до первых 52х знаков- округлена!
Подскажите, 1/5 в двоичной системе как точно представляется? у меня почему-то получается двоичная периодическая дробь, которая точно не представима в конечным числом двоичных знаков.
конечным числом двоичных знаков
Ну так, получается, избыточность c этим справится, но есть незначительный нюанс с требованиями к оборудованию :)
Разумеется, конечная избыточность не осилит то, что не представимо конечным числом знаков. К сожалению, или к счастью, арифметические сопроцессоры не умеют в периодические дроби на аппаратном уровне. Хотя это было бы интересно.
Речь не о том, что мы делаем избыточность, и, якобы, при каком‑то конечном уровне этой избыточности, получаем точное значение. Разумеется, это не так. Речь о том, что при каком‑то уровне избыточности точность будет достаточной для нашей конкретной задачи: при переводе из строки в бинарный вид и обратно, будет накапливаться такая ошибка, которой мы можем пренебречь.
это невозможно же! строка-то в десятичной системе, а число мы получим в двоичной системе. Конечные десятичные дроби могут быть периодичными двоичными дробями, поэтому число 0,2 в двоичной системе точно не представимо и преобразование туда-обратно обязательно даст отклонения в младшем бите. В численных расчетах сохранение промежуточных результатов в человекочитаемом виде приводит к тому, что повторная загрузка этих данных и продолжение счета с них отличаются от того, что рассчитывается без промежуточных сохранок-загрузок, а если нужно точное продолжение счета после загрузки сохранения- то приходится вещественные числа сохранять побитово, в разных форматах, но чтоб гарантировать побитовое совпадение записанного и считанного.
, почему scanf или подобные функции работают медленнее. ..... если уж нельзя по каким-то причинам использовать стандартную библиотеку.
Стандартная функция sscanf ненадежная для ответственных систем.
sscanf делает синтаксический разбор double тогда, когда это не требеется и при этом еще и выдает непредсказуемый результат.
Вот отчет тестирования функции sscanf.
если уж нельзя по каким-то причинам использовать стандартную библиотеку.
Кода Вы пишите свой парсер double чисел из строки, то Вы можете совершенно спокойно добавить распознавание размерных суффиксов (n m k p M G).
Например строчку "100n" распознать как 100e-9 = 0.0000001.
scanf Вам такое не сделает.
Не ясно откуда такой оверхед (может это из-за логов, которые вы почему-то оставили?), у меня решение на Rust справляется также быстро и потребляет максимум 2.2mb (0ms 2.1mb, 4ms 2.2mb).
Также, не думаю, что \n
и \r
- легальные символы. Но они, собственно, в коде и задействуются как условия завершения работы.
Может case '1'
... case '9'
стоило поместить в default
ветку и сравнить два раза (с '1'
и '9'
соответственно)?
Посмотрел на функцию number_exponenta_calc
и заметил, что вы производите много работы с числами. Не думаю, что это хорошо, потому что от вас этого не требуют. Условно, если добавить этот код в какой-то проект (просто представьте), то число будет вычисляться дважды - для проверки и при построении после.
Кому интересно, код на Rust можно посмотреть тут
потребление памяти на leetcode, по-моему, близко к случайному. Очевидно же что для этой функции и 2 килобайта памяти много, откуда там мегабайты.
Не настолько же
Именно настолько. Уверен, автор успешно запустит свою функцию на микроконтроллере с несколькими килобайтами рам (и несколькими десятками кб флеша). На этом же контроллере запустится и растовский вариант. Но если на функцию ушло 2 килобайта, то остальные мегабайты ушли на библиотеки рантайма, файловые кеши, прочее не относящиеся к задаче вещи. Скорее всего ключи компилятора повлияют намного сильнее на размер памяти чем то что там понаписал пользователь.
Почему не sscanf? Железка настолько сурова, что недоступна libc?
оказалось быстрее всех решений на языке программирования Си!
Ну тк в задаче на Leetcode требуется определить валидность/невалидность числа, а не зачитать его в double, то можете выбросить все арифметические операции из вашего решения и получить ещё более быстрое...
(Upd: не обновил комменты перед ответом)
Можно упростить: https://onlinegdb.com/4U-2Q6w0K
Упростить -то можно, однако по ISO26262 надо чтобы код ещё оставался читаемым, тестируемым, ремонто-пригодным, конфигурируемым, переносимым и поддерживаемым.
А это
https://onlinegdb.com/4U-2Q6w0K
выглядит как код написанный неземным существом
Это классический LL(0) парсер рекурсивным спуском (конечно однобуквенные переменные надо переименовать). Но код все равно понятен как отче наш любому, кто знаком с "Драконом" Ахо-Ульмана. Или учился на книгах Вирта.
Не думаю, что стандарт на прошивки автомобилей ISO26262 требует, чтобы код прошел одобрение Шалыто.
Пальцем можно показать рекурсию?
В методе рекурсивного спуска есть поток токеров, словари правил и матчер, который рекурсивно вызывает себя с различными словарями правил. Если матчер захардкодить, и для разных словарей правил построить отдельные функции матчинга, например: "skip_whitespace", "get_sign", "parse_int",- то такая реализация рекурсивного спуска может и не содержать явную рекурсию, но метод все равно будет называться методом рекурсивного спуска.
Вот именно, что тут захардкоден абсолютно жёсткий формат, а вместо токенов простые символы.
Вы это так написали как будто это что-то плохое. Да именно жесткий формат числа с плавающей точкой. Это было исходное задание. Причем код построчно повторяет грамматику, то есть самодокументирующийся. А токены не нужны. Они были нужны во времена перфокарт, когда надо было между пассами компиляторов передавать промежуточные данные, и хранить один байт вместо ключевого слова из пяти байт было принципиально. Сегодня и ключевые слова в языках стали контекстно зависимы, и токенизация больше не может различать границы (как например >> в именах шаблонов С++) и поток токенов, увешанный метаданными значительно превышает по объему и исходный текст и усложняет/замедляет парсеры. Сегодня даже в грамматиках напрямую используют символы (например, в ANTLR).
В приниципе код хороший, отличный даже, и наверняка закроет 99.9% всех типичных кейсов, хотя пара моментов всё же не учтена.
Я не знаю что там в стандарте, но зравый смысл требует чтобы код вернул ошибку в случае потери точности (если мантиссы не хватит), а не только если на входе не число.
Т.е. даже если наш double
соответствует IEEE 754 то у нас всего 52 бита, а это маловато как-то если получим на входе хотя бы 17 знаков, но поскольку C не гарантирует что это будет именно 64 бита double precision (не говоря уже о том что это может быть и вовсе не IEEE 754) то результат может оказаться чуть печальней чем хотелось бы, особенно если код используется в чём-то критичном типа авиации или автомобилей.
Подобная проверка может показаться избыточной на таких многозначных числах - но её наличие позволит поймать случаи когда входные данные неадекватны.
С переполнением тоже не всё гладко - если повезет, то получим на выходе INF (хотя его ещё нужно будет проверять в месте вызова), но можем нарваться и на SIGFPE (или его аналог) или просто на мусор в результате.
@aabzelВаш код из статьи тоже "посыпется" если на входе будет что-то многозначное, но ситуация усугубляется ещё и тем что вы используете uint64_t
для разбора целой части - т.е. возможные переполнения вообще могут оказаться незамеченными. Может быть именно по этой причине задачка получила уровень "hard" - разбор чисел с плавающей точкой (да и просто целых тоже) это совсем не так просто если нет никаких гарантий о качестве входных данных. И да, судя по всему их тесты описанные выше случаи явно не покрывают.
К тому же, конечный автомат в данном случае это перебор - медленно, громоздко и плохо читаемо и понимаемо (= высокая когнитивная нагрузка).
Ваш код из статьи тоже "посыпется" если на входе будет что-то многозначное, но ситуация усугубляется ещё и тем что вы используете
uint64_t
для разбора целой части - т.е. возможные переполнения вообще могут оказаться незамеченными.
Есть ли возможность прислать test case?
Легко: 12345678901234567890
Прогнал тест. Число 12345678901234567890 благополучно распозналось
А, у вас же беззнаковый тип. Тогда 23456789012345678901
Спасибо за тест-кейс !
В самом деле распознавание 23456789012345678901 не проходит.
это лишь потому, что разрядность для целого числа переполнилась за 64 бит
это лишь потому, что разрядность для целого числа переполнилась за 64 бит
Именно это вам и писали выше.
Даже если интерпретировать целую часть как double мантисса переполняется на тесте 23456789012345678901 .
. Тогда 23456789012345678901
Перевел целую часть парсера на long double. Теперь и 23456789012345678901 обрабатывается корректно
К тому же, конечный автомат в данном случае это перебор - медленно, громоздко и плохо читаемо и понимаемо (= высокая когнитивная нагрузка).
Вот конечные автоматы это как раз таки способ уменьшить когнитивную нагрузку. Ибо все понимают что есть такой паттерн и как он работает. Все кто прочитал хоть одну методичку/учебник по FSM без труда поймёт мой код.
При этом FSM код отлично представляется визуально в виде графа и переходов или табличкой. Тут уж кому что по вкусу
Потом стандарт автомобильного программирования iso26262-6 обязывает использовать well-trusted design principles. И теория fsm это как раз-тот самый well-trusted design принцип.
И наконец, быстрее программных конечных автоматов может работать только аппаратный конечный автомат внутри ASIC(а).
Не думаю, что стандарт на прошивки автомобилей ISO26262 требует
В вашем коде в функции 3 раза return. По ISO26262 в каждой функции должен быть только один return.
В моей компании используется другой стиль кодирования, в котором приветствуется ранний return. Вы легко можете изменить мой код, чтобы поддержать единственный return.
Кстати обратите внимание на 1h No hidden data/control flow. Боюсь, это - прямой запрет на стейт-машины.
так можно сказать, что и локальные переменные запрещены- они же "hidden" для вызывающего кода. Это скорее запрет на использование стейт-машины без ее явной инициализации при каждом вызове.
В моей компании используется другой стиль кодирования, в котором приветствуется ранний return.
В вашей компании разрабатывают firmware для автомобильных ECU?
обратите внимание на 1h No hidden data/control flow. Боюсь, это - прямой запрет на стейт-машины.
ISO26262 не запрещает использование конечных автоматов.
Можно упростить себе задачу: передавать в МК только нормированные целые числа (милливольты вместо вольтов, микроамперы вместо амперов етц) и не закатывать солнце вручную.
В программировании микроконтроллеров часто приходится в UART консоли вводить в прошивку какие-то калибровочные коэффициенты: значения токов, пороговых напряжений, уровней освещений и прочего. Как правило это действительные числа с плавающий запятой.
Я так понимаю что весь вышеописанный гемморой связан именно с этим? Настолько часто надо вводить, что нужно рожать решение, которое быстрее всех что-то делает?
Потом часто надо анализировать текстовые логи с SD-карты. Надо выхватывать вещественные числа из CSV строчек.
наши погромисты настолько суровы, шо не помнят, как пишут текстовые (!) логи на SD карту? Или какая религия запрещает использовать xprintf/xscanf с одним и тем же (ну или почти) форматом?
И что это вообще получается, боремся за быстрее всех распознавание текстовых логов, но при этом безбожно тормозим при записи этих логов в текстовом виде и на SD карту?
Или вообще речь идет о борьбе за наносекунды при анализе логов на компе, где обычно и ядер и памяти до и больше?
И вообще, как минимум по моему опыту, при анализе логов проблема не с засасыванием CSV, а с визуализацией данных для больших логов. Если эксель или LibreOffice еще как-то способны засасывать логи под 100k строк, то с построением графиков в этом случае у них все плохо и как раз тут надо городить свою приблуду на чистом Це/Це++
Я так понимаю что весь вышеописанный гемморой связан именно с этим? Настолько часто надо вводить, что нужно рожать решение, которое быстрее всех что-то делает?
Пользуюсь UART-CLI каждый день. И знаю еще с пол дюжены embedded контор, где тоже умеет UART-CLI.
Тут же представлен универсальный алгоритм, который парсит все числовые типы данных!
И задача парсинга вещественного числа из строчки на самом деле очень-очень простая для тех, кто не прогулял курс по теории автоматов в универе.
да она и без МК актуальна- эксель до сих пор не понимает числа с точкой вместо запятой, а куча научного софта для всяких разрывных машин сохраняет данные в текстовый формат и именно с точкой. И пользователи этого софта тоже хотят вводить вещественные числа, и при этом не париться вопросом- запятую они там влупили, или точку, английскую е или русскую, 0.1 или .1е+0.
Я так понимаю что весь вышеописанный гемморой связан именно с этим?
Не только.
Double(ы) надо на лету парсить в NMEA протоколе, которым флудит каждый GNSS приемник в UART.
Так выделяются значения для широты и долготы инфа про спутники и много прочих системных параметров.
Double(ы) надо на лету парсить в NMEA протоколе, которым флудит каждый GNSS приемник в UART.
Википедия говорит, что там 4800 бод скорость, в расширенном 38400, т.е. скорости никакие, Формат фиксированный, кривых ручечек нет.
Пользуюсь UART-CLI каждый день.
и что, что пользуетесь? сколько времени вы набираете в этом CLI double число? Допустим, секунду. И какой эффект будет от того что, вы сэкономите микросекунду на парсинге?
а реальная практика радиосвязи говорит, что иногда эти данные приходят битые- и тогда парсинг строки фиксированного формата превращается в черте что.
Я сделал парсер не для выйгрыша времени, а для корректного парсига любых форм записи.
С этим вот как раз проблемы у sscanf, которая даже "abc" считает double числом.
Да ну?
double d;
int r;
r = sscanf("abc", "%lf", &d);
printf("r = %d", r); // r = 0
Возвращаемое значение 0 означает что вещественное число прочитать не удалось. Ну и о каком "даже abc считает double числом" речь-то?
Я так понял, что автору по ТЗ нужна ошибка при поступлении невалидной строки, а не интерпретация её как 0.
да
Так это и есть признак ошибки, я же переменную r, а не d проверяю.
а кто ее интерпретирует как ноль?
int main(int argc, char * argv[])
{ char *str = "abc";
char *str1 = "3.14";
double d = -1.;
int rc;
rc = sscanf(str, "%lf", &d);
printf("rc = %d, str=%s, d=%f\n", rc, str, d);
rc = sscanf(str1, "%lf", &d);
printf("rc = %d, str1=%s, d=%f\n", rc, str1, d);
return 0;
}
//Вывод
//rc = 0, str=abc, d=-1.000000
//rc = 1, str1=3.14, d=3.140000
А как вам такое?
Вот подборка кейсов, где sscanf выдает явные ошибки
Почему перевод не отмечен как перевод? Судя по "словарю" в конце поста, где даётся расшифровка ни разу не применявшейся в тексте аббревиатуры DFA, это точно не авторский контент...
вариант на Lua
function nkff(S)
z0=string.byte('0'); z9=string.byte('9');
zE=string.byte('E'); zp=string.byte('+');
zm=string.byte('-'); zt=string.byte('.');
len=string.len(S);
for j=1,len do
m=string.byte(S,j);
if m>32 then
if m>=z0 and z9>=m then
z2=true s1=true;
else
m=m&0xdf;
if s1 then
if m==zp or m==zm then
if s1==nil or z1==zE then s1=true; end
else
if m==ze and (z1==zp or z1==zm) then s1=nil; break else s1=true; end
end
else
if m~=ze then s1=true; end
end
z1=m;
end
z1=m;
end
end
if z1==ze or z1==zp or z1==zm or z2==nil then s1=nil end
return s1;
end
вариант на C
char nkff(char *ps) {
char f=0; char z1=0; char s1=0; char z2=0;
long len=strlen(ps);
long j=0; while(len>j) { char m=ps[j];
if (m>32){
if(m>='0' && m<='9'){ s1=1; z2=1;}
else { m=m&0xdf;
if(s1){
if (m=='+' || m=='-') s1=1;
else { if(m=='E' && (z1=='+' ||z1=='-')){ s1=0;break;} else s1=1; }
} else { if (m!='E') s1=1;}
}
z1=m;}
j++;}
if (z1=='E' ||z1=='+' || z2==0)s1=0;
return s1;}
Техникум: Распознавание Вещественного Числа из Строчки