文章/答案/技术大牛

发布

社区首页 >问答首页 >嵌入式C- switch/case和hashtable之间的选择

问嵌入式C- switch/case和hashtable之间的选择
EN

Stack Overflow用户

提问于 2016-08-31 15:18:27

回答 3查看 508关注 0票数 3

我在一个自制的板上工作，用的是ARM芯片，用的是C语言。我的代码必须执行得很快，而且我也有空间限制。现在，我必须编写一个十六进制值的“解析器”。每个十六进制数必须与一个十进制数(1；2；3或4)关联。目前，我认为它在未来不会有太大变化，我有100个十六进制值要解析。十六进制值是“随机的”，没有特定的模式。

我从一个开关/案例开始，就像这样：

switch (i)
{   
case 0xF3:
case 0xF7:
case 0x02:
    return 1;
    break;

case 0x20:
case 0x40:
case 0xE0:
case 0xC0:
    return 2;
    break;

case 0x21:
case 0x41:
case 0x81:
case 0x61:
case 0xA1:
    return 3;
    break;


case 0xBB:
case 0xCC:
case 0x63:
    return 4;
    break;

default:
    return 0;
    break;
}

但我考虑的是一个哈希表。当然，在最坏的情况下它会更快，但它会占用更多的空间，对于100个值来说，哈希表真的值得吗？

谢谢你的回答，如果你想要精确的答案，尽管问吧！

安托万

回答 3

Stack Overflow用户

发布于 2016-08-31 15:30:41

您可以将值放在256字节的数组中，以便快速访问：

static uint8_t const table[256] = { 2, 3, 1, 4, ... };
return table[i];

您只使用了256个值中的100个，因此存在浪费空间的“漏洞”，但它可以与switch竞争。

但是因为你只需要4个值，所以这些值可以用2比特来表示。您可以将四个值打包到一个字节中。只需使用值0-3而不是1-4：

#define PACK4(a, b, c, d) \
    (((a)-1 << 0) | ((b)-1 << 2) | ((c)-1 << 4) | ((d)-1 << 6))
static uint8_t const table[64] = { PACK4(2, 3, 1, 4), PACK4(... };
int byteOffset = i / 4;
int bitOffset = i % 4 * 2;
return (table[byteOffset] >> bitOffset & 0x03) + 1;

票数 3

Stack Overflow用户

发布于 2016-08-31 17:06:53

正如您已经注意到的，有两种方法可以实现这一点。

为了确定哪种方法是有利的，您需要从两个方面分析每种方法：

执行性能空间(memory consumption)

Time (
)

但是，您的问题的答案取决于平台。

为了分析内存消耗，您需要编译这两个函数，检查反汇编，并确定每个函数使用的内存量。请记住，内存不仅用于变量，还用于代码。

为了分析执行性能，您基本上需要大量运行这两个函数，并测量每个函数的平均持续时间。请记住，运行时间还取决于底层HW架构部署的缓存启发式，因此，例如，如果您在第二个函数之后立即测试第一个函数，然后在第一个函数之后再次测试第二个函数，则结果不一定是一致的。

以下是我的平台上的内存消耗分析(基于x64的VS2013编译器)：

方法1:

uint8_t func1(uint8_t i)
{
    switch (i)
    {   
        case 0x02:
        case 0xF3:
        case 0xF7:
            return 1;
        case 0x20:
        case 0x40:
        case 0xC0:
        case 0xE0:
            return 2;
        case 0x21:
        case 0x41:
        case 0x61:
        case 0x81:
        case 0xA1:
            return 3;
        case 0x63:
        case 0xBB:
        case 0xCC:
            return 4;
        default:
            return 0;
    }
}

分解成114字节的代码：

00007FF778131050  mov         byte ptr [rsp+8],cl  
00007FF778131054  push        rdi  
00007FF778131055  sub         rsp,10h  
00007FF778131059  mov         rdi,rsp  
00007FF77813105C  mov         ecx,4  
00007FF778131061  mov         eax,0CCCCCCCCh  
00007FF778131066  rep stos    dword ptr [rdi]  
00007FF778131068  movzx       ecx,byte ptr [i]  
00007FF77813106D  movzx       eax,byte ptr [i]  
00007FF778131072  mov         dword ptr [rsp],eax  
00007FF778131075  mov         eax,dword ptr [rsp]  
00007FF778131078  sub         eax,2  
00007FF77813107B  mov         dword ptr [rsp],eax  
00007FF77813107E  cmp         dword ptr [rsp],0F5h  
00007FF778131085  ja          $LN5+10h (07FF7781310B6h)  
00007FF778131087  movsxd      rax,dword ptr [rsp]  
00007FF77813108B  lea         rcx,[__ImageBase (07FF778130000h)]  
00007FF778131092  movzx       eax,byte ptr [rcx+rax+10D4h]  
00007FF77813109A  mov         eax,dword ptr [rcx+rax*4+10C0h]  
00007FF7781310A1  add         rax,rcx  
00007FF7781310A4  jmp         rax  
00007FF7781310A6  mov         al,1  
00007FF7781310A8  jmp         $LN5+12h (07FF7781310B8h)  
00007FF7781310AA  mov         al,2  
00007FF7781310AC  jmp         $LN5+12h (07FF7781310B8h)  
00007FF7781310AE  mov         al,3  
00007FF7781310B0  jmp         $LN5+12h (07FF7781310B8h)  
00007FF7781310B2  mov         al,4  
00007FF7781310B4  jmp         $LN5+12h (07FF7781310B8h)  
00007FF7781310B6  xor         al,al  
00007FF7781310B8  add         rsp,10h  
00007FF7781310BC  pop         rdi  
00007FF7781310BD  ret  
00007FF7781310BE  xchg        ax,ax  
00007FF7781310C0  cmps        byte ptr [rsi],byte ptr [rdi]  
00007FF7781310C1  adc         byte ptr [rax],al

方法2:

uint8_t func2(uint8_t i)
{
    static const uint8_t hash_table[] =
    {
    /*  0x0, 0x1, 0x2, 0x3, 0x4, 0x5, 0x6, 0x7, 0x8, 0x9, 0xA, 0xB, 0xC, 0xD, 0xE, 0xF, */
          0,   0,   1,   0,   0,   0,   0,   0,   0,   0,    0,   0,   0,   0,   0,  0, /* 0x00 - 0x0F */
          0,   0,   0,   0,   0,   0,   0,   0,   0,   0,    0,   0,   0,   0,   0,  0, /* 0x10 - 0x1F */
          2,   3,   0,   0,   0,   0,   0,   0,   0,   0,    0,   0,   0,   0,   0,  0, /* 0x20 - 0x2F */
          0,   0,   0,   0,   0,   0,   0,   0,   0,   0,    0,   0,   0,   0,   0,  0, /* 0x30 - 0x3F */
          2,   3,   0,   0,   0,   0,   0,   0,   0,   0,    0,   0,   0,   0,   0,  0, /* 0x40 - 0x4F */
          0,   0,   0,   0,   0,   0,   0,   0,   0,   0,    0,   0,   0,   0,   0,  0, /* 0x50 - 0x5F */
          0,   3,   0,   4,   0,   0,   0,   0,   0,   0,    0,   0,   0,   0,   0,  0, /* 0x60 - 0x6F */
          0,   0,   0,   0,   0,   0,   0,   0,   0,   0,    0,   0,   0,   0,   0,  0, /* 0x70 - 0x7F */
          0,   3,   0,   0,   0,   0,   0,   0,   0,   0,    0,   0,   0,   0,   0,  0, /* 0x80 - 0x8F */
          0,   0,   0,   0,   0,   0,   0,   0,   0,   0,    0,   0,   0,   0,   0,  0, /* 0x90 - 0x9F */
          0,   3,   0,   0,   0,   0,   0,   0,   0,   0,    0,   0,   0,   0,   0,  0, /* 0xA0 - 0xAF */
          0,   0,   0,   0,   0,   0,   0,   0,   0,   0,    0,   4,   0,   0,   0,  0, /* 0xB0 - 0xBF */
          2,   0,   0,   0,   0,   0,   0,   0,   0,   0,    0,   0,   4,   0,   0,  0, /* 0xC0 - 0xCF */
          0,   0,   0,   0,   0,   0,   0,   0,   0,   0,    0,   0,   0,   0,   0,  0, /* 0xD0 - 0xDF */
          2,   0,   0,   0,   0,   0,   0,   0,   0,   0,    0,   0,   0,   0,   0,  0, /* 0xE0 - 0xEF */
          0,   0,   0,   1,   0,   0,   0,   1,   0,   0,    0,   0,   0,   0,   0,  0, /* 0xF0 - 0xFF */
    };
    return hash_table[i];
}

分解成23个字节的代码：

00007FF778131030  mov         byte ptr [rsp+8],cl  
00007FF778131034  push        rdi  
00007FF778131035  movzx       eax,byte ptr [i]  
00007FF77813103A  lea         rcx,[hash_table (07FF7781368C0h)]  
00007FF778131041  movzx       eax,byte ptr [rcx+rax]  
00007FF778131045  pop         rdi  
00007FF778131046  ret

当然，还有256字节的数据。

以下是几个注意事项：

，

，你在问题中提到，在最坏的情况下，使用哈希表比使用switch/case语句更快。现在，尽管这不是由C语言标准规定的，并且每个编译器可能会以不同的方式处理switch/case语句，但是switch/case语句通常由单个分支组成，因此对于每种情况执行的操作量是相同的。
请注意，我已经将hash_table变量声明为static。因此，这个数组驻留在数据段中，而不是堆栈中，并且被初始化为可执行映像的一部分(即，硬编码)，而不是每次调用函数时。同样，这不是C语言标准所规定的东西，但大多数C编译器都以相同的方式处理它。我不能说它会改善内存消耗，因为它取决于分配给每个段(数据段和堆栈)的初始内存量。但这肯定会提高执行性能，因为哈希表将在可执行映像加载到内存时进行初始化。

票数 1

Stack Overflow用户

发布于 2016-08-31 17:09:36

您可以使用查找表在O(1)空间中完成此操作：

#include <stdio.h>

static const unsigned char keymap[] = {
    0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
    2,3,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
    2,3,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
    0,3,0,4,0,0,0,0,0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
    0,3,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
    0,3,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,0,0,0,4,0,0,0,0,
    2,0,0,0,0,0,0,0,0,0,0,0,4,0,0,0,
    0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
    2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
    0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,0
};

static int find(int id)
{
    if ((id >= 0) && (id < 256)) {
        return keymap[id];
    }
    return 0;
}

int main(void)
{
    int id = 0x20;

    printf("%d\n", find(id));
    return 0;
}

输出：

票数 1

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/39243121

复制

相似问题

问嵌入式C- switch/case和hashtable之间的选择
EN

回答 3

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问嵌入式C- switch/case和hashtable之间的选择EN

回答 3

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问嵌入式C- switch/case和hashtable之间的选择
EN