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 进行分析后，它的包容性成本filter高得离谱：33.4%。该过滤器的三个标准函数大部分时间都用于该百分比：std::remove_if占用 6.53%、std::set::find15.07% 和std::transform7.71%。

因此，如果我可以做（或改变）任何事情来减少这个过滤器的指令时间成本（比如使用并行化或类似的东西），请给我你的建议。提前致谢。

更新：感谢您的所有建议。简而言之，我总结了我需要做的事情是：1）通过构建我自己的循环来合并tolower并合二为一。remove_if2）使用unordered_set代替set更快的find方法。因此，我选择Mark_B了 's 作为正确答案。

4

7 回答 7

2

首先，您确定编译时启用了优化和内联吗？

假设是这种情况，我会首先尝试编写自己的转换器，将删除垃圾和小写合并到一个步骤中，以防止第二次迭代关键字。

unordered_set如果不使用其他容器（例如评论中建议的），您对查找无能为力。

您的应用程序是否有可能真的只是在操作中真正占用 CPU 密集型部分？

于 2012-05-01T15:29:21.840 回答
2

如果您使用增强过滤器迭代器，则可以将remove_ifand合并transform为一个，例如（未经测试）：

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和谓词即可完成所有操作。您可以为停用词列表构建一个分层数据结构（基本上是一棵树），从而使“就地”匹配成为可能，例如，如果您的停用词是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));
}

您可以对此进行一些优化（紧凑的长单字符串运行）并使其更通用，但它显示了如何在一次通过中就地完成所有操作，这是加速您展示的功能的最有可能的候选者。

（当然是基准变化）

于 2012-05-01T15:40:29.977 回答
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 回答
1

如果对 isGarbage() 的调用不需要同步，那么并行化应该是首先考虑的优化（当然，过滤一个关键字是一项足够大的任务，否则并行化应该更高一级）。这是如何完成的 - 一次通过原始数据，使用线程构建块进行多线程：

    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 回答
0

这里的问题不是标准功能，而是您对它们的使用。当您显然只需要做一个时，您正在对您的字符串进行多次传递。

您需要做的事情可能无法直接使用算法完成，您需要提升或滚动自己的帮助。

您还应该仔细考虑是否真的需要调整字符串的大小。是的，您可能会节省一些空间，但这会降低您的速度。单独删除它可能会占您运营费用的很大一部分。

于 2012-05-01T15:54:05.157 回答
0

这是一种将垃圾清除和小写合并到一个步骤中的方法。它不适用于 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 和以空字符结尾的字符串）：

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 回答