c++ - 处理一长串单词。是否可以同时分批处理？

Question

目前我有一个包含 36,000 个单词的列表。我有一个将它们全部设置为小写的过程(简单且不到一秒钟)，然后我决定使用一个代码来检查这些单词中的任何一个是否是另一个单词的变位词。

我使用这个片段来检查它们是否是一个字谜:

bool is_anagram(string s1, string s2) {
    string c1(s1), c2(s2);
    if(c1.length() != c2.length())
        return 0;
    sort(c1.begin(), c1.end());
    sort(c2.begin(), c2.end());
    return c1 == c2;
}

现在使用该代码，我将代码分类到两个容器中。一个用于字谜，另一个用于非字谜。请注意，因为我不想重复，所以我使用的是集合而不是 vector 。这是排序函数:

template<typename Container>
void sort_anagrams ( Container& unsorted, Container& yes, Container& no ) {
    for( auto x : unsorted ) {
        for ( auto y : unsorted ) {
            if ( is_anagram ( x, y ) && y != x ) {
                cout << "yes "<< x << " " << y << endl;
                yes.insert(y);
            }else {
                cout << "no "<< x << " " << y << endl;
                no.insert(y);
            }   
        }
    }
}

这是主要的，以防万一有人想使用这个明显“糟糕”的代码:

int main() {
    set<string> initial;
    set<string> anagrams;
    set<string> trash;
    string input;
    string newline = "\n";
    ofstream os("output.txt", ios::out | ios::trunc | ios::binary);

    while(cin >> input) {
        initial.insert(input);
    }

    sort_anagrams ( initial, anagrams, trash );

    cout << "printing" << endl;

    for ( auto x : anagrams ) {
        cout << x << endl;
        if(os.good()) {
            os.write(x.c_str(), sizeof(char)*x.size() );
            os.write(newline.c_str(), sizeof(char)*newline.size() );            
        }
    }

    return 1;   
}

tl:dr，我正在尝试运行一个我没有优化得很好的过程，而且它一直在运行。我知道有更好的方法来处理这个列表，但我想从中学到的是，当我运行这段代码并分块处理列表时，我是否能够打开这个过程的多个版本。例如，这是我的一行列表:{ > [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] }

我想学的是这样处理:

{ > [] [] [] > [] [] [] > [] [] [] > [] [] [] > [] [] [] > [] [] [] > [] [ ] []

是否存在类似的东西？

Answer 1

这应该非常有效(c++11、c++03 将使用 map<> 和 set<>)。

不需要多线程，因为它不会增加任何性能。线程在访问集合映射时需要相互阻塞。

编辑:更新为从 stdin 获取单词列表并将变位词列表仅发送到 stdout

#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <iterator>
#include <algorithm>

std::unordered_map<std::string, std::unordered_set<std::string>> anagram_map;

using namespace std;

auto main() -> int
{
    while (cin) {
        string word;
        cin >> word;
        auto sorted = word;
        sort(begin(sorted), end(sorted));
        anagram_map[sorted].insert(word);
    }

    // now we have sets of distinct words indexed by sorted letters

    for (const auto& map_entry : anagram_map)
    {
        const auto& anagrams = map_entry.second;
        if (anagrams.size() > 1)
        {
            // this is the code path where we have anagrams for a set of letters
            auto sep = "";
            for (const auto& word : anagrams) {
                cout << sep << word;
                sep = " ";
            }
            cout << endl;
        }

    }
    return 0;
}

使用示例(unix，windows下很相似):

$ cat > words.txt
boy yob head pane nape planet plate tape pate
<ctrl-d>

$ c++ -o anagram -std=c++11 -stdlib=libc++ anagram.cpp
... or if you are using gcc ...
$ g++ -o anagram -std=c++11 anagram.cpp
$ ./anagram < words.txt > anagrams.txt
$ cat anagrams.txt
pate tape
nape pane
yob boy