代码之家  ›  专栏  ›  技术社区  ›  jakogut

有没有办法提高查找的速度或效率?(C/C++)

  •  1
  • jakogut  · 技术社区  · 15 年前

    我编写了一个函数,用于将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。看起来我应该能够减少内存和/或提高速度,但我不确定如何做到。

    如果有人能帮我找出如何进一步优化这个表,我将不胜感激。

    8 回复  |  直到 8 年前
        1
  •  6
  •   Rob Walker    15 年前

    使用某种字符串生成器而不是重复连接到“key”中,可以显著提高速度。

        2
  •  6
  •   Charles Salvia    15 年前

    您可能需要提前为您的应用程序保留内存 string key std::string

        3
  •  5
  •   Aaron    15 年前

    我同意罗伯·沃克的观点——你把注意力集中在了错误的领域。绳子是最慢的部分。

    我对代码进行了计时(顺便说一句,您的原始代码已损坏),您的原始代码(修复时)为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);
    }
    
        4
  •  2
  •   Mark Bessey    15 年前

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


    编辑:这是我突然想到的。它还允许您指定任何所需的基准:

    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;
    }
    

        5
  •  1
  •   wilhelmtell    15 年前

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

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

    顺便问一下,如果传入的输入值为零会怎么样?你甚至不会进入循环;那么键不应该是“0”吗?

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

        6
  •  1
  •   jmucchiello    15 年前

    为什么不直接使用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字节值,而不直接将其用作“键”,而不是可变长度的字符串值?

    注:我很清楚这方面的endian问题。他没有说密钥将用于什么,所以我假设它没有被用于具有不同端点的机器之间的网络通信。

        7
  •  1
  •   Zan Lynx    15 年前

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

        8
  •  1
  •   mfx    15 年前

    如果您只需要一个短字符串键,那么转换为base-64数字将大大加快速度,因为div/mod 64非常便宜(shift/mask)。