1

我编写了一个函数，用于将 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 4 个字符串，生成如下：

// 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。似乎我应该能够减少内存和/或提高速度，但我不确定如何。

如果有人可以帮助我弄清楚如何进一步优化此表，我将不胜感激。

4

8 回答 8

6

使用某种字符串生成器而不是重复连接到“键”将提供显着的速度提升。

于 2009-11-09T22:07:59.860 回答
6

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

于 2009-11-09T22:08:44.417 回答
5

我同意 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);
}
于 2009-11-09T22:26:45.287 回答
2

这几乎是如何不这样做的教科书案例。在循环中连接字符串是一个坏主意，因为追加不是特别快，而且因为您不断地分配内存。

注意：您的问题表明您正在转换为 base-62，但代码似乎有 63 个符号。你想做什么？

给定一个 64 位整数，您可以计算出结果中不需要超过 11 位数字，因此使用静态 12 字符缓冲区肯定有助于提高速度。另一方面，您的 C++ 库很可能具有与 ultoa 等效的 long-long，这将是非常理想的。

编辑：这是我整理的东西。它还允许您指定任何所需的基础：

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 对象，并且不会不必要地移动内存。它目前不会对输出进行零填充，但是将其更改为您想要的输出位数是微不足道的。

于 2009-11-09T22:30:26.430 回答
1

如果您只需要一个短字符串键，则转换为 base-64 数字会大大加快速度，因为 div/mod 64 非常便宜（移位/掩码）。

于 2009-11-19T16:51:34.210 回答
1

您不需要将输入复制到 num 中，因为您按值传递它。您还可以在编译时计算字符集的长度，无需在每次调用函数时都在运行时计算它。

但这些都是非常小的性能问题。我认为您可以获得的最重要的帮助是避免循环中的字符串连接。当您构造键字符串时，将结果字符串的长度传递给字符串构造函数，以便该字符串只有一个分配。然后在循环中，当您连接到字符串时，您将不会重新分配。

如果您将目标字符串作为参考参数，或者甚至像标准算法那样使用两个迭代器，您可以使事情变得更加高效。但这可以说是走得太远了。

顺便说一句，如果传入的输入值为零怎么办？你甚至不会进入循环；键不应该是“0”吗？

我看到传入的输入值不能为负，但我们注意到：C 余数运算符不是模运算符。

于 2009-11-09T22:25:38.017 回答
1

为什么不直接使用 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);
}

是的，每个字符串都将以相同的大小结尾。如果你不想要它，去掉等号。（如果您需要解码数字，请记住将其添加回来。）

当然，我真正的问题是为什么你要转换一个固定宽度的 8byte 值而不是直接使用它作为你的“键”而不是可变长度的字符串值？

脚注：我很清楚与此有关的字节序问题。他没有说密钥将用于什么，所以我认为它没有用于不同字节序的机器之间的网络通信。

于 2009-11-09T22:48:59.357 回答
1

如果您可以再添加两个符号以便将其转换为 base-64，则您的模数和除法运算将变成位掩码并移位。比除法快得多。

于 2009-11-10T14:53:13.133 回答