Python 比 c++ 慢大约 40 倍

Question

我正在实现一个滚动的中值解决方案，不确定为什么我的 python 实现比 c++ 实现慢 40 倍左右。

以下是完整的实现

C++

#include <iostream>
#include <vector>
#include <string.h>
using namespace std;
int tree[17][65536];
void insert(int x) { for (int i=0; i<17; i++) { tree[i][x]++; x/=2; } }
void erase(int x) { for (int i=0; i<17; i++) { tree[i][x]--; x/=2; } }
int kThElement(int k) {
    int a=0, b=16;
    while (b--) { a*=2; if (tree[b][a]<k) k-=tree[b][a++]; }
    return a;
}
long long sumOfMedians(int seed, int mul, int add, int N, int K) {
    long long result = 0;
    memset(tree, 0, sizeof(tree));
    vector<long long> temperatures;
    temperatures.push_back( seed );
    for (int i=1; i<N; i++)
      temperatures.push_back( ( temperatures.back()*mul+add ) % 65536 );
    for (int i=0; i<N; i++) {
      insert(temperatures[i]);
      if (i>=K) erase(temperatures[i-K]);
      if (i>=K-1) result += kThElement( (K+1)/2 );
    }
    return result;
}
// default input
// 47 5621 1 125000 1700
// output
// 4040137193
int main()
{   
  int seed,mul,add,N,K;
  cin >> seed >> mul >> add >> N >> K;
  cout << sumOfMedians(seed,mul,add,N,K)  << endl;
  return 0;
}

蟒

def insert(tree,levels,n):
        for i in xrange(levels):
                tree[i][n] += 1
                n /= 2
def delete(tree,levels,n):
        for i in xrange(levels):
                tree[i][n] -= 1
                n /= 2
def kthElem(tree,levels,k):
        a = 0
        for b in reversed(xrange(levels)):
                a *= 2
                if tree[b][a] < k:
                        k -= tree[b][a]
                        a += 1
        return a
def main():
        seed,mul,add,N,K = map(int,raw_input().split())
        levels = 17
        tree = [[0] * 65536 for _ in xrange(levels)]
        temps = [0] * N
        temps[0] = seed
        for i in xrange(1,N):
                temps[i] = (temps[i-1]*mul + add) % 65536
        result = 0
        for i in xrange(N):
                insert(tree,levels,temps[i])
                if (i >= K):
                        delete(tree,levels,temps[i-K])              
                if (i >= K-1):
                        result += kthElem(tree,levels,((K+1)/2))
        print result
# default input
# 47 5621 1 125000 1700
# output
# 4040137193
main()

在

上面提到的输入（在代码的注释中）C++代码花了大约0.06 seconds，而python花了大约2.3 seconds。

有人可以建议我的 python 代码可能存在的问题以及如何改进到低于 10 倍的性能影响吗？

我不希望它接近 c++ 实现，而是达到 5-10 倍的数量级。我知道我可以通过使用 numpy（和/或 scipy）等库来优化它。我从使用python解决编程挑战的角度提出这个问题。在这些挑战中，通常不允许使用这些库。我只是问是否有可能在 python 中击败此算法的时间限制。

如果有人感兴趣C++代码是从浮动中位数问题中借用的 http://community.topcoder.com/tc?module=Static&d1=match_editorials&d2=srm310

[编辑]

对于那些认为使用 numpy 数组会提高性能的人来说，事实并非如此。另一方面，仅使用 numpy ndarray 而不是列表列表，性能进一步下降到大约 14 秒，这比 c++ 慢了 200 多倍。

Answer 1

正如你所发现的，计算受限和程序编写的纯 Python 代码可能会很慢。 如果你想在Python中制作一些可以快速运行此类任务的东西，你需要使用一些C（或C++，Fortran或其他）扩展，这些扩展非常丰富。 例如，统计和数学人员使用NumPy和SciPy以及相关工具，这些工具很容易从Python中使用，但实际上是用编译语言实现的，并且具有高性能（如果使用得当）。

如果你想尝试从纯Python中榨取更多的性能，你可以尝试使用"cProfile"模块来分析你的代码。 但它的速度可能不会接近C++，除非你使用像NumPy这样的更智能的模块或编写自己的扩展。

通过重构以下内容，您可能会获得少量收益：

reversed(xrange(levels))

特别是如果您使用的是Python 2.x，因为这将创建一个实际的列表。 您可以改为执行以下操作：

xrange(levels - 1, -1, -1)

Answer 2

有人可以建议[...]如何提高到性能命中率低于10倍吗？

1. 分析代码。
2. 考虑使用NumPy而不是本机列表。
3. 如果事实证明这还不够，请考虑使用Cython作为关键部分。