Python列表vs C数组：慢100倍？

Question

我的理解是Python列表是作为向量实现的。这就是为什么我不能解释为什么下面的代码在Python中比等效的C代码慢100倍（在3.1.3中，在python3.2中“只有”65x）。在

它只是重复提取列表的最大值，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和list），而不是Python中所有可用的函数。在

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

有人知道为什么Python在内部对列表操作慢得多吗？在

---

根据要求，等效C代码： ^{pr2}$

Answer 1

编辑：划掉这个，我在这里说的显然没有道理。我的印象是Python的列表几乎都是链接列表，但事实并非如此。

Python的list类型并不完全是一个数组，至少在您所考虑的数组/向量的意义上是不完全的。list类型更像是一个链表数据结构（易于插入、追加、删除元素等），尽管这也不是一个完全准确的描述。为了与C数组进行比较，我建议使用Numpy中的array类型。在

有关详细信息，请参阅此处：Python List vs. Array - when to use?

Answer 2

你可以通过一些小的调整来减少几秒钟的时间。在

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. 我把整个代码块包装在一个函数中。函数块内的代码比顶层的代码快，因为变量查找可以通过索引而不是在全局字典中查找变量名来完成。改进：我的电脑速度提高了60%。

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

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

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

^{pr2}$

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