Python : 목록 앞쪽의 요소를 효율적으로 제거 하시겠습니까?

Question

긴 숫자 목록의 시작 부분에서 요소를 제거 할 수있는 방법이 있습니까? 지금 나는 del arr [i : i + x]를하고 있지만, 그 점을 지나서 모든 것을 왼쪽으로 옮겨야하므로 속도가 느려지므로 큰 목록에는 시간이 많이 걸립니다.

나는 여기에 적용되는지 모르겠지만 확실하지 않습니다. 어떤 방향을 사용할 수있었습니다!

Answer 1

예 deque 예를 들어 적용해야합니다. 정면에 매우 가까이 있으면 매우 빠르지 만 시작 색인이 중간에 있으면 느리게 나타납니다.

색인 액세스는 양 끝에서 O (1)이지만 중간에 O (n)까지 느려집니다.

def delete_slice(d, start, stop): 
    stop = min(stop, len(d)) # don't go past the end 
    start = min(start, stop) # don't go past stop 
    if start < len(d) // 2: 
     d.rotate(-start) 
     for i in range(stop-start): # use xrange on Python 2 
      d.popleft() 
     d.rotate(start) 
    else: 
     n = len(d) - stop 
     d.rotate(n) 
     for i in range(stop - start): 
      d.pop() 
     d.rotate(-n) 

:

>>> from collections import deque 
>>> def delete_slice(d, start, stop): 
     d.rotate(-start) 
     for i in range(stop-start): # use xrange on Python 2 
      d.popleft() 
     d.rotate(start) 


>>> d = deque(range(15)) 
>>> delete_slice(d, 5, 10) 
>>> d 
deque([0, 1, 2, 3, 4, 10, 11, 12, 13, 14]) 

참고 : 당신은 당신과 같이 코드를 확장 할 수 있습니다 오른쪽에서 빠른 삭제를 지원하려면 중간 과거의 회전은, 이전에 언급 한 바와 같이, 속도가 느린 것

물론 다른 오류 검사가 필요 하겠지만 간단하게하기 위해 여기에서 빠져 나갈 것입니다. 불행히도 이러한 메서드는 이미 deque 자체에서 제공하지 않으므로 이러한 메서드를 구현해야합니다.

는, 양단 큐 슬라이스를 구현하는 deque의 왼쪽에 대상 요소를 가져 rotate()을 적용 유사한 방법을 사용합니다. popleft()으로 이전 항목을 제거하고 extend()과 함께 새 항목을 추가 한 다음 회전을 되돌립니다. 이 접근법의 사소한 변형으로 dup, drop, swap, over, pick, rot 및 roll과 같은 Forth 스타일 스택 조작을 쉽게 구현할 수 있습니다.

Answer 2

예, 여기에 deque이 적용됩니다. 보여주는 예제를 준비했습니다 사용 방법 :

import collections 

"create deque from list" 
d=collections.deque([1,2,3,4,5,6]) 
"remove first element" 
d.popleft() 

print d 

출력 :

deque([2,3,4,5,6]) 

Answer 3

당신이 순서대로 번호를 유지하기를 원한다면 당신은 지정하지 않았습니다. 가장 빠른 옵션은 목록의 시작 부분에있는 번호를 목록 끝에있는 번호로 바꾸는 것입니다. 당신은 색인 작업을해야하는 경우

arr = [e for e in arr if not rejected(e)] 

것은, 당신이 사용할 수 있습니다 : 당신이 연속으로 여러 삭제를하고 있다면

Answer 4

, 필터와 발전기를 사용하여 새 목록을 작성하는 것이 더 효율적이 될 수있다 열거 :

arr = [e for i, e in enumerate(arr) if not rejected(i)] 

모두 동작은 O (N) (공간 O (2 * N)), 연속으로 몇 삭제를 수행하면 O (n 개 *의 m) 인 동안 (단, 공간 N O()) .

인덱스 액세스 (1) 양쪽 끝에 O하지만 중간에 O (N)에 속도가 느려집니다 :

deque

당신이 원하는 것이 아닐 수도 있습니다 특성을 가지고 있습니다.

Answer 5

나는 당신이 아마 트리 또는 skiplist을 원하는 생각하고 있어요. http://stromberg.dnsalias.org/~strombrg/python-tree-and-heap-comparison/

당신은 사이트의 알고리즘 섹션에서 이것에 대해 물어 더 나을 수 있습니다

나는 잠시 다시 파이썬 트리 구현에 대한 연구를했다.