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

>>> 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 2

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

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

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

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

Answer 3

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

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

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

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