Hợp nhất trong python

Question

Việc triển khai hợp nhất của tôi hiện mất rất nhiều thời gian, đối với một danh sách có 1 triệu phần tử, phải mất hơn 130 giây để danh sách được sắp xếp.

• Ai đó có thể vui lòng xem mã của tôi và đề xuất tôi có thể làm gì để cải thiện nó không?

• Có điều gì cụ thể trong mã của tôi mà mất nhiều thời gian không?

Mã

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])

Đây là mã của tôi để tạo triệu phần tử:

rlist = random.sample(range(0,2000000),1000000)

Answer 1

Thời pop(0)gian tuyến tính mất. Làm điều đó theo cách khác, trong O (1) thời gian. Cách tiêu chuẩn sử dụng các biến chỉ số. Xem câu trả lời của câu hỏi này để biết thêm một số cách trị trăn. Hoặc bạn có thể hợp nhất từ ​​phải sang trái, sử dụng pop(), và cuối cùng reverse()là kết quả.

Một cách để làm sau:

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

Những thay đổi khác mà tôi đã thực hiện và những thay đổi bạn cũng có thể áp dụng trong các phần khác của mã của mình:

• Đã xóa dấu gạch dưới khỏi các biến, tôi nghĩ nó đọc tốt hơn. Tôi giữ chúng viết hoa bởi vì L, đó là những gì PEP 8 nói . Và sau đó tôi giữ Ncho nhất quán. Thường thì tôi sẽ sử dụng resulthoặc có thể merged. Không biết tại sao bạn lại chọn N. Nếu bạn có một từ có nghĩa bắt đầu bằng "n", thì tôi khuyên bạn nên sử dụng từ đó.
• Khoảng trắng giữa các tham số chức năng.
• Định dạng docstring thích hợp thay vì nhận xét.
• Đã thay thế len(L_1) > 0bằng L1kiểm tra không trống thông thường .
• Đã thay thế N += [x]bằng bình thường N.append(x).

Chỉ có một cách khác, thay thế một dòng "dài" đó để xác định Lbằng một cách rõ ràng hơn nhưng chậm hơn:

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

Đối với một số niềm vui, hai thủ thuật hiểu danh sách:

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]

Và tôi không muốn rời đi mà không có cách nào nhanh hơn nhiều:

def merge(L1, L2):
    """Merges two (already sorted) lists to one sorted list."""
    return sorted(L1 + L2)

Đó là O (n) vì Timsort. Và nhanh O (n) vì mã C. Nếu bạn nghĩ rằng việc sử dụng sức mạnh sortedbên trong một hợp nhất sẽ đánh bại mục đích của việc viết hợp nhất ngay từ đầu: Thậm chí điều đó có thể có ý nghĩa, nếu bạn không chỉ làm hợp nhất. Ít nhất một lần tôi đã viết một hợp nhất với số đếm được nhúng của một cái gì đó và tôi thực sự đã sử dụng sortedchỉ để hợp nhất. Bởi vì điều đó đã làm cho giải pháp của tôi nhanh hơn / ngắn hơn / đơn giản hơn.

Hiệu quả hơn nữa (cả không gian và thời gian):

def merge(L1, L2):
    """Merges two (already sorted) lists to one sorted list."""
    L1 += L2
    L1.sort()
    return L1

(Nếu L2có thể dài hơn L1, có thể có lợi khi chèn L1vào L2.)