私は現在この種のループを持っています
while(1)
{
generate_string(&buffer);
for(int i = 0; i < filelines; i++)
{
if(strcmp(buffer,line[i]) == 0)
{
/* do something */
}
}
}
私は数百万の文字列を含むファイルを持っています（これは近いうちに半分に削減されることを願っています）、これらすべての文字列の数はファイル行に保存されます
line [i]は基本的に、文字列自体が格納される場所です。
現在、これらの百万の文字列の比較により、function generate_string（＆buffer）; 1秒間に約42回実行されます。Cで文字列比較を行うより速い方法はありますか？
strcmp通常、すべてのベンダーによって最適化されています。ただし、これに満足できない場合は、次のことを試すことができます。
libcは、5バイト未満の文字列を整数としてテストする場合、小さな文字列に対してこの最適化を行っていました。MSclには、小さな文字列用のいくつかの最適化もあります（調べてください）。しかし、もっと重要なことstrcmpは、あなたの本当のボトルネックであることを確認してください。
私はあなたを保証することができます、機能strcmpは絶対にボトルネックではありません。通常、strcmpは十分に最適化されており、アーキテクチャに応じて4/8バイトより長い文字列に対して32ビットまたは64ビットの比較を実行できます。newlibとGNUlibcの両方がこれを行います。ただし、両方の文字列の各バイトを20回見たとしても、ここで行ったアルゴリズムとデータ構造の選択ほど重要ではありません。
実際のボトルネックは、O（N）検索アルゴリズムです。ファイルでの単一のO（N log N）パスを使用して、O（log N）ルックアップを実行するための適切なデータ構造（通常のBST、トライ、または単純なソートされた配列）を使用できます。
ここで私と一緒に耐えてください-多くの数学が続きます。しかし、これは、アルゴリズムとデータ構造の選択が文字列比較の方法よりもはるかに重要である理由を説明する良い機会だと思います。スティーブはこれに触れていますが、もう少し詳しく説明したいと思います。
N = 1e6の場合、log（1e6、2）= 19.9であるため、理想的なデータ構造で20回の比較に切り上げます。
現在、O（N）または1e6操作の最悪の場合の検索を行っています。
つまり、O（log N）挿入時間で赤黒木を構築し、N個のアイテムを挿入するとします。これは、ツリーを構築するためのO（N log N）時間です。つまり、ツリーを構築するために必要な1e6x20または20e6の操作です。
現在のアプローチでは、データ構造の構築はO（N）または1e6操作ですが、最悪の場合の検索時間もO（N）です。したがって、ファイルを読み取って20回の検索操作を実行するまでに、理論上最悪の場合の21,000,000回の操作になります。比較すると、赤黒木と20回の検索での最悪のケースは、20,000,400回の操作、つまり、ソートされていない配列でのO（N）検索よりも999,600回の操作の方が優れています。つまり、20回の検索で、より洗練されたデータ構造が実際に成果を上げる最初のポイントになります。しかし、1000回の検索で何が起こるかを見てください。
ソートされていない配列=初期化+1000x検索時間=O（N）+ 1000 * O（N）= 1,000,000 + 2,000,000,000=2,001,000,000回の操作。
赤黒=初期化+1000x検索時間=O（N log N）+ 1000 * O（log N）= 20,000,000 + 20,000=20,020,000操作。
2,001,000,000 / 20,020,000〜= O（N）検索の100倍の操作。
1e6検索では、（1e6 + 1e6 * 1e6）/（20e6 + 1e6 * 20）=25,000倍の操作になります。
コンピュータが1分でlogN検索を実行するのに必要な40e6の「操作」を処理できると仮定します。現在のアルゴリズムで同じ作業を行うには、25,000分、つまり17日かかります。または、別の見方をすれば、O（log N）アルゴリズムが1,000,000を実行できる時間内に、O（N）検索アルゴリズムは39回の検索しか処理できないということです。そして、検索を増やすほど、醜くなります。
データ構造とアルゴリズムのより良い選択については、Steveからの回答を参照してください。私の唯一の追加の注意はqsort()、スティーブによって提案されたO（N * N）の最悪の場合の複雑さを持っているかもしれないということです。これは、ヒープソートまたはさまざまなツリーのようなもので得られるO（N log N）よりもはるかに悪いです。構造。
呼び出しを行う前に、問題の文字列の最初の文字を確認することで、少し時間を節約できます。明らかに、最初の文字が異なる場合は、strcmpを呼び出して残りをチェックする理由はありません。自然言語での文字の分布が不均一であるため、ペイオフは26：1ではなく、大文字のデータの場合は15：1のようになります。
#define QUICKIE_STRCMP(a, b) (*(a) != *(b) ? \
(int) ((unsigned char) *(a) - \
(unsigned char) *(b)) : \
strcmp((a), (b)))
使用している単語の辞書が明確に定義されている場合（つまり、strcmpからの戻り値は問題ありませんが、0 ==等しい）、たとえば、同じプレフィックスで始まるコマンドライン引数のセット（例：tcp-accept） 、tcp-rejectマクロを書き直し、ポインタ演算を実行して、最初の文字ではなくN番目の文字（この場合は4番目の文字）を比較します。例：
#define QUICKIE_STRCMP(a, b, offset) \
(*(a+offset) != *(b+offset))\ ? -1 : strcmp((a), (b)))
質問が正しければ、これまでに読んだすべての行に文字列があるかどうかを確認する必要があります。ファイル行からTRIEまたはさらに良いPatriciaツリーを使用することを提案します。このようにして、すべての行を調べる代わりに、文字列が存在するかどうかを直線的に確認できます（そして、もう少し手間をかけて-どこで）。
あなたはすでに最適化でコンパイルしていますよね？
Trieまたはハッシュテーブルのデータ構造がその場所の周りにあり、すぐに使用できる場合は、そうする必要があります。
それができない場合、おそらく処理を高速化するかなり簡単な変更は、line検索する文字列の生成を開始する前に、配列を1回ソートすることです。buffer次に、ソートされた配列での二分探索。必要な2つの関数は標準であるため、簡単qsortですbsearch。
ソートされた配列へのバイナリ検索は、ファイルラインではなく、ログ2（ファイルライン）の文字列比較についてのみ行う必要があります。generate_stringしたがって、あなたの場合、それは数百万ではなく、呼び出しごとに20程度の文字列比較です。あなたが与えた数字から、私は何も約束しませんが、それが20-25倍速くなることを合理的に期待できると思います。
strcmp()バイトごとに比較するマクロを使用することに対してベンチマークを行いました。マクロバージョンは、のバージョンと比較すると「非常に」高速ですstrcmp()。通常、文字列の比較では、よりもバイトコンパレータマクロを使用する方がはるかに高速ですstrcmp()。元：
#define str3_cmp(m, c0, c1, c2, c3) m[0] == c0 && m[1] == c1 && m[2] == c2 && m[3] == c3
これは、のそれに比べて「非常に」高速ですstrcmp()。しかし、それらを書き留めるのは面倒であり、文字列をcharごとに分割する必要があるため、ヘッダーファイルとして生成するための便利なPHPスクリプトを作成しました。
この文字列compareは、比較するサイズが正確にわかっているホットループで使用できますchar*。
#!/usr/bin/php
<?php
function generate_macro($num) : string {
$returner = "#define str".$num."cmp_macro(ptr, ";
for($x = 0; $x < $num; $x++){
$returner .= "c".$x;
if($x != $num-1){ $returner .= ", "; }
}
$returner .= ") ";
for($x = 0; $x < $num; $x++){
$returner .= "*(ptr+".$x.") == c".$x;
if($x != $num-1){ $returner .= " && "; }
}
return $returner;
}
function generate_static_inline_fn(&$generated_macro, $num) : string {
$generated_macro .= "static inline bool str".$num."cmp(const char* ptr, const char* cmp)".
"{\n\t\treturn str".$num."cmp_macro(ptr, ";
for($x = 0; $x < $num; $x++){
$generated_macro .= " *(cmp+".$x.")";
if($x != $num-1){ $generated_macro .= ", "; }
}
$generated_macro .= ");\n}\n";
return $generated_macro;
}
function handle_generation($argc, $argv) : void {
$out_filename = $argv[$argc-1];
$gen_macro = "";
for($x = 0; $x < $argc-2; $x++){
$macro = generate_macro($argv[$x+1])."\n";
$gen_macro .= generate_static_inline_fn($macro, $argv[$x+1]);
}
file_put_contents($out_filename, $gen_macro);
}
handle_generation($argc, $argv);
?>
このスクリプトは2つの引数を取ります。
char*比較しているでしょう。例：$ ./gen_faststrcmp.php 3 5 fast_strcmp.h
そしてこれはfast_strcmp.hコンテンツで生成されます
#define str3cmp_macro(ptr, c0, c1, c2) *(ptr+0) == c0 && *(ptr+1) == c1 && *(ptr+2) == c2
static inline bool str3cmp(const char* ptr, const char* cmp){
return str3cmp_macro(ptr, *(cmp+0), *(cmp+1), *(cmp+2));
}
#define str5cmp_macro(ptr, c0, c1, c2, c3, c4) *(ptr+0) == c0 && *(ptr+1) == c1 && *(ptr+2) == c2 && *(ptr+3) == c3 && *(ptr+4) == c4
static inline bool str5cmp(const char* ptr, const char* cmp){
return str5cmp_macro(ptr, *(cmp+0), *(cmp+1), *(cmp+2), *(cmp+3), *(cmp+4));
}
そして、あなたのコードでは、そのような関数を使うことができます、
const char* compare_me = "Hello";
if(str5cmp(compare_me, "Hello")) { /* code goes here */ }
文字列の比較を行うために呼び出すよりも速い方法があるかどうかはわかりませんが、strcmpおそらくそれほど多くの呼び出しを避けることができます。strcmpハッシュテーブルを使用して文字列を格納すると、の文字列がbufferハッシュテーブルにあるかどうかを確認できます。「何かをする」ときにヒットのインデックスが重要な場合、テーブルは文字列をインデックスにマップできます。
この場合、プログラムは実際にはソートされませんが、等しいかどうかを比較するため、バイナリ比較でうまくいく可能性があります。
事前に長さを決定することで、ここで比較速度を向上させることもできます（もちろん、長さが十分に異なる場合）。ここで長さが合わない場合はdo something発生しません。
もちろん、ここでのハッシュは、ハッシュされた値を読み取る回数に応じて、別の考慮事項になります。
最初の文字に基づいたスクリーニングのような「安い」ものを試すことができます。最初の文字が一致しない場合、文字列を等しくすることはできません。それらが一致する場合は、strcmpを呼び出して文字列全体を比較します。状況に適している場合は、より良いアルゴリズムを検討することをお勧めします。例としては、ファイル/行の並べ替え、バイナリ検索の実行、ハッシュテーブルの使用、または同様の文字列テーブルの手法があります。
文字列の長さによって異なります。
長すぎない場合は、バイトごとに比較してみてください。
str[0] == str2[0] && str[1] == str2[1] && str[2] == str2[2]
それ以外の場合は、を使用memcmp()して、メモリのチャンクを比較します。
strcmp通常の文字列に使用します。しかし、文字列が本当に長い場合は、を使用できますmemcmp。メモリのチャンクを比較します。