C++中的短(ASCII码，7位/字符)字符串存储和比较优化

Question

在我的项目中，我使用了大量的7位ASCII码的短字符串，并且必须以最高的性能处理(存储、比较、搜索等)这些字符串。基本上，我构建了一些uint64_t类型的Index数组，每个元素存储一个单词的9个字符，并将该索引用作任何字符串比较操作的Numeric元素。目前的实现运行得很快，但如果你愿意的话，也有可能改进一下。

此函数最多可将9个初始字符转换为Strcmp值-该数字的任何比较都等同于标准的“uint64_t”函数。

#include <cstdint>
#include <iostream>

uint64_t cnv(const char* str, size_t len)
{
    uint64_t res = 0;

    switch (len)
    {
    default:
    case 9: res = str[8];
    case 8: res |= uint64_t(str[7]) << 7;
    case 7: res |= uint64_t(str[6]) << 14;
    case 6: res |= uint64_t(str[5]) << 21;
    case 5: res |= uint64_t(str[4]) << 28;
    case 4: res |= uint64_t(str[3]) << 35;
    case 3: res |= uint64_t(str[2]) << 42;
    case 2: res |= uint64_t(str[1]) << 49;
    case 1: res |= uint64_t(str[0]) << 56;
    case 0: break;
    }

    return res;
}

int main()
{
    uint64_t v0 = cnv("000", 3);
    uint64_t v1 = cnv("0000000", 7);

    std::cout << (v1 < v0);
}

Answer 1

您可以一次加载8个字节的原始字符串，然后将它们压缩到一个结果整数中(如果您的机器具有小端数字表示，则可以反转它们)。

#include <iostream>

uint64_t ascii2ulong (const char  *s, int len)
{
    uint64_t i = (*(uint64_t*)s);
    if (len < 8) i &= ((1UL << (len<<3))-1);
#ifndef BIG_ENDIAN
    i = (i&0x007f007f007f007fUL) | ((i & 0x7f007f007f007f00) >> 1);
    i = (i&0x00003fff00003fffUL) | ((i & 0x3fff00003fff0000) >> 2);
    i = ((i&0x000000000fffffffUL) << 7) | ((i & 0x0fffffff00000000) << (7-4));
    // Note: Previous line: an additional left shift of 7 is applied
    // to make room for s[8] character
#else
    i = ((i&0x007f007f007f007fUL) << 7)  | ((i & 0x7f007f007f007f00) >> 8);
    i = ((i&0x00003fff00003fffUL) << 14) | ((i & 0x3fff00003fff0000) >> 16);
    i = ((i&0x000000000fffffffUL) << (28+7)) | ((i & 0x0fffffff00000000) >> (32-7));
#endif

    if (len > 8) i |= ((uint64_t)s[8]);
    return i;
}


//Test
std::string ulong2str(uint64_t compressed) {
    std::string s;
    for (int i = 56; i >= 0; i-=7) 
        if (char nxt=(compressed>>i)&0x7f) s+= nxt;
    return s;
}
int main() {
    std::cout << ulong2str(ascii2ulong("ABCDEFGHI", 9))<<std::endl;
    std::cout << ulong2str(ascii2ulong("ABCDE", 5))<<std::endl;
    std::cout << (ascii2ulong("AB", 2) < ascii2ulong("B", 1))<<std::endl;
    std::cout << (ascii2ulong("AB", 2) < ascii2ulong("A", 1))<<std::endl;
    return 0;
}

但请注意:这样做会正式违反分配的地址范围(如果您的原始字符串分配了<8字节)。如果运行具有内存健全性检查的程序，则可能会产生运行时错误。为了避免这种情况，您当然可以使用memcpy来代替uint64_t i = (*(uint64_t*)s);复制所需的字节数

uint64_t i;
memcpy(&i,s,std::min(len,8));

如果在您的机器上(很可能)对memcpy使用了一些硬件加速，那么就效率而言，这可能是不错的。