파이썬에서 병합
내 mergesort 구현은 현재 매우 오랜 시간이 걸립니다. 1 백만 개의 요소가있는 목록의 경우 목록을 정렬하는 데 130 초 이상 걸립니다.
누군가 내 코드를 친절하게보고 개선 할 수있는 방법을 제안 할 수 있습니까?
내 코드에 상당히 오래 걸리는 특별한 것이 있습니까?
암호
def splitlist(L): #splits the list to a list of individual listed elements (e.g. [1,2] to [[1],[2]])
envelop = lambda x: [x]
return(list(map(envelop,L)))
def merge(L_1,L_2): #merges two (already sorted) lists to one sorted list
N = []
while len(L_1) > 0 and len(L_2) > 0:
if L_1[0] > L_2[0]:
N += [L_2.pop(0)]
else:
N += [L_1.pop(0)]
if len(L_1) == 0:
N += L_2
else:
N += L_1
return(N)
#performs one round of pairwise merges (e.g. [[2],[1],[4],[3]] to [[1,2],[3,4]]), or [[5,10],[1,8],[2,3]] to [[1,2,3,5,8,10]])
def mergelist(L):
N = []
if len(L) % 2 == 0:
for i in range(0,len(L)//2):
N += [merge(L[2*i],L[2*i + 1])]
else:
for i in range(0,len(L)//2 - 1):
N += [merge(L[2*i],L[2*i + 1])]
N += [merge(merge(L[-3],L[-2]),L[-1])]
return(N)
def mergesort(L): #recursively performs mergelist until there is only 1 sorted list remaining
L = splitlist(L)
while len(L) > 1:
L = mergelist(L)
return(L[0])
백만 개의 요소를 생성하는 코드는 다음과 같습니다.
rlist = random.sample(range(0,2000000),1000000)
답변
pop(0)선형 시간 이 걸립니다. O (1) 시간에 다르게하십시오. 표준 방식은 인덱스 변수를 사용합니다. 더 파이썬적인 방법에 대해서는 이 질문 의 답변을 참조하십시오 . 또는를 사용하여 오른쪽에서 왼쪽으로 병합 pop()한 다음 결국 reverse()결과를 얻을 수 있습니다.
후자를 수행하는 한 가지 방법 :
def merge(L1, L2):
"""Merges two (already sorted) lists to one sorted list."""
N = []
while L1 and L2:
L = L1 if L1[-1] > L2[-1] else L2
N.append(L.pop())
N.reverse()
N[:0] = L1 or L2
return N
내가 한 다른 변경 사항은 코드의 다른 부분에도 적용 할 수 있습니다.
- 변수에서 밑줄을 제거하여 더 잘 읽는다고 생각합니다. 나는 그들에게 있기 때문에 대한 대문자를 유지
L의 어떤 것을, PEP 8 말한다 . 그리고N일관성을 유지 했습니다. 일반적으로 내가 사용하는 거라고result어쩌면 나merged. 을 선택한 이유를 모르겠습니다N. "n"으로 시작하는 의미있는 단어가 있다면 그것을 사용하는 것이 좋습니다. - 함수 매개 변수 사이의 공간.
- 주석 대신 적절한 독 스트링 형식.
len(L_1) > 0일반L1비어 있지 않은 검사 로 대체 되었습니다 .- 대체
N += [x]정상으로N.append(x).
또 다른 방법은 "긴"줄을 L더 명확하지만 느린 방법으로 바꾸는 것입니다 .
def merge(L1, L2):
"""Merges two (already sorted) lists to one sorted list."""
N = []
def last(L):
return L[-1]
while L1 and L2:
L = max(L2, L1, key=last)
N.append(L.pop())
N.reverse()
N[:0] = L1 or L2
return N
재미를 위해 두 가지 목록 이해 해킹 :
def merge(L1, L2):
"""Merges two (already sorted) lists to one sorted list."""
def end(L):
return L[-1:]
return [max(L2, L1, key=end).pop() for _ in L1 + L2][::-1]
def merge(L, R):
"""Merges two (already sorted) lists to one sorted list."""
return [(R, L)[L[-1:] > R[-1:]].pop() for _ in L + R][::-1]
그리고 훨씬 더 빠른 방법 없이는 떠나고 싶지 않습니다.
def merge(L1, L2):
"""Merges two (already sorted) lists to one sorted list."""
return sorted(L1 + L2)
Timsort 때문에 O (n)입니다. 그리고 C 코드 때문에 빠른 O (n). sortedMergesort 내부 에서 강력한 기능을 사용하는 것이 처음부터 mergesort를 작성하는 목적에 맞지 않는다고 생각한다면 : Mergesort 만하는 것이 아니라면 의미가있을 수 있습니다. 적어도 한 번은 무언가를 포함하는 병합 정렬을 작성했으며 실제로 sorted병합을 위해 사용했습니다 . 그것은 내 솔루션을 더 빠르고 / 짧게 / 단순하게 만들었 기 때문입니다.
훨씬 더 효율적 (공간과 시간 모두) :
def merge(L1, L2):
"""Merges two (already sorted) lists to one sorted list."""
L1 += L2
L1.sort()
return L1
(경우 L2이상이 될 수 있습니다 L1, 삽입하는 것이 유리할 수 있습니다 L1로 L2대신.)