Pythonのリストは、Cの配列：100倍遅い？

Question

私は、Pythonのリストがベクトルとして実装されていることを理解しました。だから私は以下のコードがPythonでは（なぜ3.1.3では、そしてPython 3.2では65xしか）同等のCコードより100倍遅いのか説明できません。

単に繰り返し、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ログ未満とすることができる（nbValues）は値をソートすることは、通常遅い

I kown （例えば、内部のmax関数を使用して）これを高速化する方法はありましたが、これは高校生のための練習であり、私たちは基礎（if/else、for、while、およびlists）を教えています。 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

編集：スクラッチこれ、私ははっきりとここに意味を話していませんよ。私は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() 

私は2つのマイナーな変更を行いました。

1. 私は関数内にコードブロック全体をラップしました。関数ブロック内のコードは、グローバル辞書の変数名を検索するのではなく、変数の参照がインデックスで実行できるため、トップレベルのコードよりも高速です。改善：私のコンピュータで60％速くなりました。

2. 次に、ローカル変数の現在の最大値をキャッシュすることによって配列アクセスの数を減らしました。この速度はさらに15％増加しました。

私はarrayモジュールを使用しようとしましたが、これ以上の利益は得られませんでした。アレイオブジェクトの整数にアクセスするにはヒープ割り当てが必要なので、私は驚いていませんでした。

一般的に、Python開発者は、この種のコードを処理するためにPythonを最適化することは気にせず、正当な理由があります。私は、組み込み関数に頼らなくてもそれ以上の改善は期待できません。たとえば、次のコードは私のシステムのCバージョンの3分の1の範囲内にあり、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％のスピードアップが可能です。