2

明確にするために、タイトルも少しばかげていると思います。言語のほとんどの組み込み関数が非常によく書かれており、高速であることは誰もが知っています (アセンブリで記述された関数もあります)。私の状況に対するアドバイスがまだいくつかあるかもしれませんが。検索エンジンの動作を示す小さなプロジェクトがあります。インデックス作成フェーズでは、キーワードから不要なものを除外するためのフィルター メソッドがあります。それはここにあります：

bool Indexer::filter(string &keyword)
{
    // Remove all characters defined in isGarbage method
    keyword.resize(std::remove_if(keyword.begin(), keyword.end(), isGarbage) - keyword.begin());

    // Transform all characters to lower case
    std::transform(keyword.begin(), keyword.end(), keyword.begin(), ::tolower);

    // After filtering, if the keyword is empty or it is contained in stop words list, mark as invalid keyword
    if (keyword.size() == 0 || stopwords_.find(keyword) != stopwords_.end())
        return false;

    return true;
}

最初の兆候として、これらの関数 (すべて STL コンテナーのメンバー関数または標準関数) は高速であり、インデックス作成フェーズにそれほど時間はかからないはずです。しかし、Valgrind でプロファイリングした後では、これを含めた総コストはfilter33.4% と非常に高くなります。このフィルターの 3 つの標準関数は、そのパーセンテージにほとんどの時間をstd::remove_if要します: 6.53%、std::set::find15.07%、std::transform7.71% です。

したがって、このフィルターによって命令時間のコストを削減するためにできること (または変更すること) があれば (並列化などを使用するなど)、アドバイスをお願いします。前もって感謝します。

更新: ご提案いただきありがとうございます。簡単に言えば、私がする必要があることを要約しました: 1) マージtolowerしremove_if、独自のループを作成して 1 つにします。2)より高速な方法unordered_setの代わりに使用します。したがって、私は を正しい答えとして選択しました。setfindMark_B

4

7 に答える 7

2

ブースト フィルター イテレーターを使用する場合は、remove_ifandtransformを 1 つにマージできます (未テスト):

keyword.erase(std::transform(boost::make_filter_iterator(!boost::bind(isGarbage), keyword.begin(), keyword.end()),
                             boost::make_filter_iterator(!boost::bind(isGarbage), keyword.end(), keyword.end()),
                             keyword.begin(),
                            ::tolower), keyword.end());

これは、文字列を変更した場合の副作用が外部から見えるようにしたい場合を想定しています。それ以外の場合は、const代わりに参照渡ししcount_if、述語を使用してすべてを 1 つにします。「インプレース」マッチングを可能にするストップワードのリストの階層データ構造（基本的にはツリー）をSELECT, SELECTION, SELECTED構築できます。たとえば、ストップワードがツリーを構築する場合：

|- (その他/空を受け入れる)
\- SELECT- (空、失敗)
             |- (その他、受け入れる)
             |- イオン (失敗)
             \- ED (失敗)

文字列自体を変更することなく、変換とフィルタリングを同時に行いながら、そのようなツリー構造をたどることができます。実際には、マルチキャラクターの実行をツリー内の単一のノードに圧縮する必要があります (おそらく)。

次のようなものを使用して、このようなデータ構造をかなり簡単に構築できます。

#include <iostream>
#include <map>
#include <memory>

class keywords {
  struct node {
        node() : end(false) {}
    std::map<char, std::unique_ptr<node>> children;
        bool end;
  } root;

  void add(const std::string::const_iterator& stop, const std::string::const_iterator c, node& n) {
    if (!n.children[*c])
      n.children[*c] = std::unique_ptr<node>(new node);

    if (stop == c+1) {
      n.children[*c]->end = true;
      return;
    }
    add(stop, c+1, *n.children[*c]);
  }
public:
  void add(const std::string& str) {
    add(str.end(), str.begin(), root);
  }

  bool match(const std::string& str) const {
    const node *current = &root;
    std::string::size_type pos = 0;
    while(current && pos < str.size()) {
      const std::map<char,std::unique_ptr<node>>::const_iterator it = current->children.find(str[pos++]);
      current = it != current->children.end() ? it->second.get() : nullptr;
    }
    if (!current) {
      return false;
    }
    return current->end;
  }
};

int main() {
  keywords list;
  list.add("SELECT");
  list.add("SELECTION");
  list.add("SELECTED");
  std::cout << list.match("TEST") << std::endl;
  std::cout << list.match("SELECT") << std::endl;
  std::cout << list.match("SELECTOR") << std::endl;
  std::cout << list.match("SELECTED") << std::endl;
  std::cout << list.match("SELECTION") << std::endl;
}

これは期待どおりに機能し、次の結果が得られました。

0
1
0
1
1

次にmatch()、変換およびフィルタリング関数を適切に呼び出すように変更する必要があります。

const char c = str[pos++];
if (filter(c)) {
  const std::map<char,std::unique_ptr<node>>::const_iterator it = current->children.find(transform(c));
}

これを少し最適化して (コンパクトな長い単一文字列の実行)、より一般的なものにすることができますが、1 つのパスですべてをインプレースで実行する方法を示しており、それが示した関数を高速化する可能性が最も高い候補です。

（もちろんベンチマークは変わります）

于 2012-05-01T15:40:29.977 に答える
2

まず、コンパイル時に最適化とインライン化が有効になっていることを確認しますか?

その場合は、最初に、ゴミの削除と小文字化を 1 つのステップにまとめて、2 回目のキーワードの反復を防ぐ独自のトランスフォーマーを作成してみます。

unordered_setコメントで提案されているような別のコンテナを使用せずに検索についてできることはあまりありません。

あなたのアプリケーションにとって、フィルタリングを実行することは、操作の中で本当に CPU を集中的に使用する部分である可能性はありますか?

于 2012-05-01T15:29:21.840 に答える
1

isGarbage() の呼び出しに同期が必要ない場合は、並列化を最初に検討する最適化にする必要があります (もちろん、1 つのキーワードをフィルター処理するだけでも十分に大きなタスクであるため、それ以外の場合は並列化を 1 レベル上で行う必要があります)。これを行う方法は次のとおりです-元のデータを1回のパスで、スレッド化ビルディングブロックを使用してマルチスレッド化します。

    bool isGarbage(char c) {
    return c == 'a';
}

struct RemoveGarbageAndLowerCase {
    std::string result;
    const std::string& keyword;

    RemoveGarbageAndLowerCase(const std::string& keyword_) : keyword(keyword_) {}

    RemoveGarbageAndLowerCase(RemoveGarbageAndLowerCase& r, tbb::split) : keyword(r.keyword) {}

    void operator()(const tbb::blocked_range<size_t> &r) {
        for(size_t i = r.begin(); i != r.end(); ++i) {
            if(!isGarbage(keyword[i])) {
                result.push_back(tolower(keyword[i]));
            }
        }
    }

    void join(RemoveGarbageAndLowerCase &rhs) {
        result.insert(result.end(), rhs.result.begin(), rhs.result.end());
    }
};

void filter_garbage(std::string &keyword) {
    RemoveGarbageAndLowerCase res(keyword);
    tbb::parallel_reduce(tbb::blocked_range<size_t>(0, keyword.size()), res);
    keyword = res.result;
}

int main() {
    std::string keyword = "ThIas_iS:saome-aTYpe_Ofa=MoDElaKEYwoRDastrang";

    filter_garbage(keyword);

    std::cout << keyword << std::endl;

    return 0;
}

もちろん、データのコピーを回避することで最終的なコードをさらに改善することもできますが、このサンプルの目的は、簡単にスレッド化できる問題であることを示すことです。

于 2012-05-03T08:13:55.680 に答える
1

ガベージ文字を無視して、文字列を 1 回通過させることで、これを高速化できます。このようなもの（疑似コード）：

std::string normalizedKeyword;
normalizedKeyword.reserve(keyword.size())
for (auto p = keyword.begin(); p != keyword.end(); ++p)
{
    char ch = *p;
    if (!isGarbage(ch))
        normalizedKeyword.append(tolower(ch));
}

// then search for normalizedKeyword in stopwords

これにより、 のオーバーヘッドが解消されますstd::remove_ifが、メモリの割り当てと、文字を にコピーするための新しいオーバーヘッドが発生しnormalizedKeywordます。

于 2012-05-01T15:38:13.757 に答える
0

ここでの問題は標準関数ではなく、それらの使い方です。明らかに 1 つだけを実行する必要があるときに、文字列に対して複数のパスを作成しています。

あなたがしなければならないことは、おそらくアルゴリズムをまっすぐに実行することはできません.ブーストまたは独自のローリングの助けが必要です.

文字列のサイズ変更が実際に必要かどうかも慎重に検討する必要があります。ええ、スペースを節約できるかもしれませんが、速度が低下します。これだけを削除すると、かなりの運用費用が発生する可能性があります。

于 2012-05-01T15:54:05.157 に答える
0

ガベージの削除と小文字化を 1 つのステップに組み合わせる方法を次に示します。UTF-8 などのマルチバイト エンコーディングでは機能しませんが、元のコードでも機能しません。0と1はどちらもゴミの値だと思います。

bool Indexer::filter(string &keyword)
{
    static char replacements[256] = {1}; // initialize with an invalid char
    if (replacements[0] == 1)
    {
        for (int i = 0;  i < 256;  ++i)
            replacements[i] = isGarbage(i) ? 0 : ::tolower(i);
    }
    string::iterator tail = keyword.begin();
    for (string::iterator it = keyword.begin();  it != keyword.end();  ++it)
    {
        unsigned int index = (unsigned int) *it & 0xff;
        if (replacements[index])
            *tail++ = replacements[index];
    }
    keyword.resize(tail - keyword.begin());

    // After filtering, if the keyword is empty or it is contained in stop words list, mark as invalid keyword
    if (keyword.size() == 0 || stopwords_.find(keyword) != stopwords_.end())
        return false;

    return true;
}

あなたのタイミングの大部分は ですので、それが物事を改善するかどうかも確認std::set::findしようと思います.std::unordered_set

于 2012-05-01T16:05:05.310 に答える
-1

私はそれをより低いレベルのC関数で実装します。おそらく（このコンパイルをチェックしないで）このようなもので、その場で置換を行い、キーワードのサイズを変更しません。

  1. ガベージ文字のセットを使用する代わりに、256文字すべての静的テーブルを追加します（もちろん、ASCIIでのみ機能します）。0は問題のないすべての文字、1はフィルターで除外する必要のある文字です。何かのようなもの：

static const char GARBAGE[256] = { 1, 1, 1, 1, 1, ...., 0, 0, 0, 0, 1, 1, ... };

次に、オフセットpos内の各文字について、const char *strチェックするだけif (GARBAGE[str[pos]] == 1)です。

これは多かれ少なかれ順序付けられていないセットが行うことですが、命令ははるかに少なくなります。stopwordsそうでない場合は、順序付けされていないセットにする必要があります。

ここでフィルタリング関数（ここではascii / utf8とnullで終了する文字列を想定しています）：

bool Indexer::filter(char *keyword)
{

    char *head = pos;
    char *tail = pos;

    while (*head != '\0') {
        //copy non garbage chars from head to tail, lowercasing them while at it
        if (!GARBAGE[*head])  {
           *tail = tolower(*head);
           ++tail; //we only advance tail if no garbag
        }
        //head always advances
        ++head;
    }
    *tail = '\0';

    // After filtering, if the keyword is empty or it is contained in stop words list, mark as invalid keyword
    if (tail == keyword || stopwords_.find(keyword) != stopwords_.end())
        return false;


    return true;
}
于 2012-05-01T15:43:22.440 に答える