有没有办法提高此查找的速度或效率？(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 MB,64位系统上的内存使用量超过400 MB.看起来我应该能够减少内存和/或提高速度,但我不知道如何.

如果有人能帮我弄清楚如何进一步优化这个表格,我将非常感激.

Answer 1

使用某种字符串构建器而不是重复串联到"键"将提供显着的速度提升.

Answer 2

您可能需要提前为您预留记忆string key.这可以为您带来不错的性能提升,以及内存利用率的提升.无论何时调用append运算符std::string,如果必须重新分配,它可能会使内部缓冲区的大小加倍.这意味着每个字符串可能占用的内存比存储字符所需的内存大得多.您可以通过提前为字符串保留内存来避免这种情况.

Answer 3

我同意Rob Walker的看法 - 你专注于改善错误领域的表现.字符串是最慢的部分.

我定时代码(你的原始文件被破坏,顺便说一句)和你的原始文件(修复后)是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);
}