logo标签列表

为什么在这种情况下Python比C++更快？

pythonc++performanceio
6
以下是使用Python和C++编写的程序，执行以下任务：从stdin读取以空格为分隔符的单词，并按字符串长度排序打印唯一单词以及每个唯一单词的计数到stdout。输出行的格式为：长度，计数，单词。
例如，使用这个输入文件（一个同义词词典的488kb） http://pastebin.com/raw.php?i=NeUBQ22T 带有格式的输出如下：
1 57 "
1 1 n
1 1 )
1 3 *
1 18 ,
1 7 -
1 1 R
1 13 .
1 2 1
1 1 S
1 5 2
1 1 3
1 2 4
1 2 &
1 91 %
1 1 5
1 1 6
1 1 7
1 1 8
1 2 9
1 16 ;
1 2 =
1 5 A
1 1 C
1 5 e
1 3 E
1 1 G
1 11 I
1 1 L
1 4 N
1 681 a
1 2 y
1 1 P
2 1 67
2 1 y;
2 1 P-
2 85 no
2 9 ne
2 779 of
2 1 n;
...

这里是C++程序

#include <vector>
#include <string>
#include <iostream>
#include <set>
#include <map>

bool compare_strlen (const std::string &lhs, const std::string &rhs) {
  return (lhs.length() < rhs.length());
}

int main (int argc, char *argv[]) {
  std::string str;
  std::vector<std::string> words;

  /* Extract words from the input file, splitting on whitespace */
  while (std::cin >> str) {
    words.push_back(str);
  }

  /* Extract unique words and count the number of occurances of each word */
  std::set<std::string> unique_words;
  std::map<std::string,int> word_count; 
  for (std::vector<std::string>::iterator it = words.begin();
       it != words.end(); ++it) {
    unique_words.insert(*it);
    word_count[*it]++;
  }

  words.clear();
  std::copy(unique_words.begin(), unique_words.end(),
            std::back_inserter(words));

  // Sort by word length 
  std::sort(words.begin(), words.end(), compare_strlen);

  // Print words with length and number of occurances
  for (std::vector<std::string>::iterator it = words.begin();
       it != words.end(); ++it) {
    std::cout << it->length() << " " << word_count[*it]  << " " <<
              *it << std::endl;
  }

  return 0;
}

这是Python程序：

import fileinput
from collections import defaultdict

words = set()
count = {}
for line in fileinput.input():
  line_words = line.split()
  for word in line_words:
    if word not in words:
      words.add(word)
      count[word] = 1
    else:
      count[word] += 1 

words = list(words)
words.sort(key=len)

for word in words:
  print len(word), count[word], word

对于C++程序，使用的编译器是带有-O3标志的g++ 4.9.0。

使用的Python版本为2.7.3

C++程序所用时间：

time ./main > measure-and-count.txt < ~/Documents/thesaurus/thesaurus.txt

real    0m0.687s
user    0m0.559s
sys     0m0.123s

Python程序所需的时间：
time python main.py > measure-and-count.txt < ~/Documents/thesaurus/thesaurus.txt

real    0m0.369s
user    0m0.308s
sys     0m0.029s

Python程序比C++程序快得多，而且在输入尺寸较大时甚至更快。这是怎么回事？我的C++ STL使用有误吗？
编辑： 根据评论和答案的建议，我将C++程序改为使用std :: unordered_set和std :: unordered_map。
以下行已更改。
#include <unordered_set>
#include <unordered_map>

...

std::unordered_set<std::string> unique_words;
std::unordered_map<std::string,int> word_count;

编译命令：
g++-4.9 -std=c++11 -O3 -o main main.cpp

这只稍微提高了性能：

time ./main > measure-and-count.txt < ~/Documents/thesaurus/thesaurus.txt

real    0m0.604s
user    0m0.479s
sys     0m0.122s

编辑2： C++中的一个更快的程序

这是NetVipeC的解决方案、Dieter Lücking的解决方案和this question的最佳答案的结合。真正的性能杀手是cin默认使用非缓冲读取。可以通过std::cin.sync_with_stdio(false);解决。此解决方案还使用了单个容器，利用了C++中有序的map。

#include <vector>
#include <string>
#include <iostream>
#include <set>
#include <map>

struct comparer_strlen {
    bool operator()(const std::string& lhs, const std::string& rhs) const {
        if (lhs.length() == rhs.length())
            return lhs < rhs;
        return lhs.length() < rhs.length();
    }
};

int main(int argc, char* argv[]) {
    std::cin.sync_with_stdio(false);

    std::string str;

    typedef std::map<std::string, int, comparer_strlen> word_count_t;

    /* Extract words from the input file, splitting on whitespace */
    /* Extract unique words and count the number of occurances of each word */
    word_count_t word_count;
    while (std::cin >> str) {
        word_count[str]++;
    }

    // Print words with length and number of occurances
    for (word_count_t::iterator it = word_count.begin();
         it != word_count.end(); ++it) {
        std::cout << it->first.length() << " " << it->second << " "
                  << it->first << '\n';
    }

    return 0;
}

运行时

time ./main3 > measure-and-count.txt < ~/Documents/thesaurus/thesaurus.txt

real    0m0.106s
user    0m0.091s
sys     0m0.012s

编辑3：Daniel提供了一个简洁明了的Python程序版本，它运行时间与上面的版本大致相同：

import fileinput
from collections import Counter

count = Counter(w for line in fileinput.input() for w in line.split())

for word in sorted(count, key=len):
  print len(word), count[word], word

运行时：

time python main2.py > measure-and-count.txt.py < ~/Documents/thesaurus/thesaurus.txt

real    0m0.342s
user    0m0.312s
sys     0m0.027s
1
std::map 和 std::unordered_map 有什么区别？ - clcto
1
我不太有信心去使用dupe-hammer，但这里可能是重复的链接：https://dev59.com/_mox5IYBdhLWcg3wLhei - Mysticial
2
顺便说一句，Python 之所以被使用是因为它简短而不是快速的：count = Counter(l for line in fileinput.input() for l in line.split()) for word in sorted(count, key=len): print len(word), count[word], word - Daniel
1
尝试降低优化设置。在某些情况下，使用-O3可能会降低性能。尝试不同的优化设置。还可以尝试将比较函数标记为“内联”。 - Some programmer dude
现在你已经解决了最大的瓶颈，尝试使用unordered吧。它可能会节省另外一大块时间... - Yakk - Adam Nevraumont
显示剩余4条评论
6个回答
4

请用此测试，它必须比原来的C++更快。

改动如下：

  • Eliminated the vector words to save the words (there will be saved already in word_count).
  • Eliminated the set unique_words (in word_count are only the unique words).
  • Eliminated the second copy to words, not needed.

  • Eliminated the sort of the words (the order was updated in the map, now the words in the map are order by length and the words with same length are lexicographically order.

    #include <vector>
#include <string>
#include <iostream>
#include <set>
#include <map>

struct comparer_strlen_functor {
    operator()(const std::string& lhs, const std::string& rhs) const {
        if (lhs.length() == rhs.length())
            return lhs < rhs;
        return lhs.length() < rhs.length();
    }
};

int main(int argc, char* argv[]) {
    std::cin.sync_with_stdio(false);

    std::string str;

    typedef std::map<std::string, int, comparer_strlen_functor> word_count_t;

    /* Extract words from the input file, splitting on whitespace */
    /* Extract unique words and count the number of occurances of each word */
    word_count_t word_count;
    while (std::cin >> str) {
        word_count[str]++;
    }

    // Print words with length and number of occurances
    for (word_count_t::iterator it = word_count.begin(); it != word_count.end();
         ++it) {
        std::cout << it->first.length() << " " << it->second << " " << it->first
                  << "\n";
    }

    return 0;
}

新版本的读取循环，逐行读取并分割。需要#include <boost/algorithm/string/split.hpp>

while (std::getline(std::cin, str)) {
    for (string_split_iterator It = boost::make_split_iterator(
             str, boost::first_finder(" ", boost::is_iequal()));
         It != string_split_iterator(); ++It) {
        if (It->end() - It->begin() != 0)
            word_count[boost::copy_range<std::string>(*It)]++;
    }
}

在 Core i5，8GB RAM，GCC 4.9.0，32位环境下测试，耗时238毫秒。根据建议使用 std::cin.sync_with_stdio(false); 和 \n 更新了代码。

g++-4.9 -std=c++11 -O3 -o main2 main2.cpp - OregonTrail
你同时执行了这两个程序吗？ - NetVipeC
是的，衡量性能的正确方法应该是多次运行的平均值。在这种情况下，在粘贴代表结果之前，我会运行测试大约10次，以获得+-5ms的性能。 - OregonTrail
如下所述，std::endl 不是“行结束”，而是“行结束并刷新缓冲区”。如果您不需要刷新，请使用 "\n"。 - Yakk - Adam Nevraumont
1
我喜欢这个答案，因为它利用了STL中默认map的排序属性。然而，最终答案中大部分的加速来自于使用std::cin.sync_with_stdio(false);和'\n'代替std::endl。 - OregonTrail
显示剩余2条评论
2
做出三个改变，省略额外的向量（在Python中没有），为单词向量保留内存，并避免在输出中使用endl（！）。
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <set>
#include <map>

bool compare_strlen (const std::string &lhs, const std::string &rhs) {
  return (lhs.length() < rhs.length());
}

int main (int argc, char *argv[]) {
    /* Extract words from the input file, splitting on whitespace */
    /* Also count the number of occurances of each word */
    std::map<std::string, int> word_count;
    {
        std::string str;
        while (std::cin >> str) {
            ++word_count[str];
        }
    }

    std::vector<std::string> words;
    words.reserve(word_count.size());
    for(std::map<std::string, int>::const_iterator w = word_count.begin();
        w != word_count.end();
        ++w)
    {
        words.push_back(w->first);
    }

    // Sort by word length
    std::sort(words.begin(), words.end(), compare_strlen);

    // Print words with length and number of occurances
    for (std::vector<std::string>::iterator it = words.begin();
       it != words.end();
       ++it)
    {
        std::cout << it->length() << " " << word_count[*it]  << " " <<
                  *it << '\n';
    }
    return 0;
}

Gives:

Original:

real    0m0.230s
user    0m0.224s
sys 0m0.004s

改进：

real    0m0.140s
user    0m0.132s
sys 0m0.004s

更好的办法是添加 std::cin.sync_with_stdio(false); （参见 OregonTrail 的问题）：
real    0m0.107s
user    0m0.100s
sys 0m0.004s

NetVipeC的解决方案是使用std::cin.sync_with_stdio(false);并将std::endl替换为'\n'：

real    0m0.077s
user    0m0.072s
sys 0m0.004s

Python：

real    0m0.146s
user    0m0.136s
sys 0m0.008s
你的版本在我的机器上仍比Python慢约30％，但迄今为止是最快的解决方案。 - OregonTrail
哇，从NetVipeC的解决方案中删除std::endl使得他的程序在我的机器上只比Python程序慢了约8%。 - OregonTrail
@OregonTrail - 在我的电脑上速度相同（g++ -O3 main.cc -o Test）。 - user2249683
1
  std::vector<std::string> words;

  /* Extract words from the input file, splitting on whitespace */
  while (std::cin >> str) {
    words.push_back(str);
  }

需要不断重复分配/复制/释放操作才能使向量增长。要么预分配向量，要么使用类似列表的东西。
Python程序没有进行任何预分配。此外，预分配需要计算文件中的单词数。 - OregonTrail
@OregonTrail 如果你理解我的意思，那么你的回答就是一个无关紧要的话题。(而且这并不需要数它们。只需预先分配，比如一百万个条目，就可以了。另外，你怎么知道Python程序是否预先分配呢？) - David Schwartz
你试过它吗？我没有看到明显的区别。我猜这是受IO控制的。 - juanchopanza
Python程序动态增长set()，Python必须realloc()这个数据结构（至少是哈希表，除非它有一个异常大的默认大小用于set()）。此外，在C++程序中永远不要让向量自我复制，需要提前计算输入文件中的单词数量，然后倒回文件。 - OregonTrail
@DavidSchwartz 我认为你很接近答案了。我相信Python必须使用某种形式的缓冲读取输入文件。cin不会在内存中缓冲文件，因此每次读取都需要IO。相反，应该读取整个文件（或分批读取），并在内存中执行解析。 - Climax
0
这是另一种C++版本，我认为它更接近Python逐行的方式。它试图保留在Python版本中找到的相同类型的容器和操作，带有明显的特定于C++的调整。请注意，我从其他答案中借用了`sync_with_stdio`优化。
#include <iostream>
#include <unordered_set>
#include <unordered_map>
#include <list>

#include <sstream>
#include <iterator>


bool compare_strlen(const std::string &lhs, const std::string &rhs)
{
    return lhs.length() < rhs.length();
}

int main (int argc, char *argv[]) {
    std::unordered_set<std::string> words;
    std::unordered_map<std::string, std::size_t> count;

    // Make std::cin use its own buffer to improve I/O performance.
    std::cin.sync_with_stdio(false);

    // Extract words from the input file line-by-line, splitting on
    // whitespace
    char line[128] = {};  // Yes, std::vector or std::array would work, too.
    while (std::cin.getline(line, sizeof(line) / sizeof(line[0]))) {
        // Tokenize
        std::istringstream line_stream(line);
        std::istream_iterator<std::string> const end;
        for(std::istream_iterator<std::string> i(line_stream);
            i != end;
            ++i) {
            words.insert(*i);
            count[*i]++;
        }
    }

    std::list<std::string> words_list(words.begin(), words.end());
    words_list.sort(compare_strlen);

    // Print words with length and number of occurences
    for (auto const & word : words_list)
        std::cout << word.length()
                  << ' ' << count[word]
                  << ' ' << word
                  << '\n';

    return 0;
}

这个结果与您的原始Python代码和@NetVipeC的C++代码相当。

C++

real    0m0.979s
user    0m0.080s
sys     0m0.016s

Python

real    0m0.993s
user    0m0.112s
sys     0m0.060s

我有点惊讶这个版本的C++与其他简化的C++答案相比表现得很好，因为我本以为像基于stringstream的标记化处理会成为瓶颈。

0
你的 C++ 代码存在几个问题。
首先，你正在使用可变字符串。这意味着你在大量复制它们。(Python 字符串是不可变的)。测试发现，实际上会使得 C++ 代码变慢，因此我们可以放弃这个。
其次，无序容器可能是一个不错的选择。测试表明，通过交换它们 (使用 boost::hash 算法进行哈希)，我获得了三分之一的速度提升。
第三，你使用的 std::endl 在每行刷新 std::cout 。这似乎有些愚蠢。
第四，使用 std::cin.sync_with_stdio(false); 来减少 std::cin 的开销，或者干脆不使用它们。
第五，直接从输入输出构造 set 和 map ，不要不必要地通过 std::vector 来回传输。

这里有一个测试程序（硬编码数据约为原始数据的四分之一），使用不可变字符串（std::shared_ptr<const std::string>）和手动哈希设置的unordered_容器，以及一些C++11特性使代码更简短。

去掉大型R"(字符串文字，并将stringstream替换为std::cin。

为了获得更好的性能，请勿使用重量级流对象。它们会做很多非常谨慎的工作。

针对你最后的观点，使用std::cin.sync_with_stdio(false);让我的程序速度提升了4倍。最新版本在原帖底部。 - OregonTrail
@OregonTrail 已更新。速度比之前快了5倍（从0.05秒降至0.01秒）。新增代码可轻松切换智能指针字符串和按值传递字符串，以及无序容器和有序容器。 - Yakk - Adam Nevraumont
-1

无论是std::set还是std::map，它们都优化了查找而不是插入。每次更改内容时，它们必须进行排序/平衡树。您可以尝试使用基于哈希的std::unordered_set和std::unordered_map，对于您的用例而言速度会更快。

1
使用unordered容器后的结果已添加，但性能提升仅微不足道。 - OregonTrail
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接