ผสานใน python

Question

ขณะนี้การใช้งาน 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)

Answer 1

pop(0)ต้องใช้เวลาในการเชิงเส้น ทำสิ่งนั้นต่างออกไปใน O (1) ครั้ง วิธีมาตรฐานใช้ตัวแปรดัชนี ดูคำตอบของคำถามนี้เพื่อดูวิธีการ pythonic เพิ่มเติม หรือคุณสามารถผสานจากขวาไปซ้ายโดยใช้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" ฉันขอแนะนำให้ใช้คำนั้น
• ช่องว่างระหว่างพารามิเตอร์ฟังก์ชัน
• รูปแบบ docstring ที่เหมาะสมแทนการแสดงความคิดเห็น
• แทนที่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)

นั่นคือ O (n) เพราะ Timsort และรวดเร็ว O (n) เนื่องจากรหัส C หากคุณคิดว่าการใช้อันยิ่งใหญ่sortedภายในการผสานจะเอาชนะจุดประสงค์ของการเขียนการผสานในตอนแรก: แม้ว่าจะมีความหมาย แต่ถ้าคุณไม่เพียงแค่ทำการผสาน อย่างน้อยครั้งหนึ่งฉันเขียนsortedการผสานที่มีการนับสิ่งที่ฝังไว้และฉันก็ใช้เพื่อการรวมเท่านั้น เพราะนั่นทำให้โซลูชันของฉันเร็วขึ้น / สั้นลง / ง่ายขึ้น

มีประสิทธิภาพมากยิ่งขึ้น (ทั้งพื้นที่และเวลา):

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

(ถ้าL2ยาวกว่าL1นั้นอาจเป็นประโยชน์ในการแทรกL1เข้าไปL2แทน)