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

下面给出了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 ++程序，使用的编译器是带有-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); 。 该解决方案还使用单个容器，利用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

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

变化是：

#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);更新了代码std::cin.sync_with_stdio(false); 和n建议。

做三个改变，省略额外的向量（你没有在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); 看俄勒冈州线索的问题）：

real    0m0.107s
user    0m0.100s
sys 0m0.004s

和NetV​​ipeC的解决方案与std::cin.sync_with_stdio(false); 并用' n'代替std :: endl：

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

蟒蛇：

real    0m0.146s
user    0m0.136s
sys 0m0.008s

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

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

这需要随着矢量的增长不断重复分配/复制/释放操作。 要么预先分配矢量，要么使用类似列表的东西。

上一篇: Why is Python faster than C++ in this case?

下一篇: Regex library not working correctly in c++