Страницы

Поиск по вопросам

суббота, 7 декабря 2019 г.

Почему один способ проверки чисел в списке медленнее второго?

#python #python_3x #производительность #python_internals 


import time

lst = [-3, 3, 7, 0, -10, 23, -9, -8, -5, -10, 9, 3,
 -2, 8, -3, 6, -1, 0, 10, -1, -6, -6, 10, -7, 3, 8,
 0, 7, 1, 5, -3, -6, 4, 6, -6, -4, -3, 10, 10, -5,
 -7, 0, -4, -8, 2, 9, 0, -10, -3, 3, -4, 9, -7, -8,
 0, -1, 1, 7, 2, -1, 3, 0, 9, -9, 4, 7, 6, 10, 8,
 -6, 3, 1, 1, 9, -8, -8, 2, 4, 10, 1, 5, -1, -1, 5,
 -9, 9, -3, 3, 0, -6, 2, 5, 10, 10, 5, -6, -10,  -2, -9, 'СТРОКА']


start1 = time.clock()
a =  all(isinstance(item, (int, float, complex)) for item in lst)
finish1 = time.clock()
print("Результат: {}, время:{:.2}ms".format(a, (finish1 - start1) * 1000))

start2 = time.clock()
def is_numbers(iterable):
    for item in iterable:
        if not isinstance(item, (int, float, complex)):
            return False
    return True
b = is_numbers(lst)
finish2 = time.clock()
print("Результат: {}, время:{:.2}ms".format(b, (finish2 - start2) * 1000))

Результат:

>>> 
====== RESTART: /home/dzmitry/adasdsadasdasdsad.py ======
Результат: False, время:0.081ms
Результат: False, время:0.042ms
>>> 
====== RESTART: /home/dzmitry/adasdsadasdasdsad.py ======
Результат: False, время:0.085ms
Результат: False, время:0.043ms
>>> 

Функция all() эквивалентна:


def all(iterable):
    for element in iterable:
        if not element:
            return False
    return True


Получается, что первый и второй способ равнозначны, за исключением использования
генераторного выражения. Почему первый способ медленнее в 1.5-2 раза?


Ответы

Ответ 1


Дело не в проверке типов—разница во времени сохраняется даже если заменить isinstance(item,
..) вызов на f(item), где f функция ничего не делает, а просто возвращает True значение:
f = lambda item: True (чтобы all() весь lst список просматривала без раннего выхода).
Более того, разница остаётся, если вообще вызов функции убрать:

In [1]: %timeit all(True for _ in range(1000))
10000 loops, best of 3: 69.7 µs per loop

In [2]: def loop():
   ...:     for _ in range(1000):
   ...:         if not True:
   ...:             return False
   ...:     return True
   ...: 

In [3]: %timeit loop()
10000 loops, best of 3: 30.3 µs per loop


Явный for-цикл может быть эффективней генератора в CPython (результат также может
зависеть от платформы). 

all_(), реализованная вручную, слегка медленнее встроенной версии all(), которая
реализует похожий цикл в C:

def all_(iterable):
    for item in iterable:
        if not item:
            return False
    return True


то есть важно что генератор используется, а не то как all() реализована:

In [4]: %timeit all_(range(1, 1000))
10000 loops, best of 3: 41.1 µs per loop
In [5]: %timeit all_(i  for i in range(1, 1000))
10000 loops, best of 3: 93.9 µs per loop




Даже генератор списков (listcomp—списковое включение) может быть эффективней эквивалентного
genexpr (хотя в Jython это с точностью до наоборот):

In [6]: %timeit [True for _ in range(1000)]
10000 loops, best of 3: 44.4 µs per loop

In [7]: %timeit list(True for _ in range(1000))
10000 loops, best of 3: 83.2 µs per loop


Хотя между этими выражениями не должно быть особой разницы в Питоне 3: Why this list
comprehension is faster than equivalent generator expression?

Байт-код ничего особо подозрительного не показывает:

>>> import dis
>>> dis.dis(lambda: [True for _ in range(1000000)])
  1           0 LOAD_CONST               1 ( at 0x610efc445eea,
file "", line 1>)
              3 LOAD_CONST               2 ('..')
              6 MAKE_FUNCTION            0
              9 LOAD_GLOBAL              0 (range)
             12 LOAD_CONST               3 (1000000)
             15 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
             18 GET_ITER
             19 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
             22 RETURN_VALUE
>>> dis.dis(lambda: list(True for _ in range(1000000)))
  1           0 LOAD_GLOBAL              0 (list)
              3 LOAD_CONST               1 ( at 0x610efc4bc0b2,
file "", line 1>)
              6 LOAD_CONST               2 ('..')
              9 MAKE_FUNCTION            0
             12 LOAD_GLOBAL              1 (range)
             15 LOAD_CONST               3 (1000000)
             18 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
             21 GET_ITER
             22 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
             25 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
             28 RETURN_VALUE


Первый фрагмент: создаёт функцию из listcomp объекта и вызывает её с результатом
iter(range(1000000)). Второй фрагмент: создаёт функцию из genexpr и вызывает её с тем
же аргументом, дополнительно вызывается list() функция с результатом.

listcomp реализуется достаточно прямолинейно:

>>> code = compile('[True for _ in range(1000000)]', '', 'eval')
>>> code.co_consts[0]
 at 0x610efc445f2c, file "", line 1>
>>> dis.dis(code.co_consts[0])
  1           0 BUILD_LIST               0
              3 LOAD_FAST                0 (.0)
        >>    6 FOR_ITER                12 (to 21)
              9 STORE_FAST               1 (_)
             12 LOAD_CONST               0 (True)
             15 LIST_APPEND              2
             18 JUMP_ABSOLUTE            6
        >>   21 RETURN_VALUE


Что близко к: 

def listcomp(it):
    L = []
    for _ in it:
        L.append(True)
    return L


где it = iter(range(1000000)), полученный ранее.

genexpr выглядит похоже:

>>> code = compile('list(True for _ in range(1000000))', '', 'eval')
>>> code.co_consts[0]
 at 0x610efc44145d, file "", line 1>
>>> dis.dis(code.co_consts[0])
  1           0 LOAD_FAST                0 (.0)
        >>    3 FOR_ITER                11 (to 17)
              6 STORE_FAST               1 (_)
              9 LOAD_CONST               0 (True)
             12 YIELD_VALUE
             13 POP_TOP
             14 JUMP_ABSOLUTE            3
        >>   17 LOAD_CONST               1 (None)
             20 RETURN_VALUE


Что близко к:

def genexpr(it):
    for _ in it:
        yield True


созданный генератор (объект) передаётся во встроеннуюlist() функцию, которая реализована
вызовом listextend(), что выполняет код близкий к listcomp(it), приведённому выше.
Снова разница в производительности не в использовании list(), а в том что ей передан
генератор (list(range(1000)) и list(iter(range(1000)) могут быть быстрее как list(i
for i in range(1000)) так и [True for _ in range(1000)]).

Уже не так удивительно, что даже list([True for _ in range(1000)]), который казалось
бы выполняет лишнюю работу, может быть быстрее list(True for _ in range(1000)) (CPython/Pypy
2/3, Ubuntu).

Не стоит слишком увлекаться микрооптимизациями—пишите самый простой и понятный код,
который решает поставленную задачу. Не изменяйте код, пока измерения не показали, что
это необходимо в вашем конкретном случае.


Ответ 2


Посмотреть можно, используя profile. 

Как видно, время помимо isinstance

98902    0.125    0.000    0.125    0.000 :0(isinstance)

уходит на genexpr те генератор

98903    0.406    0.000    0.531    0.000 C:/Scripts/python/2016/4/123.py:21()

# -*- coding: UTF-8 -*-
import timeit
import profile, pstats
p = 'profile.txt'

def execTime(target_: list, repeat=1):
    target_[:] = [(fn.__name__, timeit.Timer(fn).timeit(repeat)) for fn in target_]
    for e, (n, tmt) in enumerate(sorted(target_, key=lambda r: r[1]), start=1):
        print("{}'time {} {}".format(e, n, tmt))

lst = [-3, 3, 7, 0, -10, 23, -9, -8, -5, -10, 9, 3,
 -2, 8, -3, 6, -1, 0, 10, -1, -6, -6, 10, -7, 3, 8,
 0, 7, 1, 5, -3, -6, 4, 6, -6, -4, -3, 10, 10, -5,
 -7, 0, -4, -8, 2, 9, 0, -10, -3, 3, -4, 9, -7, -8,
 0, -1, 1, 7, 2, -1, 3, 0, 9, -9, 4, 7, 6, 10, 8,
 -6, 3, 1, 1, 9, -8, -8, 2, 4, 10, 1, 5, -1, -1, 5,
 -9, 9, -3, 3, 0, -6, 2, 5, 10, 10, 5, -6, -10,  -2, -9]*999 + ['СТРОКА']


def test1():
    return all(isinstance(item, (int, float, complex)) for item in lst)

def test2():
    for a in lst:
        if not isinstance(a, (int, float, complex)): return

if __name__ == '__main__':
    print('-'*20, 1)
    profile.run('test1()', p)
    print(pstats.Stats(p).sort_stats('cumtime').print_stats())

    print('-'*20, 2)
    profile.run('test2()', p)
    print(pstats.Stats(p).sort_stats('cumtime').print_stats())

    print('-'*20, 3)
    execTime([test1, test2], 100)


out:

-------------------- 1
Mon Sep 19 10:45:57 2016    profile.txt

         197811 function calls in 0.672 seconds

   Ordered by: cumulative time

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.672    0.672 :0(exec)
        1    0.141    0.141    0.672    0.672 :0(all)
        1    0.000    0.000    0.672    0.672 C:/Scripts/python/2016/4/123.py:20(test1)
        1    0.000    0.000    0.672    0.672 :1()
        1    0.000    0.000    0.672    0.672 profile:0(test1())
    98903    0.406    0.000    0.531    0.000 C:/Scripts/python/2016/4/123.py:21()
    98902    0.125    0.000    0.125    0.000 :0(isinstance)
        1    0.000    0.000    0.000    0.000 :0(setprofile)
        0    0.000             0.000          profile:0(profiler)



-------------------- 2
Mon Sep 19 10:45:59 2016    profile.txt

         98907 function calls in 0.203 seconds

   Ordered by: cumulative time

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.203    0.203 :0(exec)
        1    0.000    0.000    0.203    0.203 :1()
        1    0.094    0.094    0.203    0.203 C:/Scripts/python/2016/4/123.py:23(test2)
        1    0.000    0.000    0.203    0.203 profile:0(test2())
    98902    0.109    0.000    0.109    0.000 :0(isinstance)
        1    0.000    0.000    0.000    0.000 :0(setprofile)
        0    0.000             0.000          profile:0(profiler)



-------------------- 3
1'time test2 3.4469346536397873
2'time test1 4.2089339634381275

Автор: на
Ярлыки: , , ,

Комментариев нет:

Отправить комментарий

Подписаться на: Комментарии к сообщению (Atom)