Python 列表与 C 数组 : 100x slower?

Question

据我了解，Python 列表是作为 vector 实现的。这就是为什么我无法解释为什么以下代码在 Python 中比等效的 C 代码慢 100 倍(在 3.1.3 中，“仅”在 python 3.2 中慢 65 倍)。

它只是重复提取列表的最大值，nbExtract次数:

nbValues = int(input())
nbExtract = int(input())
values = [int(value) for value in input().split()]

for loop in range(nbExtract):
   idMax = 0   
   for idValue in range(nbValues):
      if values[idMax] < values[idValue]:
         idMax = idValue
   print(values[idMax], end = ' ')
   values[idMax] = values[nbValues- 1]
   nbValues= nbValues - 1

注意:nbExtract可能小于 log(nbValues)，因此对值进行排序通常会较慢

我知道如何更快地做到这一点(例如使用内部 max 函数)，但这是针对高中生的练习，我们只教他们基础知识(if/else、for、while 和列表) ，并非 Python 中提供的所有函数。

有没有办法在保持结构不变的情况下提高速度？我尝试过Python的数组，但速度大致相同。

有谁知道为什么 Python 内部的列表操作速度慢得多？

---

根据要求，等效的 C 代码:

#include <stdio.h>
int main()
{
   int nbValues, nbExtract ;
   scanf("%d%d", &nbValues, &nbExtract);
   int values[nbValues];
   for (int idValue = 0; idValue < nbValues; idValue++)
      scanf("%d", &values[idValue]);

   for (int loop = 0; loop < nbExtract; loop++)
   {
      int idMax = 0;
      for (int idValue = 0; idValue < nbValues; idValue++)
         if (values[idMax] < values[idValue])
            idMax = idValue;
      printf("%d ", values[idMax]);
      values[idMax] = values[nbValues - 1];
      nbValues--;
   }
   return 0;
}

Answer 1

通过细微的调整，您可以节省几秒钟的时间。

def main():
    nbValues = int(input())
    values = [int(x) for x in input().split()]

    for loop in range(nbValues):
        idMax = 0   
        maxv = -2**64 # Not perfect
        for idValue in range(nbValues):
            v = values[idValue]
            if v > maxv:
                idMax = idValue
                maxv = v
        print(values[idMax], end = ' ')
        values[idMax] = values[nbValues- 1]
        nbValues = nbValues - 1

main()

我做了两个小改动。

1. 我将整个代码块包装在一个函数中。功能 block 内的代码比顶层的代码更快，因为变量查找可以通过索引来完成，而不是通过在全局字典中查找变量名来完成。改进:在我的计算机上速度提高了 60%。

2. 然后，我通过将当前最大值缓存在局部变量中来减少数组访问次数。这使速度进一步提高了 15%。

我尝试使用array模块，但它没有提供进一步的 yield 。我并不感到惊讶，因为访问数组对象中的整数需要堆分配。

一般来说，Python 开发人员并不关心优化 Python 来处理此类代码，并且他们提供了很好的理由。如果不借助内置函数，我不会期望有任何进一步的改进。例如，下面的代码在我的系统上是 C 版本的 3 倍以内，并且与 Python 程序员编写它的方式相匹配。

nbValues = int(input())
values = [int(x) for x in input().split()]
values.sort(reverse=True)
print(' '.join(str(x) for x in values))

建议:减小输入大小。将数组大小减半即可免费提高 300% 的速度。