Как можно оптимизировать код для перевода из одной системы счисления в другую?

Question

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

#include<iostream>
#include <math.h>
#include <string>
using namespace std;
int Pered(const char* num, int osn)
{

    return static_cast<const int>(strtol(num, NULL, osn));


}
string sys(int b, int n) 
{

    string res = "";

    for (int i = 0; n > 0; i++) {

        if (n == b) {
            res = "10" + res;
            break;
        }

        else {
            if (n % b > 9) {
                res = char('a' + (n % b) - 10) + res;
            }
            else {
                res = char((n % b) + '0') + res;
            }
        }

        n /= b;
    }

    return res;
}
int main()
{
    char num[20];
    int osn_star, osn_new, chis_d;
    cin >> osn_star >>osn_new >> num;
    if (osn_star < 2 || osn_new>36 || num < 0)
    {
        return 0;
    }

    chis_d = Pered(num, osn_star);
    cout << sys(osn_new, chis_d);
}

Answer 1

Можно придраться к тому, что строки уже создаются пустыми и инициализированными, так что string res = ""; у вас - просто лишнее.

Теперь, к реальной проблеме: Да это же старый знакомый - Маляр Шлемиэель! [EN]

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

Другие, более злобные алгоритмы, используют заранее подготовленные таблицы и SIMD-инструкции, но обычно они заточены на конкретные системы счисления

P.S. Авторство притчи про Шлемиэля приписывается Джоэлю Спольски, который помимо всего прочего, основал и этот сайт в том числе:

Спольски является сооснователем (совместно с Джефом Этвудом) системы вопросов и ответов Stack Overflow.

Answer 2

А так не хотите?

int main()
{
    int f, t;
    char n[65] = {0};
    cin >> f >> t >> n;
    _strupr(n);
    unsigned long long m = 0;
    char * c;
    for(c = n; *c; ++c)
        m = m*f + *c - (*c > '9' ? 'A' - 10 : '0');
    for(c = n+64;m;m/=t)
        if ((*--c = m%t + 'A' - 10) < 'A') *c += '0'-'A'+10;

    cout << c;
}

БЛОГ НА HUSL

Как можно оптимизировать код для перевода из одной системы счисления в другую?

Ответы (2 шт):