0

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

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

#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);
}
4

1 回答 1

0

您可以一次加载 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（这很可能），那么它在效率方面可能还不错。

于 2018-02-11T01:39:49.233 回答