@gledor

Здравствуйте! Недавно загорелся идеей создать свой собственный класс больших чисел (с десятичной дробью)
Для этого я буду использовать два целочисленных массива (целая и дробная часть числа), каждый элемент которых будет не более 1 байта размером, и одни флажок bool для "означивания" числа положительное\отрицательное.

Разумеется, чтобы вводить такое длинное число, я решил использовать строку, вводимую пользователем.
Внимание, вопрос:
Представим, что человек ввел 500 000 символов. Возможна ли проверка введенного числа на корректность, и его разбор + раскидывание по массивам менее, чем за 0,5 секунды?
Если да, то какими приемами тут лучше пользоваться? У меня есть немного оформившиеся планы, но они немного мутноватые.
Ах, да, забыл сказать, что лучше не ограничивать человека в вводимой строке, кроме как в совсем очевидных случаях (если две разделительные запятые, или два знака, или буквенный символ) например, функция должна понять эти строки одинаково и не сообщать об ошибке.
И так далее. Разумеется, необходима хорошая скорость распознавания, а то иначе это никому не нужно будет. На что мне следует сейчас ориентироваться?

0

@nmcf

Ну это измерять надо. От компьютера зависит. Ты замеры делал? Может, полсекунды хватает.

0

@gledor

Пока мне удалось довести расшифровку до 3,2 секунды, при условии наличия 1 000 000 элементов в каждом массиве. (всего 2 миллиона на 2 массива).

Мне кажется, надо переделывать алгоритм, сделать его "хитрым" и умным, с "ленивым" заполнением элементов. То есть мы заполняем только необходимые цифры в массив. И если пользователь ввел 10 цифр до запятой, то и записать в массив надо 10. А не весь миллион переписывать. Просто я думаю, как это решить. Сейчас очень сложно определиться с ключевыми параметрами строки, которые необходимы для такого заполнения. Попробовать несколько вариантов. Если у меня все сработает, то чем более маленькое число вводит пользователь, тем быстрее строка расшифровывается.

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

Так можно компенсировать огромную тяжеловесность класса.

Добавлено через 7 минут
Вопрос в том, что м.б. у кого - то были подобные случаи, и кто-то может поделиться опытом организации кода для такого дела.
У меня мозг ломается.Там очень много нужно учесть.
Сначала моя функция занимала 298 строчек кода.
Потом я сократил до 245 строк кода.
Сейчас вот, оптимизировал, и теперь она занимает 250 строк кода. Да, появилось несколько новых, но зато я убрал много лишних повторяющихся вычислений в циклах, которые по сути, являются константными.

0

@nmcf

Разве это не очевидно?

0

@gledor

Весьма очевидно. но трудноосуществимо по причинам:

1. В связи со спецификой массивов, у меня идет связка в виде:

массив целочисленной части числа массив дробной части числа
0эл. 1эл. 2эл. 3эл. 4эл. 5эл. 6эл. 0эл. 1эл. 2эл. 3эл. 4эл. 5эл. .....

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

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

3. Для того, чтобы обрабатывать только те символы, которые являются цифрами, пропуская пробелы, и пропуская "мусорные" нули в начале целочисленной части числа и "мусорные" нули в конце дробной части числа (если пользователь их зачем-то ввел, или же это вывод из какой-либо другой функции), необходимо соединить эту систему с алгоритмом поиска ошибок, что даст высокую скорость обработки, но обеспечит сумасшедшую хардкорность алгоритма и написание кода.

4. Для реализации вот такого "ленивого" заполнения необходимо будет написать анализатор положения "ориентиров", по которым я буду одновременно заполнять оба массива, а так же возрастет сложность заполнения массивов и сложность алгоритма благодаря вводу в него таких понятий, как ориентиры заполнения.

Я уже 4 дня мучаюсь. Наконец, оформил то, что надо сделать. Но мне кажется, что это неподъемно... -_- быть может, я изобретаю велосипед в случае анализа строки, и есть какие-то сопутствующие функции в библиотеке C++. В общем, очень прошу помощи в организации, как этот объем провернуть?

+ я все это хочу воплотить в лице одной функции, единым куском кода. Потому что логически верно считать расшифровку строки одной функцией.

0

@nmcf

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

1

@gledor

Хех)))) Ну, что поделать...
На счет пробелов - теоретически я хочу дать возможность человеку их вставлять неограниченно, дабы во время написания длинных чисел он мог группировать скажем, каждые три разряда при помощи пробелов. Но я не хочу жертвовать производительностью от лишнего прогона (если он делается в одном ядре с другими) . Поэтому хочу добавить алгоритм пропуска пробелов уже во время разбрасывания результатв по массивам
Так же, я хочу дать возможность человеку ставить перед перед числом знак +, - или не ставить знак вообще.

То есть, функция должна корректно считать в крайнем случае такое:

" - 000 00000 0 758 87 7 , 0045 67 8 00000 0"
И выдать на выходе такое:
"-758877,0045678"

Да, согласен! Минимум - два цикла выходит. Ну, может быть, еще поцдикл в одном из циклов.
То есть задачу можно уже разбить так:
Первый цикл - проверка синтаксиса и сбор сведений об ориентирах ввода
второй цикл - заполнение двух массивов одновременно, один - слева направо, другой - справа налево.

0

@nmcf

Что за массивы, обычные? Как именно хранятся цифры частей?

0

@gledor

Массивы обычные, не динамические. Потому что с динамическими будет очень много проблем... НО! Если руки дойдут - и если это будет себя оправдывать, то сделаю массивы в классе динамическими.
Цифры являются переменными типа signed char, просто при выводе на экран, я привожу элементы к их численному значению.
Каждый элемент это 1 десятичный разряд. Хранятся они по порядку. но заполнение массива целой части числа начинается с попы, где последний элемент массива - это самый первый разряд единиц. А заполнение дробной части - с начала, где 0 элемент - количество десятых частей.

0

@Fulcrum_013

Удали из строки пробелы,вычти из каждого элемента '0' вот тебе и твои массивы. Вернее массив можно иметь вообще один, только завести переменную которая показывает положение в нем запятой. Кстати их можно и в BCD конвертнуть, операции с которым интеловский проц выполнять обучен от рождения.

1

@sourcerer

Указатель на элемент, с которого начинается дробная часть?

0

@Fulcrum_013

типа того

0

@gledor

Спасибо всем за ответы! Задачу я ДОвыполнил сегодня утром.
В общем, пришлось переписывать с самого начала. В итоге у меня вышло много циклов, НО! даже при самой максимальной нагрузке, строка проходит не более, чем через 3 цикла, а минимально - через 2.

числа по - прежнему хранятся в signed char, но в виде целых чисел, а не символов. То есть, я отнимаю '0' от символа, введенного пользователем и присваиваю результат элементу signed char.

+ я смог дать возможность пользователю вводить в строку пробелы по своему усмотрению, группируя ввод разрядов как ему удобно, и избежать дополнительного цикла по избавлению от пробелов.

В итоге, я обеспечил как мне кажется, хорошую скорость выполнения расшифровки.
Проводил тест на вводе около 250 000 символов в массив, а потом выводе элементов массива в консоль.
На расшифровку и разбрасывание по массивам ушло 98 ms, а на вывод через cout - около 300 ms

В общем, план явно выполнен! Всем спасибо!

0

@nmcf

Целая часть должна храниться начиная с разряда единиц (индекс 0), иначе при сложении тебе придётся сдвигать всё это при переполнении. Тоже самое касается дробной части.
А для хранения лучше std::vector.

0

@gledor

Дык если у меня разряд переполнен в результате сложения двух элементов одного и того же разряда (скажем, тысячного). Например,мы сложили 5+7, то получится 12. Мы по-любому вычтем десять, и прибавим к старшему разряду единицу,оставив 2 во младшем. То есть мы по любому перекинем всю эту информацию. Только в одном случае справа налево, а в другом - слева направо.

Как я это представляю:

То есть в любом случае у переполненного разряда отнимаем десятку и прибавляем единицу к более старшему.
И тут вообще не важно, слева направо мы считаем или справа налево. Разумеется, ни о каком "сдвиге" в массиве речи не идет. Обработка переполненных разрядов - да, будет в обоих случаях. А полный сдвиг всех элементов массива при добавлении\переполнении - нет. не будет. Потому что это жесткий каркас. И вектор тут не нужен. Я хочу протестировать эту версию. Если на будет достаточно быстра - я её оставлю. Если нет - попробую с вектором по другой системе.

0

@nmcf

5+5=10, т. е. число становится двухразрядным и чтобы старший разряд вместить в нулевой индекс, придётся сдвинуть всё. А если старшие разряды в конце, то просто добавить.

0

@gledor

А, врубился.
Знаешь, я просто решил сделать всё-таки конечное число. Потому что по моему скромному мнению, людям вполне хватит и 100 разрядов до запятой, и 100 000 разрядов после запятой. Я же сделаю до миллиона. Много памяти это не сожрет, такая переменная будет занимать всего около 1,95МБ памяти (если считать не только массивы), что просто пустяк...
По-моему в прикладной математике даже "сумасшедшим ученым" не нужна бОльшая точность и громадность. Ибо поросту, и считать больше нечего.

А при помощи "ориентиров" я сделаю быстрые вычисления для коротких чисел.

Между прочим, надо не забывать, что запас числа очень большой. И вряд ли человек от руки вобьет больше 300 - 400 символов. Да даже если огромное число будет результатом какой-либо операции и просто будет передано строкой в функцию, это не очень удобно. Поэтому я не вижу особого смысла делать динамически добавляющиеся ячейки. Мб, я не прав... слово Вам.

Добавлено через 16 минут
И что пока еще говорит НЕ в пользу вектора и динамики, так это вопрос:

Допустим, я перегружу оператор *, и напишу умножение.
Я приму на входе четыре массива (два числа) и... тут оказывается, что все эти массивы абсолютно разной длины! Как мне умножать и координировать их относительно друг друга? Я же не знаю, сколько места потребуется зарезервировать для результата умножения, потому что сначала мне надо умножить. Нет, я, конечно, могу выделить места сразу по максимуму (количество ячеек самого большого числа * 2), а потом урезать мусорные лидирующие нули, но тогда смысл в этой динамичности, если она только мешает? Усложняет алгоритм, работает неэффективно, тратит больше времени. Лучше сразу задать какие-то рамки. А выход за рамки пресекать сообщением о нехватке места. Так может не очень гибко, но зато очень быстро!

0

@nmcf

Да не в ориентирах дело, а в оптимальности. Статический массив или нет, при твоём способе хранения потенциально понадобится сдвиг для операций типа += и -=, и придётся этот мегабайт сдвигать.
std::vector можно использовать с фиксированным размером, если ты об этом. Про разную длину массивов я не понял, как это мешает?

0

@gledor

Мб. мы немного разные вещи подразумеваем и думаем? ))))

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

То есть, Вы скорее всего думаете, что я храню число 1024 таким способом:

0 0 0 4 2 0 1.

согласен, такой вариант - это идиотизм, потому что при переполнении старшего разряда необходимо сдвигать информацию, например:

0 0 0 4 2 0 1
0 0 0 0 0 0 9
= 0 0 0 4 2 0 10,

То тут да, это плохое решение, необходим сдвиг влево при увеличении числа на один разряд.

может быть, Вы думаете, что я сохраняю число 1024, как

1 0 2 4 0 0 0 0,

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

Я же говорю о другом случае хранения. тоже сзади начинается, но не задом наперед, а по-нормальному, в моем случае

где мне не надо при увеличении числа его постоянно сдвигать.

я говорю о варианте

0 0 0 0 0 0 0 0 1 0 2 4

Это неплохой вариант, потому что при переполнении старшего разряда, я перекидываю дополнительную единицу в свободный, нуленый старший разряд и нет необходимости переписывать и сдвигать ВСЕ число. Когда у меня переполнится старший разряд (0 элемент), я просто выдам сообщение о переполнении и сделаю обнуление.

0

@nmcf

1. Впустую расходуется память. И не мало.
2. Усложняется индексация при работе с числом. Хранить, как я описал, проще и расширению это не мешает. Можно использовать фиксированный размер с запасом, а можно и динамический.

1