python - разница в производительности между двумя реализациями

Question

Как следующие две реализации имеют различную производительность в Python?

from cStringIO import StringIO 
from itertools import imap 
from sys import stdin 
input = imap(int, StringIO(stdin.read())) 
print '\n'.join(imap(str, sorted(input))) 

И

import sys 
for line in sys.stdin: 
    l.append(int(line.strip('\n'))) 

l.sort() 
for x in l: 
    print x 

Первая реализация происходит быстрее, чем второй входы для порядка 10^6 линий. Почему так?

Answer 1

две основные причины:

• 2-й код явно конструирует список и сортирует его потом, в то время как первая версия позволяет sorted создавать только внутренний список во время сортировки одновременно.
• 2-й код явно перебирает список по for (на Python VM), а 1-я версия неявно петли с imap (над структурой подкладки на C).

В любом случае, почему StringIO там? Самый простой и, вероятно, самый быстрый способ:

from sys import stdin, stdout 
stdout.writelines(sorted(stdin, key=int)) 

Answer 2

>>> dis.dis(first) 
    2   0 LOAD_GLOBAL    0 (imap) 
       3 LOAD_GLOBAL    1 (int) 
       6 LOAD_GLOBAL    2 (StringIO) 
       9 LOAD_GLOBAL    3 (stdin) 
      12 LOAD_ATTR    4 (read) 
      15 CALL_FUNCTION   0 
      18 CALL_FUNCTION   1 
      21 CALL_FUNCTION   2 
      24 STORE_FAST    0 (input) 
      27 LOAD_CONST    0 (None) 
      30 RETURN_VALUE   
>>> dis.dis(second) 
    2   0 SETUP_LOOP    48 (to 51) 
       3 LOAD_GLOBAL    0 (sys) 
       6 LOAD_ATTR    1 (stdin) 
       9 CALL_FUNCTION   0 
      12 GET_ITER    
     >> 13 FOR_ITER    34 (to 50) 
      16 STORE_FAST    0 (line) 

    3   19 LOAD_GLOBAL    2 (l) 
      22 LOAD_ATTR    3 (append) 
      25 LOAD_GLOBAL    4 (int) 
      28 LOAD_FAST    0 (line) 
      31 LOAD_ATTR    5 (strip) 
      34 LOAD_CONST    1 ('\n') 
      37 CALL_FUNCTION   1 
      40 CALL_FUNCTION   1 
      43 CALL_FUNCTION   1 
      46 POP_TOP    
      47 JUMP_ABSOLUTE   13 
     >> 50 POP_BLOCK   

    4  >> 51 LOAD_GLOBAL    2 (l) 
      54 LOAD_ATTR    6 (sort) 
      57 CALL_FUNCTION   0 
      60 POP_TOP    
      61 LOAD_CONST    0 (None) 
      64 RETURN_VALUE   

first - это ваша первая функция. second - ваша вторая функция.

dis рассказывает одну из причин, по которой первая быстрее.

Answer 3

Выполните преобразование шаг за шагом от второго к первому и увидеть, как меняется производительность с каждым шагом.

1. Удалить строку. Это приведет к некоторому ускорению, независимо от того, будет ли оно значительным, другое дело. Вычистка излишняя, как было упомянуто вами и THC4k.
2. Затем замените цикл for, используя l.append с картой (int, sys.stdin). Я предполагаю, что это даст значительное ускорение.
3. Заменить map и l.sort с imap и sorted. Я предполагаю, что это не повлияет на производительность, может быть небольшое замедление, но это будет далеко не значительным. Между ними я обычно бывал с первым, но с Python 3 на горизонте последний, вероятно, предпочтительнее.
4. Заменить петлю цикла, используя print с print '\n'.join(...). Я предполагаю, что это будет еще одно ускорение, но это будет стоить вам некоторой памяти.
5. Добавьте cStringIO (что совершенно необязательно, кстати), чтобы увидеть, как это влияет на производительность. Я предполагаю, что он будет немного медленнее, но недостаточно, чтобы счетчик 4 и 2.

Затем, если вы попробуете ответ THC4k, это, вероятно, будет быстрее, чем все вышеперечисленное, будучи проще и проще читать и использовать меньше памяти, чем 4 и 5. Он имеет несколько другое поведение (он не разделяет ведущие нули от чисел).

Конечно, попробуйте сами, вместо того, чтобы доверять кому-либо догадываться. Также запустите cProfile на свой код и посмотрите, какие части теряют больше всего времени.