Скоростная реализация перевода символьной строки в численные массивы

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

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

0

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

А количество резервируемых разрядов мне совершенно неизвестно до тех пор, пока я не посчитаю. Допустим, я выделил для умножения чисел 30*3 (2*2) разряда (это по максимуму, вдруг мы умножаем 99 на 99 и нам потребуется 4 разряда, мы не провидцы и не можем предсказать, сколько именно разрядов нам понадобится резервировать).

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

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

А теперь представьте, что я для выражения 2^1 зарезервировал, на всякий случай, 100 000 разрядов, ведь и такая вещь может случиться. Что тогда? удалять лишние разряды, снова ужимая массив?
Тогда мы получим ухудшение производительности вычислений не менее, чем процентов эдак на... 40.. Не хило, верно?)))

Ну и зачем это мне нужно, в таком случае?)))

Можно, конечно, возразить, что ужимать массивы не надо, и так далее, но вот представьте, что человек выполнил 20 математических операций. Программа на всякий случай зарезервировала при каждом действии много разрядов. Логика программа допускает что если у числа есть разряды, то все они являются полезными, и зарезервирует для следующего результата еще больше никому не нужных разрядов. Таким образом у нас образуется неконтролируемая "утечка" разрядов...))))

Нет, конечно, можно написать программу, которая устраняет эти проблемы и строго контролирует нужные разряды. Но если у меня будет такой алгоритм, то динамика мне ВООБЩЕ не нужна будет, понимаете в чем проблема? То есть динамка тут как табурету пятая ножка нужна)))

Добавлено через 6 минут

Сообщение от nmcf 1. Впустую расходуется память. И не мало.

Увы! чем-то надо жертвовать... Я выбрал скорость и пожертвовал памятью. Чуть выше пост, там написано, почему динамические массивы - не лучшая вещь, если я в чем-то не прав, помогите мне это понять, осознать, потому что решения вышеозначенной проблемы в динамике я не вижу. Это очень отрицател
ьно скажется на скорости выполнения кода в угоду экономии места в оперативной памяти.

Сообщение от nmcf Усложняется индексация при работе с числом.

Абсолютно с Вами согласен, усложняется! Очень усложняется!

Хранить, как я описал, проще и расширению это не мешает

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

Добавлено через 2 минуты
На самом деле, использовать вектор - это свежая мысль для меня. Я должен это обдумать. Спасибо за подсказку
Просто появляется ряд ограничений, и если их обойти- это будет лучшим выходом.

0

Даже используя массив фиксированной длины проще хранить от младшего к старшему с нулевого индекса - индексация в циклах проще. Как скорость стала ниже в таком варианте, мне не ясно.
У тебя сто чисел - уже 200 мегабайт. И они должны быть динамическими в любом случае, т. к. в стек столько не влезет. Ну если только глобальные.

0

Сообщение от nmcf Даже используя массив фиксированной длины проще хранить от младшего к старшему с нулевого индекса - индексация в циклах проще. Как скорость стала ниже в таком варианте, мне не ясно.

- Слушайте, а ведь и правда! Я могу так же избавиться от лишней операции вычитания в цикле во время итераций раскидывания по массивам, что даст еще прирост в скорости при расшифровке строки!

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

Сообщение от nmcf У тебя сто чисел - уже 200 мегабайт. И они должны быть динамическими в любом случае, т. к. в стек столько не влезет. Ну если только глобальные.

Да - это проблема! Но и гибкий размер массивов - тоже не сахар.
Вот и вопрос, что выбирать... минимум -33% к скорости или же забитая оперативка...

0

После выделения памяти динамический массив работает с той же скоростью, что и статический. Ну вектор, может быть, чуть медленнее - никак не на 30%.

0

Есть еще другая тема, как снизить количество места, занимаемое в оперативке.
сделать разряды числа, равные не 10, а скажем.. 127. Тогда число, занимающее такой же объем информации займет в 12 раз меньше места. Но это уже из разряда фантазий. Жаль, я не могу контролировать биты, а не байты. Все было бы проще.

0

В 2 раза меньше, существенно не поможет. Используй vector.

0

Сообщение от nmcf После выделения памяти динамический массив работает с той же скоростью, что и статический. Ну вектор, может быть, чуть медленнее - никак не на 30%.

Проблема в том, что если мои прогнозы разойдутся с результатами, и я зарезервирую лишние разряды, то:

1. Надо посмотреть, сколько же реально используется разрядов, то есть необходим анализ числа
2. Надо создать новый динамический массив с инициализацией, подходящий по фактическому размеру числа.
3. Надо скопировать полезные разряды из старого массива в новый.
4. Надо освободить память по старому адресу.
5. Надо перекинуть указатель на новый адрес.

Не знаю как последние две операции, но первые три - точно трудоемкие.

Добавлено через 19 секунд

Сообщение от nmcf Используй vector.

ОК!

0