ファイル内の単語の一意の出現をカウントし、それらのカウントをアルファベット順に表示するプログラムを作成しようとしています。
重要なのは、これを可能な限り最速かつ最も効率的な方法で行うことです。
私は C++ を使用してコードを記述していることを心に留めておいてください。ただし、純粋な理論的な答えに反対しているわけではありません。
推奨事項はありますか?
ファイル内の単語の一意の出現をカウントし、それらのカウントをアルファベット順に表示するプログラムを作成しようとしています。
重要なのは、これを可能な限り最速かつ最も効率的な方法で行うことです。
私は C++ を使用してコードを記述していることを心に留めておいてください。ただし、純粋な理論的な答えに反対しているわけではありません。
推奨事項はありますか?
以下は、cin を使用した例です。
#include <iostream>
#include <string>
#include <map>
using namespace std;
int main() {
string word;
std::map<std::string, int> word_count;
while (std::getline(cin, word, ' ')) {
word_count[word]++;
}
typedef std::map<std::string, int>::iterator iter;
iter end = word_count.end();
for(iter it = word_count.begin(); it != end; ++it) {
cout << it->first << ", count= " << it->second << endl;
}
return 0;
}
2 つの std::set を「1 回使用する単語」と「禁止された単語: 2 回以上使用する」で使用する必要があると思います。
つまり、処理する単語があります: cur_word です。禁止された単語に含まれている場合は無視し、許可された単語に含まれているかどうかを確認し、そこから削除して禁止された単語に追加し、そうでない場合は追加して許可された単語を実行します。
std::unordered_set
よりも高速になる場合がstd::set
あります (特にファイルが大きい場合)。
ただし、それによって大きな違いが生じる可能性は低いです。他のすべてを極端に悪く記述しない限り、ジョブは I/O に大きく依存することになるため、作業のほとんどを I/O の高速化に費やす必要があります。
そこからの進め方は対象OSによって異なると思われます。Linux の場合、ファイルの高速読み取りは、ほとんどの場合mmap
. Windows の場合、通常、メモリ マップされたファイルを避けReadFile
、FILE_FLAG_NO_BUFFERING
フラグと共に使用します。