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

Question

下面是一个用Python和C++写的程序，它的功能是：从标准输入读取用空格分隔的单词，打印出每个独特单词的长度和出现次数，并按单词长度排序。输出的格式是：长度，次数，单词。

例如，使用这个输入文件（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++程序，使用的编译器是g++ 4.9.0，带有-O3选项。

使用的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的解决方案，以及对这个问题的最佳答案。真正影响性能的是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

Answer 1

这是另一个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这样的基于流的分词方法会成为瓶颈。

Answer 2

你的C++代码有几个问题。

首先，你在使用可变字符串。这意味着你在到处复制它们。（而Python的字符串是不可变的。）经过测试，我发现这样会让C++代码变得更慢，所以我们可以放弃这个做法。

第二，使用unordered_容器可能是个不错的主意。经过测试，我发现用它们替换后，速度提高了三分之一（使用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。

为了提高性能，不要使用那些重量级的流对象。它们做了很多非常繁琐的工作。

Answer 3

  std::vector<std::string> words;

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

这意味着在向量（vector）变大的时候，需要不断地进行分配、复制和释放操作。你可以提前分配好空间，或者使用类似列表（list）这样的结构。

Answer 4

做了三个改动，去掉了多余的向量（在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;
}

结果是：

原始版本：

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

Answer 5

试试这个，应该比原来的C++快。

改动有：

• 去掉了用来保存单词的向量 words（因为单词已经保存在word_count里了）。
• 去掉了集合 unique_words（在word_count里只有唯一的单词）。
• 去掉了第二次复制单词的操作，这个不需要了。

• 去掉了对单词的排序（现在在映射中，单词的顺序是根据长度来的，长度相同的单词按字典顺序排列）。

  #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内存、GCC 4.9.0、32位的环境下测试，运行时间为238毫秒。更新了代码，使用了 std::cin.sync_with_stdio(false); 和 \n，如建议的那样。