title: Python lists vs C arrays : 100x slower?
body: <p>It was my understanding that Python lists were implemented as vectors. That's why I can't explain why the following code is 100x slower in Python (in 3.1.3, and "only" 65x in python 3.2) than the equivalent C code.</p>
  
  <p>It simply repeatedly extracts the maximum of a list, <code>nbExtract</code> times : </p>
  
  <pre><code>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] &lt; values[idValue]:
           idMax = idValue
     print(values[idMax], end = ' ')
     values[idMax] = values[nbValues- 1]
     nbValues= nbValues - 1
  </code></pre>
  
  <p><strong>Note</strong> : <code>nbExtract</code> can be less than log(nbValues) so sorting the values is normally slower</p>
  
  <p>I kown how to do it faster (using the internal <code>max</code> function for example) but this was an exercise for high-school students and we are only teaching them the basics (if/else, for, while and lists), not all the functions available in Python.</p>
  
  <p>Is there a way to improve the speed while keeping the same structure? I've tried Python's arrays but the speed is roughly the same.</p>
  
  <p>Does anyone know why internally Python is so much slower for lists manipulation ?</p>
  
  <p><hr/>
  As requested, equivalent C code : </p>
  
  <pre><code>#include &lt;stdio.h&gt;
  int main()
  {
     int nbValues, nbExtract ;
     scanf("%d%d", &amp;nbValues, &amp;nbExtract);
     int values[nbValues];
     for (int idValue = 0; idValue &lt; nbValues; idValue++)
        scanf("%d", &amp;values[idValue]);
  
     for (int loop = 0; loop &lt; nbExtract; loop++)
     {
        int idMax = 0;
        for (int idValue = 0; idValue &lt; nbValues; idValue++)
           if (values[idMax] &lt; values[idValue])
              idMax = idValue;
        printf("%d ", values[idMax]);
        values[idMax] = values[nbValues - 1];
        nbValues--;
     }
     return 0;
  }
  </code></pre>