python의 목록에서 요소를 제거합니다.

Question

O (1) complexity.i.e., remove (value) : 의 목록에서 요소를 제거하는 방법은 목록에서 선형으로 검색하고 오른쪽을 제거합니다. 그래서 인덱스 또는 값을 지정하여 O (1) 복잡도의 요소를 삭제하는 방법이 있습니까?

"del"을 사용한 후에도 다음 코드에 크기 100000의 입력 목록이 주어지면 제한 시간을 초과합니다.

l=map(int,raw_input("").split(" ")) 
n=l[0] 
k=l[1] 
s=map(int,raw_input("").split(" ")) 
s=sorted(s) 
count=0 
tree=[] 
while len(s)>0: 
    poset=[] 
    indices=[] 
    i=0 
    poset.append(s[i]) 
    indices.append(0) 
    j=i+1 
    while j<len(s): 
     if s[j]==k*s[i]: 
      poset.append(s[j]) 
      indices.append(j) 
      i=j 
     j+=1 
    tmp=0 
    for i in indices: 
     del s[i-tmp] 
     tmp+=1     
    tree.append(poset) 

for i in tree: 
    if len(i)%2==0: 
     count+=(len(i))/2 
    else: 
     count+=(len(i)+1)/2 
print count 

Answer 1

공식적으로.

C++을 알고 있다면 파이썬리스트는 오브젝트에 대한 포인터가 std::vector 개 (C 언어로는 포인터의 연속 배열에 대한 포인터)로 구현됩니다. 이것은 주어진 인덱스에 대해 O (1) 액세스를 제공하고 크기 조정을 허용하지만, 목록에서 요소를 삭제하면 간격을 채우기 위해 모든 후속 요소를 하나의 요소만큼 아래로 이동해야합니다.

그러나 이동되는 것은 포인터 일 뿐이며 참조 카운터를 수정하지 않아도되므로 매우 빠릅니다 (기본적으로는 memmov이라는 단일 호출). 목록이 거대하지 않은 한 이동에 필요한 시간은 극히 적습니다.

인덱스가 del L[index]을 사용하여 알려진 경우 Python의 목록에서 요소를 삭제하는 것은 형식적으로는 O(N)이지만 작은 상수 요소가 있습니다.

list 개체를 구현하여 목록 개체에 "단계"값을 추가하여 어느 한쪽 끝에서 일정한 시간을 제거 할 수 있습니다. 이렇게하면 O(1) (약간 큰 상수)이 유지되지만 del L[0]은 O(1)이되어 deque과 유사하게됩니다.

그러나이 경우는 일반적인 경우에 대해 list 액세스가 더 복잡해지고 특정 구조가 deque 인 특수한 경우에 맞게 최적화되므로 구현되지 않았습니다. 또한 모든 C 확장 모듈 액세스 목록과의 호환성이 손상됩니다.

Answer 2

인덱스 또는 값을 지정하여 O (1) 복잡도의 요소를 삭제할 수있는 방법이 있습니까?

인덱스는 다음

del L[index] 

작품 매우 빠르게 무엇인지 알고있는 경우 (하지만 의외로하지 O (1) - https://www.python.org/dev/peps/pep-3128/#motivation). 당신이 가치를 안다면, 그것은 어디서나있을 수 있습니다. 그래서 당신은 그것을 찾아야 할 것입니다. 평균적으로 요소의 절반을 확인해야하므로 O (N)입니다.

기타 데이터 구조가 도움이 될 수 있습니다. 별개의 요소가 무엇인지 알기 만하면 (그리고 순서를 신경 쓰지 않아도됩니다.) 집합을 사용할 수 있습니다.

s = set(['1','b', '1', 'a', 1]) 
s 
s.remove(1) 
s 

출력

{1, '1', 'a', 'b'} 
{'1', 'a', 'b'} 

을 산출하고 제거 명령 (기본적) O (1)

Answer 3

열기 파이썬 단말기 (예를 들어jupyer)이 시도 : 보시다시피

>>>: %%timeit 
...: l = [i for i in range(10000000)] 
...: del l[0] # O(?) 
322 ms ± 1.68 ms per loop (mean ± std. dev. of 7 runs, 1 loop each) 

>>>: %%timeit 
...: l = list(range(10000000)) 
...: del l[0] # O(?) 
195 ms ± 1.42 ms per loop (mean ± std. dev. of 7 runs, 1 loop each) 

>>>: %%timeit 
...: l = [i for i in range(10000000)] 
...: del l[-1] # O(?) 
306 ms ± 2.64 ms per loop (mean ± std. dev. of 7 runs, 1 loop each) 

>>>>: %%timeit 
...: l = list(range(10000000)) 
...: del l[-1] # O(?) 
267 ms ± 2.68 ms per loop (mean ± std. dev. of 7 runs, 10 loops each) 

>>>: %%timeit 
...: l = [i for i in range(10000000)] 
...: l.append(500) # O(1) 
299 ms ± 3.28 ms per loop (mean ± std. dev. of 7 runs, 1 loop each) 

%%timeit 
...: l = list(range(10000000)) 
...: l.append(500) # O(1) 
265 ms ± 1.87 ms per loop (mean ± std. dev. of 7 runs, 10 loops each) 

>>>: %%timeit 
...: l = [i for i in range(10000000)] 
...: max(l) # O(n) 
463 ms ± 15.5 ms per loop (mean ± std. dev. of 7 runs, 1 loop each) 

>>>: %%timeit 
...: l = list(range(10000000)) 
...: max(l) # O(n) 
335 ms ± 10.7 ms per loop (mean ± std. dev. of 7 runs, 1 loop each) 

>>>: from collections import deque # lets compare with deque 

>>>: %%timeit 
...: l = deque(range(10000000)) 
...: max(l) # O(n) 
365 ms ± 1.83 ms per loop (mean ± std. dev. of 7 runs, 1 loop each) 

>>>: %%timeit 
...: l = deque(range(10000000)) 
...: l.append(500) #O(1) 
283 ms ± 5.19 ms per loop (mean ± std. dev. of 7 runs, 10 loops each) 

>>>: %%timeit 
...: l = deque(range(10000000)) 
...: del l[0] 
279 ms ± 2.78 ms per loop (mean ± std. dev. of 7 runs, 10 loops each) 

>>>: %%timeit 
...: l = deque(range(10000000)) 
...: del l[9999999] 
286 ms ± 3.87 ms per loop (mean ± std. dev. of 7 runs, 10 loops each) 

가하는 양단에서 인덱스 항목을 제거하는 O의 복잡성이있다 (1), 인덱스 목록에서 제거하는 동안 것은 비교 sligthly 더 넓은하지만 매우 일정한 여전히 최대 계산과 같은 다른 O (n) 연산으로 변환합니다. 이것은 @ 6502 대답과 일치합니다. 어쨌든, 당신이 지시 된 목록 초기화기를 사용해야한다면, 시간이 비용 처리 절차에 의해 지배되기 때문에 그 차이가 거의 없다. 실제 생성자에 대한 호출을 통한 지시 된 초기화가 바람직합니다.