1

实现查找表的最简单方法是使用带有 256 个字符(256 字节)的数组的查找表来检查字符是否为 alpha?我知道我可以使用 isalpha 函数,但是查找表应该更有效,需要一个比较而不是多个比较。我正在考虑将索引与 char 十进制转换相对应,并直接检查 char 是否等效。

4

6 回答 6

4

我一直使用这种单一的比较方法(我认为它的流水线更好),因为它比最多进行四次比较要快。

unsigned((ch&(~(1<<5))) - 'A') <= 'Z' - 'A' 

我对几种不同的方法进行了基准测试,并考虑了查找表方法的 TLB 缓存未命中。我在 Windows 上运行了基准测试。以下是字符集为 '0'..'z' 的时间:

lookup tbl no tlb miss:                        4.8265 ms
lookup table with tlb miss:                    7.0217 ms
unsigned((ch&(~(1<<5))) - 'A') <= 'Z' - 'A':  10.5075 ms
(ch>='A' && ch<='Z') || (ch>='a' && ch<='z'): 17.2290 ms
isalpha:                                      28.0504 ms

您可以清楚地看到语言环境代码是有代价的。

以下是字符集为 0..255 的时间:

tbl no tlb miss:                               12.6833 ms
unsigned((ch&(~(1<<5))) - 'A') <= 'Z' - 'A':   29.2403 ms
(ch>='A' && ch<='Z') || (ch>='a' && ch<='z'):  34.8818 ms
isalpha:                                       78.0317 ms
tbl with tlb miss:                            143.7135 ms

时间更长,因为测试了更多的字符。在第二次测试中,我用于 tlb“flush”的段数更大。可能是表查找方法比第一次运行所表明的 tlb 未命中受到的影响更大。您还可以看到,当字符为 alpha 时,单个 cmp 方法效果更好。

如果比较一行中的多个字符,查找表方法是最好的,但它并不比单个 cmp 方法好多少。如果您在这里和那里比较字符,那么 tlb 缓存未命中可能会使 tbl 方法比单个 cmp 方法更差。当字符更可能是字母时,单个 cmp 方法效果最好。

这是代码:

__forceinline bool isalpha2(BYTE ch) {
    return (ch>='A' && ch<='Z') || (ch>='a' && ch<='z');
}

__forceinline bool isalpha1(BYTE ch) {
    return unsigned((ch&(~(1<<5))) - 'A') <= 'Z' - 'A';
}
bool* aTbl[256];

int main(int argc, char* argv[]) 
{
    __int64 n = 0, cTries = 100000;
    int b=63;
    int ch0=' ', ch1 ='z'+1;
    ch0=0, ch1 = 256;
    // having 255 tables instead of one lets us "flush" the tlb.
    // Intel tlb should have about ~32 entries (depending on model!) in it, 
    // so using more than 32 tables should have a noticable effect.
    for (int i1=0 ; i1<256 ; ++i1) {
        aTbl[i1] = (bool*)malloc(16384);
        for (int i=0 ; i<256 ; ++i)
            aTbl[i1][i] = isalpha(i);
    }

    { CBench Bench("tbl with tlb miss");
        for (int i=1 ; i<cTries ; ++i) {
            for (int ch = ch0 ; ch < ch1 ; ++ ch) 
                n += aTbl[ch][ch];  // tlb buster
        }
    }
    { CBench Bench("tbl no tlb miss");
        for (int i=1 ; i<cTries ; ++i) {
            for (int ch = ch0 ; ch < ch1 ; ++ ch) 
                n += aTbl[0][ch];
        }
    }
    { CBench Bench("isalpha");
        for (int i=1 ; i<cTries ; ++i) {
            for (int ch = ch0 ; ch < ch1 ; ++ ch)
                n += isalpha(ch);
        }
    }
    { CBench Bench("unsigned((ch&(~(1<<5))) - 'A') <= 'Z' - 'A'");
        for (int i=1 ; i<cTries ; ++i) {
            for (int ch = ch0 ; ch < ch1 ; ++ ch)
                n += isalpha1(ch);
        }
    }
    { CBench Bench("(ch>='A' && ch<='Z') || (ch>='a' && ch<='z')");
        for (int i=1 ; i<cTries ; ++i) {
            for (int ch = ch0 ; ch < ch1 ; ++ ch) 
                n += isalpha2(ch);
        }
    }
    return n;
}


class  CBench {
public:
    __declspec(noinline) CBench(CBench* p) : m_fAccumulate(false), m_nTicks(0),
     m_cCalls(0), m_pBench(p), m_desc(NULL), m_nStart(GetBenchMark()) { }
    __declspec(noinline) CBench(const char *desc_in, bool fAccumulate=false) : 
     m_fAccumulate(fAccumulate), m_nTicks(0), m_cCalls(0), m_pBench(NULL), 
     m_desc(desc_in), m_nStart(GetBenchMark()) {    }
    __declspec(noinline) ~CBench() {
        __int64 n = (m_fAccumulate) ? m_nTicks : GetBenchMark() - m_nStart;
        if (m_pBench) {
            m_pBench->m_nTicks += n;
            m_pBench->m_cCalls++;
            return;
        } else if (!m_fAccumulate) {
            m_cCalls++;
        }
        __int64 nFreq;
        QueryPerformanceFrequency((LARGE_INTEGER*)&nFreq);
        double ms = ((double)n * 1000)/nFreq;
        printf("%s took: %.4f ms, calls: %d, avg:%f\n", m_desc, ms, m_cCalls,
             ms/m_cCalls);
    }
    __declspec(noinline) __int64 GetBenchMark(void) {
        __int64 nBenchMark;
        QueryPerformanceCounter((LARGE_INTEGER*)&nBenchMark);
        return nBenchMark;
    }
    LPCSTR     m_desc;
    __int64    m_nStart, m_nTicks;
    DWORD      m_cCalls;
    bool       m_fAccumulate;
    CBench*    m_pBench;
};
于 2014-06-16T02:14:52.730 回答
3

实际上,根据 Plauger 在“标准 C 库”[91]isalpha中的说法,通常使用查找表来实现。那本书确实过时了,但今天可能仍然如此。这是他对 isalpha 提出的定义

功能

int isalpha(int c)
{
    return (_Ctype[c] & (_LO|_UP|_XA));
}

#define isalpha(c) (_Ctype[(int)(c)] & (_LO|_UP|_XA))
于 2011-04-20T08:10:01.517 回答
3

记住优化的第一条规则:不要这样做。

然后记住第二条优化规则,很少应用:不要这样做。

然后,如果您确实遇到瓶颈并且您已确定isalpha原因,那么这样的事情可能会更快,具体取决于您的库如何实现该功能。您需要衡量环境中的性能,并且仅在确实有可衡量的改进时才使用它。这假设您不需要测试范围之外的值unsigned char(通常为 0...255);为此,您需要做一些额外的工作。

#include <cctype>
#include <climits>

class IsAlpha
{
public:
    IsAlpha()
    {
        for (int i = 0; i <= UCHAR_MAX; ++i)
            table[i] = std::isalpha(i);
    }

    bool operator()(unsigned char i) const {return table[i];}

private:
    bool table[UCHAR_MAX+1];
};

用法:

IsAlpha isalpha;

for (int i = 0; i <= UCHAR_MAX; ++i)
    assert(isalpha(i) == bool(std::isalpha(i)));
于 2011-04-20T09:07:35.197 回答
3

您的编译器库的实现可能非常有效,并且可能已经在大多数情况下使用查找表,但也处理一些可能有点棘手的情况,如果您要自己做的话isalpha()

  • 正确处理带符号的字符(在查找表上使用负索引)
  • 处理非 ASCII 语言环境

您可能不需要处理非 ASCII 语言环境,在这种情况下,您可能(也许)能够稍微改进库。

事实上,如果一个宏或函数只返回以下结果,我不会感到惊讶:

((('a' <= (c)) && ((c) <= 'z')) || (('A' <= (c)) && ((c) <= 'Z')))

可能比表查找更快,因为它不必占用内存。但我怀疑它会以任何有意义的方式更快,并且很难衡量差异,除非在一个只做isalpha()调用的基准测试中(这也可能会改善表查找结果,因为该表可能会在缓存中为许多的测试)。

而且isalpha()真的是瓶颈吗?对任何人?

只需使用编译器库中的那个。

于 2011-04-20T08:23:49.933 回答
0

如果您正在寻找字母字符 aZ,那么这比您的 255 数组要少得多。您可以从相关的 ASCII 字符(最低的字母字符)中减去“A”,这将是数组的索引。例如,'B' - 'A' 为 1。如果测试为负,则不是 alpha。如果大于您的最大 alpha ('z'),则它不是 alpha。

如果您完全使用 unicode,则此方法将不起作用。

于 2011-04-20T08:15:37.163 回答
0

我认为您可以比使用查找表更简单地实现 isalpha。使用字符 'a'-'z' 和 'A'-'Z' 在ASCII中连续的事实,这样的简单测试就足够了:

char c ;
// c gets some value
if(('A'<=c && 'Z'>=c) || ('a'<=c && 'z'>=c)) // c is alpha

请注意,这没有考虑不同的语言环境。

于 2011-04-20T08:16:17.880 回答