2

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.

It simply repeatedly extracts the maximum of a list, nbExtract times : 

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

Note : nbExtract can be less than log(nbValues) so sorting the values is normally slower

I kown how to do it faster (using the internal max 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.

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.

Does anyone know why internally Python is so much slower for lists manipulation ?

As requested, equivalent C code : 
#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;
}
Loïc Février
  • 7,540
  • 8
  • 39
  • 51
  • 6
    Could you post the equivalent C code? – David Robinson Apr 03 '12 at 17:32
  • 1
    Does Python check all array accesses for out-of-bounds condition? – pmg Apr 03 '12 at 17:33
  • 1
    Do you mean the `array` module with _Python arrays_? – rubik Apr 03 '12 at 17:37
  • 1
    Using ``map`` isn't very pythonic, especially in this case. ``[int(value) for value in input().split()]`` would be more readable (although I'd move the input outside of the list comprehension for readability and clarity). – Gareth Latty Apr 03 '12 at 17:39
  • 3
    Also, does it matter it's 100x slower? – Gareth Latty Apr 03 '12 at 17:40
  • 3
    IMHO, Python just exposes the slowness of the algorithm better than C – Kien Truong Apr 03 '12 at 17:49
  • 2
    Im confused .. you're teaching Python but you don't know how it works? – Jochen Ritzel Apr 03 '12 at 17:54
  • @Jochen Ritzel : do I need to know the internal of Python to teach basic programming ? I was just surprised by the difference of speed – Loïc Février Apr 03 '12 at 17:56
  • @Lattyware : yes because we are using test files and while each individual test is runned in 0.15 in C, it takes 15s in Python, which is blocking our evaluation server for too long – Loïc Février Apr 03 '12 at 17:58
  • @Lattyware: Saying that using `map()` isn't Pythonic is meaningless. There's a reason they decided to keep in Python 3.x. I prefer `map()` over list comprehensions in some situations, and this might be one of them. – Sven Marnach Apr 03 '12 at 21:53
  • @SvenMarnach I'm not saying it doesn't have it's uses, but in this case I thought it was less clear than a list comp. – Gareth Latty Apr 04 '12 at 11:09
  • @Lattyware: Fair enough. I've become a bit touchy about the comment "Using `map()` isn't very Pythonic", which is definitely overused on SO. – Sven Marnach Apr 04 '12 at 11:17
  • @SvenMarnach True, that was my poor wording, reading it now, I agree it sounds over-zealous. – Gareth Latty Apr 04 '12 at 11:53
  • the reason it is slower in python is that the entire loop is interpreted. the main cost is not accessing the list, but running the python (bytecode) interpreter to execute all the steps in the loop. this is why the `max` command will be so much faster - because it delegates to c code. python is not slow because of the data structures, but because it's an interpreted language. cannot post this as an answer because for some reason the question has been closed. – andrew cooke May 06 '12 at 04:20

2 Answers2

2

You can shave a few seconds off with minor tweaks.

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()

I've made two minor changes.

  1. I wrapped the entire block of code in a function. Code inside a function block is faster than code at the top-level because variable lookup can be done by index rather than by looking up the variable name in the global dictionary. Improvement: 60% faster on my computer.

  2. I then reduced the number of array accesses by caching the current maximum value in a local variable. This increased speed by a further 15%.

I tried using the array module, but it provided no further gains. I was not surprised, since accessing integers in an array object requires heap allocation.

In general, the Python developers do not care about optimizing Python to handle this kind of code, and they have provided good justifications. I would not expect any further improvements without resorting to built-in functions. For example, the following code is within a factor of 3 of the C version on my system, and matches how a Python programmer would write it.

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

Suggestion: Reduce the input size. Cutting the array size in half gives you a 300% increase in speed, for free.

Dietrich Epp
  • 205,541
  • 37
  • 345
  • 415
  • Thanks for the advice. How would you do it if one only need to top X values ? (But your solution, even in this case, is in general faster that using two "for", the gain of using internal functions in enormous). I think we will reduce the test size and teach better Python for advanced students. – Loïc Février Apr 03 '12 at 18:37
  • In Python, if I only needed the top X values, then I would probably sort the entire list anyway. The large gains in programmer effort and code complexity would not be worth the minimal gains in execution speed. (Maybe that's the lesson?) – Dietrich Epp Apr 03 '12 at 18:42
0

Edit: Scratch this, I'm clearly not talking sense here. I was under the impression that Python's lists were pretty much linked lists, but that's not the case.

Python's list type isn't exactly an array, at least not in the sense that you're thinking of arrays/vectors. The list type is more like a linked list data structure (easy to insert, append, remove elements, etc.), though that's not a completely accurate description either. For a fair comparison against C arrays, I would suggest using the array type from Numpy.

See here for more information: Python List vs. Array - when to use?

Community
  • 1
  • 1
Brendan Wood
  • 6,220
  • 3
  • 30
  • 28