Есть ли способ улучшить скорость или эффективность этого поиска? (C / C ++)

Question

У меня есть функция, которую я написал для преобразования 64-разрядного целого числа в базовую 62 строку. Первоначально я добился этого примерно так:

char* charset = " 0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
int charsetLength = strlen(charset);

std::string integerToKey(unsigned long long input)
{
    unsigned long long num = input;
    string key = "";

    while(num)
    {
        key += charset[num % charsetLength];
        num /= charsetLength;
    }

    return key;
}

Однако это было слишком медленно.

Я улучшил скорость, предоставив возможность генерировать справочную таблицу. Таблица имеет размер около 62 ⁴ строк и генерируется следующим образом:

// Create the integer to key conversion lookup table
int lookupChars;

if(lookupDisabled)
    lookupChars = 1;
else
    largeLookup ? lookupChars = 4 : lookupChars = 2;

lookupSize = pow(charsetLength, lookupChars);
integerToKeyLookup = new char*[lookupSize];

for(unsigned long i = 0; i < lookupSize; i++)
{
    unsigned long num = i;
    int j = 0;

    integerToKeyLookup[i] = new char[lookupChars];

    while(num)
    {
        integerToKeyLookup[i][j] = charset[num % charsetLength];
        num /= charsetLength;

        j++;
    }

    // Null terminate the string
    integerToKeyLookup[i][j] = '\0';
}

Фактическое преобразование выглядит следующим образом:

std::string integerToKey(unsigned long long input)
{
    unsigned long long num = input;
    string key = "";

    while(num)
    {
        key += integerToKeyLookup[num % lookupSize];
        num /= lookupSize;
    }

    return key;
}

Это улучшило скорость с большим отрывом, но я все еще верю, что ее можно улучшить. Использование памяти в 32-разрядной системе составляет около 300 МБ, а в 64-разрядной системе - более 400 МБ. Похоже, я должен быть в состоянии уменьшить память и / или улучшить скорость, но я не уверен, как.

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

Answer 1

Возможно, вы захотите заранее зарезервировать память для вашего string key. Это может дать вам приличный прирост производительности, а также прирост использования памяти. Каждый раз, когда вы вызываете оператор добавления на std::string, он может удвоить размер внутреннего буфера, если ему придется перераспределить. Это означает, что каждая строка может занимать значительно больше памяти, чем необходимо для хранения символов. Вы можете избежать этого, заранее зарезервировав память для строки.

Answer 2

Использование какого-либо строителя строк вместо многократной конкатенации в «ключ» обеспечило бы значительный прирост скорости.

Answer 3

Я согласен с Робом Уокером - вы концентрируетесь на улучшении производительности не в той области. Строка самая медленная часть.

Я синхронизировал код (ваш оригинал поврежден, кстати), и ваш оригинал (после исправления) составлял 44982140 циклов для 100000 поисков, а следующий код - около 13113670.

const char* charset = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
#define CHARSET_LENGTH 62

// maximum size = 11 chars
void integerToKey(char result[13], unsigned long long input)
{
    char* p = result;
    while(input > 0)
    {
        *p++ = charset[input % CHARSET_LENGTH];
        input /= CHARSET_LENGTH;
    }

    // null termination
    *p = '\0';
    // need to reverse the output
    char* o = result;
    while(o + 1 < p)
        swap(*++o, *--p);
}

Answer 4

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

Примечание. В вашем вопросе указано, что вы конвертируете в base-62, но в коде 63 символа. Что вы пытаетесь сделать?

Учитывая 64-битное целое число, вы можете рассчитать, что вам не понадобится больше 11 цифр в результате, поэтому использование статического 12-символьного буфера, безусловно, поможет улучшить вашу скорость. С другой стороны, вполне вероятно, что ваша библиотека C ++ имеет длинный-длинный эквивалент ultoa, что будет довольно оптимально.

---

Редактировать: вот что я взбил. Позволяет также указать любую желаемую базу:

std::string ullToString(unsigned long long v, int base = 64) {
    assert(base < 65);
    assert(base > 1);
    static const char digits[]="0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ+/";
    const int max_length=65;
    static char buffer[max_length];

    buffer[max_length-1]=0;
    char *d = buffer + max_length-1;
    do {
        d--;
        int remainder = v % base;
        v /= base;
        *d = digits[remainder];
    } while(v>0);

    return d;
}

Это создает только один объект std :: string и не перемещает память без необходимости. В настоящее время он не дополняет нулями вывод, но тривиально изменить его так, чтобы получить столько цифр, сколько вы хотите.

Answer 5

Если все, что вам нужно, это короткий строковый ключ, преобразование в числа base-64 сильно ускорит процесс, поскольку div / mod 64 очень дешев (смещение / маска).

Answer 6

Если бы вы могли добавить еще два символа для преобразования в base-64, ваши операции по модулю и делению превратились бы в битовую маску и сдвиг. Гораздо быстрее, чем деление.

Answer 7

Почему бы просто не использовать библиотеку base64? Действительно ли важно, что 63 равно «11», а не более длинной строке?

size_t base64_encode(char* outbuffer, size_t maxoutbuflen, const char* inbuffer, size_t inbuflen);

std::string integerToKey(unsigned long long input) {
    char buffer[14];
    size_t len = base64_encode(buffer, sizeof buffer, (const char*)&input, sizeof input);
    return std::string(buffer, len);
}

Да, каждая строка будет иметь одинаковый размер. Если вы этого не хотите, удалите знак равенства. (Просто не забудьте добавить его обратно, если вам нужно расшифровать номер.)

Конечно, мой реальный вопрос: почему вы поворачиваете 8-байтовое значение фиксированной ширины и не используете его непосредственно в качестве «ключа» вместо строкового значения переменной длины?

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

Answer 8

Вам не нужно копировать ввод в num, потому что вы передаете его по значению. Вы также можете вычислить длину charset во время компиляции, нет необходимости вычислять ее во время выполнения каждый раз, когда вы вызываете функцию.

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

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

Кстати, а что если значение, переданное для ввода, равно нулю? Вы даже не войдете в петлю; не должен ли ключ тогда быть "0"?

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