Gabungkan dengan python

Question

Implementasi penggabungan saya saat ini membutuhkan waktu yang sangat lama, untuk daftar dengan 1 juta elemen dibutuhkan lebih dari 130 detik untuk menyortir daftar.

• Bisakah seseorang dengan baik hati melihat kode saya dan menyarankan apa yang dapat saya lakukan untuk memperbaikinya?

• Apakah ada hal khusus dalam kode saya yang memakan waktu sangat lama?

Kode

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

Inilah kode saya untuk menghasilkan jutaan elemen:

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

Answer 1

Ini pop(0)membutuhkan waktu linier. Lakukan itu secara berbeda, dalam waktu O (1). Cara standar menggunakan variabel indeks. Lihat jawaban pertanyaan ini untuk beberapa cara pythonic lainnya. Atau Anda bisa menggabungkan dari kanan ke kiri, menggunakan pop(), dan pada akhirnya reverse()hasilnya.

Salah satu cara untuk melakukan yang terakhir:

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

Perubahan lain yang saya lakukan dan yang dapat Anda terapkan di bagian lain kode Anda juga:

• Menghapus garis bawah dari variabel, menurut saya terbaca lebih baik. Saya menyimpannya dalam huruf besar karena untuk L, itulah yang dikatakan PEP 8 . Dan kemudian saya menjaga Nkonsistensi. Biasanya saya akan menggunakan resultatau mungkin merged. Tidak tahu mengapa Anda memilih N. Jika Anda memiliki kata yang bermakna yang dimulai dengan "n", maka saya sarankan untuk menggunakannya.
• Spasi antar parameter fungsi.
• Format docstring yang tepat, bukan komentar.
• Diganti len(L_1) > 0dengan pemeriksaan L1non-kekosongan normal .
• Diganti N += [x]dengan normal N.append(x).

Cara lain, mengganti satu baris "panjang" itu untuk menentukan Ldengan cara yang lebih jelas tapi lebih lambat:

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

Untuk bersenang-senang, dua peretasan pemahaman daftar:

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]

Dan saya tidak ingin pergi tanpa cara yang lebih cepat:

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

Itu O (n) karena Timsort. Dan cepat O (n) karena kode C. Jika Anda berpikir menggunakan perkasa sorteddi dalam mergesort mengalahkan tujuan penulisan mergesort di tempat pertama: Bahkan itu bisa bermakna, jika Anda tidak hanya melakukan mergesort. Setidaknya sekali saya menulis sortedpenggabungan dengan penghitungan tertanam dari sesuatu, dan saya memang menggunakan hanya untuk penggabungan. Karena itu membuat solusi saya lebih cepat / pendek / sederhana.

Bahkan lebih efisien (baik ruang maupun waktu):

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

(Jika L2boleh lebih dari L1, mungkin menguntungkan untuk memasukkan L1ke dalam L2gantinya.)