[python] 짧은 파이썬 목록을 추가하기위한 관용구 문은 무엇입니까?

짧은 파이썬 목록을 추가하기위한 관용구 문은 무엇입니까?

일반적으로 Python의 목록 앞에 반복적으로 추가하고 싶지 않습니다.

그것의 경우 짧은 , 당신이 그것을 많이 안하고 … 다음 확인을 클릭합니다.

list.insert

은 list.insert이 방법을 사용할 수 있습니다.

list.insert(0, x)

그러나 파이썬에서는 a list가 포인터의 배열이므로 파이썬은 목록의 모든 포인터를 가져 와서 포인터를 첫 번째 슬롯에 객체에 삽입하기 위해 하나씩 아래로 이동해야하므로 비효율적입니다. 당신이 요청 한대로 오히려 짧은 목록.

CPython 소스 의 스 니펫 은 다음과 같습니다. 여기서 알 수 있듯이 배열의 끝에서 시작하여 모든 삽입마다 하나씩 아래로 이동합니다.

for (i = n; --i >= where; )
    items[i+1] = items[i];

요소 앞에 붙일 수있는 컨테이너 / 목록을 원한다면 연결된 목록이 필요합니다. 파이썬은 이중 연결리스트를 가지고 있는데, 처음에는 빠르게 삽입하고 끝낼 수 deque있습니다.

deque.appendleft

A collections.deque에는 목록의 많은 방법이 있습니다. list.sort만들기 예외 인 deque에 대한 결정적 전적으로 Liskov의 대용은 list.

>>> set(dir(list)) - set(dir(deque))
{'sort'}

는 deque또한 갖는다 appendleft방법 (뿐만 아니라 popleft). 는 deque이중 종료 큐와 이중 연결리스트이다 -에 상관없이 길이는 항상 preprend 뭔가에 동일한 시간이 소요됩니다. 큰 O 표기법에서 O (1) 대 목록의 O (n) 시간. 사용법은 다음과 같습니다.

>>> import collections
>>> d = collections.deque('1234')
>>> d
deque(['1', '2', '3', '4'])
>>> d.appendleft('0')
>>> d
deque(['0', '1', '2', '3', '4'])

deque.extendleft

또한 deque의 extendleft방법 이 관련이 있으며 반복적으로 앞에 붙습니다.

>>> from collections import deque
>>> d2 = deque('def')
>>> d2.extendleft('cba')
>>> d2
deque(['a', 'b', 'c', 'd', 'e', 'f'])

각 요소는 한 번에 하나씩 추가되므로 순서를 효과적으로 반대로 바꿉니다.

list대 성능deque

먼저 우리는 몇 가지 반복적 인 접두사로 설정합니다.

import timeit
from collections import deque

def list_insert_0():
    l = []
    for i in range(20):
        l.insert(0, i)

def list_slice_insert():
    l = []
    for i in range(20):
        l[:0] = [i]      # semantically same as list.insert(0, i)

def list_add():
    l = []
    for i in range(20):
        l = [i] + l      # caveat: new list each time

def deque_appendleft():
    d = deque()
    for i in range(20):
        d.appendleft(i)  # semantically same as list.insert(0, i)

def deque_extendleft():
    d = deque()
    d.extendleft(range(20)) # semantically same as deque_appendleft above

그리고 성능 :

>>> min(timeit.repeat(list_insert_0))
2.8267281929729506
>>> min(timeit.repeat(list_slice_insert))
2.5210217320127413
>>> min(timeit.repeat(list_add))
2.0641671380144544
>>> min(timeit.repeat(deque_appendleft))
1.5863927800091915
>>> min(timeit.repeat(deque_extendleft))
0.5352169770048931

deque가 훨씬 빠릅니다. 목록이 길어질수록 deque가 더 잘 수행 될 것으로 기대합니다. deque를 사용할 수 있다면 extendleft아마도 최고의 성능을 얻을 것입니다.

답변

Python 2.7.8

In [1]: %timeit ([1]*1000000).insert(0, 0)
100 loops, best of 3: 4.62 ms per loop

In [2]: %timeit ([1]*1000000)[0:0] = [0]
100 loops, best of 3: 4.55 ms per loop

In [3]: %timeit [0] + [1]*1000000
100 loops, best of 3: 8.04 ms per loop