文字がアルファであるかどうか、または配列256文字（256バイト）のルックアップテーブルを使用していないかどうかを確認するルックアップテーブルを実装する最も簡単な方法は何ですか？isalpha関数を使用できることは知っていますが、ルックアップテーブルの方がおそらく効率的であり、複数の比較ではなく1つの比較が必要です。インデックスをcharの10進変換に対応させ、charがそれと同等であるかどうかを直接確認することを考えていました。
2490 次
6 に答える
4
最大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
より多くの文字がテストされたため、時間が長くなります。2番目のテストでは、tlbの「フラッシュ」に使用したセグメントの数が多かった。テーブルルックアップメソッドは、最初の実行が示すよりもtlbミスの影響を受けている可能性があります。また、文字がアルファの場合、単一の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
実際、「The Standard C Library」[91]のPlaugerによると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()。
- 符号付き文字を正しく処理する（ルックアップテーブルで負のインデックスを使用）
- 非ASCIIロケールの処理
非ASCIIロケールを処理する必要がない場合があります。その場合、（おそらく）ライブラリをわずかに改善できる可能性があります。
実際、次の結果を単に返すマクロまたは関数であっても、私は驚かないでしょう。
((('a' <= (c)) && ((c) <= 'z')) || (('A' <= (c)) && ((c) <= 'Z')))
メモリをヒットする必要がないため、テーブルルックアップよりも高速である可能性があります。しかし、意味のある方法で高速になるとは思えません。また、isalpha()呼び出し以外の何もしなかったベンチマークを除いて、違いを測定するのは難しいでしょう（テーブルは多くの場合キャッシュにある可能性があるため、テーブルルックアップの結果も改善される可能性があります）テストの）。
そして、isalpha()本当にボトルネックですか？誰にも？
コンパイラのライブラリにあるものを使用するだけです。
于 2011-04-20T08:23:49.933 に答える
3
最適化の最初のルールを覚えておいてください：それをしないでください。
次に、非常にまれに適用される最適化の2番目のルールを覚えておいてください。まだ実行しないでください。
次に、実際にボトルネックが発生して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 に答える
0
アルファベット文字aZを探している場合、255配列よりもはるかに少ない文字です。問題のASCII文字（最も低いアルファベット文字）から「A」を引くことができます。これは、配列のインデックスになります。たとえば、「B」-「A」は1です。テストが負の場合、アルファではありません。最大アルファ（'z'）より大きい場合、それはアルファではありません。
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 に答える