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

Question

下面给出了Python和C++中的程序,它执行以下任务:从stdin读取空格分隔的单词,打印按字符串长度排序的唯一单词以及每个唯一单词到stdout的计数.输出行的格式为:length,count,word.

例如,使用此输入文件(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解决方案,DieterLücking的解决方案的组合,也是这个问题的最佳答案.真正的性能杀手是默认cin使用无缓冲读取.解决了std::cin.sync_with_stdio(false);.此解决方案还使用单个容器,利用mapC++ 中的有序.

#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:一个简洁的Python程序版本由Daniel提供,它与上面的版本大致同时运行:

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++要快。

变化是：

• 消除了保存单词的向量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 RAM、GCC 4.9.0、32 位中进行测试，运行时间为 238ms。std::cin.sync_with_stdio(false);按照建议使用和更新了代码\n。