Python 3: наиболее эффективный способ создания списка [func (i) для i в диапазоне (N)] - PullRequest
Новая
       2

Python 3: наиболее эффективный способ создания списка [func (i) для i в диапазоне (N)]

7 голосов
/ 13 марта 2010

Скажем, у меня есть функция func (i), которая создает объект для целого числа i, а N - некоторое неотрицательное целое число. Тогда какой самый быстрый способ создать список (не диапазон), равный этому списку 

mylist = [func(i) for i in range(N)]

не прибегая к продвинутым методам, таким как создание функции в C? Моя главная проблема с приведенным выше пониманием списка заключается в том, что я не уверен, знает ли python заранее длину диапазона (N) для предварительного выделения mylist и, следовательно, должен постепенно перераспределять список. Это тот случай, или Python достаточно умен, чтобы сначала выделить mylist для длины N, а затем вычислить его элементы? Если нет, каков наилучший способ создания mylist? Может быть, это? 

mylist = [None]*N
for i in range(N): mylist[i] = func(i)

RE-EDIT: удалена вводящая в заблуждение информация из предыдущего редактирования.

Ответы [ 6 ]

7 голосов
/ 14 марта 2010

Кто-то писал: "" "Python достаточно умен. Пока объект, который вы перебираете, имеет метод __len__ или __length_hint__, Python будет вызывать его для определения размера и предварительного выделения массива." " «

Насколько я могу сказать, нет предраспределения в понимании списка . Python не может сказать, исходя из размера INPUT, каким будет размер OUTPUT.

Посмотрите на этот код Python 2.6: 

>>> def foo(func, iterable):
...     return [func(i) for i in iterable]
...
>>> import dis; dis.dis(foo)
  2           0 BUILD_LIST               0 #### build empty list
              3 DUP_TOP
              4 STORE_FAST               2 (_[1])
              7 LOAD_FAST                1 (iterable)
             10 GET_ITER
        >>   11 FOR_ITER                19 (to 33)
             14 STORE_FAST               3 (i)
             17 LOAD_FAST                2 (_[1])
             20 LOAD_FAST                0 (func)
             23 LOAD_FAST                3 (i)
             26 CALL_FUNCTION            1
             29 LIST_APPEND      #### stack[-2].append(stack[-1]); pop()
             30 JUMP_ABSOLUTE           11
        >>   33 DELETE_FAST              2 (_[1])
             36 RETURN_VALUE

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

Теперь посмотрите на этот код, который имеет «если» в понимании списка: 

>>> def bar(func, iterable):
...     return [func(i) for i in iterable if i]
...
>>> import dis; dis.dis(bar)
  2           0 BUILD_LIST               0
              3 DUP_TOP
              4 STORE_FAST               2 (_[1])
              7 LOAD_FAST                1 (iterable)
             10 GET_ITER
        >>   11 FOR_ITER                30 (to 44)
             14 STORE_FAST               3 (i)
             17 LOAD_FAST                3 (i)
             20 JUMP_IF_FALSE           17 (to 40)
             23 POP_TOP
             24 LOAD_FAST                2 (_[1])
             27 LOAD_FAST                0 (func)
             30 LOAD_FAST                3 (i)
             33 CALL_FUNCTION            1
             36 LIST_APPEND
             37 JUMP_ABSOLUTE           11
        >>   40 POP_TOP
             41 JUMP_ABSOLUTE           11
        >>   44 DELETE_FAST              2 (_[1])
             47 RETURN_VALUE
>>>

Тот же код, плюс некоторый код, чтобы избежать LIST_APPEND.

В Python 3.X вам нужно копать немного глубже: 

>>> import dis
>>> def comprehension(f, iterable): return [f(i) for i in iterable]
...
>>> dis.dis(comprehension)
  1           0 LOAD_CLOSURE             0 (f)
              3 BUILD_TUPLE              1
              6 LOAD_CONST               1 (<code object <listcomp> at 0x00C4B8D
8, file "<stdin>", line 1>)
              9 MAKE_CLOSURE             0
             12 LOAD_FAST                1 (iterable)
             15 GET_ITER
             16 CALL_FUNCTION            1
             19 RETURN_VALUE
>>> dis.dis(comprehension.__code__.co_consts[1])
  1           0 BUILD_LIST               0
              3 LOAD_FAST                0 (.0)
        >>    6 FOR_ITER                18 (to 27)
              9 STORE_FAST               1 (i)
             12 LOAD_DEREF               0 (f)
             15 LOAD_FAST                1 (i)
             18 CALL_FUNCTION            1
             21 LIST_APPEND              2
             24 JUMP_ABSOLUTE            6
        >>   27 RETURN_VALUE
>>>

Это та же старая схема: начните с создания пустого списка, затем итерируйте итерируемый, добавляя в список по мере необходимости. Я не вижу здесь никакого предварительного распределения.

Оптимизация, о которой вы думаете, используется внутри одного кода операции, например реализация list.extend(iterable) может предварительно выделить, если iterable может точно сообщить его длину. list.append(object) дается один объект, а не повторяемый.

2 голосов
/ 14 марта 2010

Если вы используете модуль timeit, вы можете прийти к противоположному выводу: понимание списка происходит быстрее, чем предварительное распределение: 

f=lambda x: x+1
N=1000000
def lc():
    return [f(i) for i in range(N)]
def prealloc():
    mylist = [None]*N
    for i in range(N): mylist[i]=f(i)
    return mylist
def xr():
    return map(f,xrange(N))

if __name__=='__main__':
    lc()

Предупреждение : Это результаты на моем компьютере. Вы должны попробовать эти тесты самостоятельно, так как ваши результаты могут отличаться в зависимости от вашей версии Python и вашего оборудования. (Смотрите комментарии.) 

% python -mtimeit -s"import test" "test.prealloc()"
10 loops, best of 3: 370 msec per loop
% python -mtimeit -s"import test" "test.lc()"
10 loops, best of 3: 319 msec per loop
% python -mtimeit -s"import test" "test.xr()"
10 loops, best of 3: 348 msec per loop

Обратите внимание, что в отличие от ответа Хавьера, я включаю mylist = [None]*N в качестве части времени кода при использовании метода "предварительного выделения". (Это не просто часть установки, поскольку это код, который потребуется только при использовании предварительного выделения.)

PS. модуль time (и команда time (unix)) может давать ненадежные результаты . Если вы хотите рассчитать код Python, я бы рекомендовал придерживаться модуля timeit.

2 голосов
/ 14 марта 2010

Нет разницы в сложности вычислений между использованием массива с автоматическим изменением размера и предварительным выделением массива В худшем случае это стоит около O (2N). Смотрите здесь:

Постоянное амортизированное время

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

1 голос
/ 14 марта 2010

Интересный вопрос. Что касается следующего теста, кажется, что предварительное распределение не улучшает производительность в текущей реализации CPython (код Python 2, но ранжирование результатов такое же, за исключением того, что в Python 3 нет xrange): 

N = 5000000

def func(x):
    return x**2

def timeit(fn):
    import time
    begin = time.time()
    fn()
    end = time.time()
    print "%-18s: %.5f seconds" % (fn.__name__, end - begin)

def normal():
    mylist = [func(i) for i in range(N)]

def normalXrange():
    mylist = [func(i) for i in xrange(N)]

def pseudoPreallocated():
    mylist = [None] * N
    for i in range(N): mylist[i] = func(i)

def preallocated():
    mylist = [None for i in range(N)]
    for i in range(N): mylist[i] = func(i)

def listFromGenerator():
    mylist = list(func(i) for i in range(N))

def lazy():
    mylist = (func(i) for i in xrange(N))



timeit(normal)
timeit(normalXrange)
timeit(pseudoPreallocated)
timeit(preallocated)
timeit(listFromGenerator)
timeit(lazy)

Результаты (рейтинг в скобках): 

normal            : 7.57800 seconds (2)
normalXrange      : 7.28200 seconds (1)
pseudoPreallocated: 7.65600 seconds (3)
preallocated      : 8.07800 seconds (5)
listFromGenerator : 7.84400 seconds (4)
lazy              : 0.00000 seconds

но с psyco.full(): 

normal            : 7.25000 seconds  (3)
normalXrange      : 7.26500 seconds  (4)
pseudoPreallocated: 6.76600 seconds  (1)
preallocated      : 6.96900 seconds  (2)
listFromGenerator : 10.50000 seconds (5)
lazy              : 0.00000 seconds

Как видите, псевдопрераспределение быстрее с психо. В любом случае, между решением xrange (которое я бы порекомендовал) и другими решениями нет особой разницы. Если вы не обработаете все элементы списка позже, вы также можете использовать ленивый метод (показанный в приведенном выше коде), который создаст генератор, который создает элементы к тому времени, когда вы выполняете итерацию по нему.

1 голос
/ 14 марта 2010

Здесь придется не согласиться с Хавьером ...

Со следующим кодом: 

print '%5s | %6s | %6s' % ('N', 'l.comp', 'manual')
print '------+--------+-------'
for N in 10, 100, 1000, 10000:
    num_iter = 1000000 / N

    # Time for list comprehension.
    t1 = timeit.timeit('[func(i) for i in range(N)]', setup='N=%d;func=lambda x:x' % N, number=num_iter)

    # Time to build manually.
    t2 = timeit.timeit('''mylist = [None]*N
for i in range(N): mylist[i] = func(i)''', setup='N=%d;func=lambda x:x' % N, number=num_iter)

    print '%5d | %2.4f | %2.4f' % (N, t1, t2)

Я получаю следующую таблицу: 

    N | l.comp | manual
------+--------+-------
   10 | 0.3330 | 0.3597
  100 | 0.2371 | 0.3138
 1000 | 0.2223 | 0.2740
10000 | 0.2185 | 0.2771

Из этой таблицы видно, что понимание списка быстрее, чем предварительное распределение в каждом случае этих переменных длин.

0 голосов
/ 14 марта 2010

Использование понимания списка для выполнения того, что вы пытаетесь сделать, было бы более питонным способом сделать это Несмотря на снижение производительности:).

...