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

Question

下面给出了一个用 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

Edit2:一个更快的 C++ 程序

这是 NetVipeC 的解决方案、Dieter Lücking 的解决方案和 this question 的最佳答案的组合。 .真正的性能 killer 是默认使用无缓冲读取 的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

Edit3: 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++快。

变化是:

• 消除了 vector words保存单词(word_count 中已经保存了单词)。
• 消除了集合unique_words (在 word_count 中只有独特的单词)。
• 消除了第二个拷贝到单词，不需要。

• 消除了单词的排序(在 map 中更新了顺序，现在 map 中的单词按长度排序，相同长度的单词按字典顺序排列。

  #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按照提议。