Python3 - merge sort, O (n) efisiensi ruang

Question

Kritik apa pun terhadap penerapan Gabung jenis saya akan sangat dihargai! Saya mengujinya menggunakan fungsi driver (ditampilkan di bawah), dan semuanya berfungsi. Namun masih terasa berat, saya seorang pemula jadi saya sangat ingin mendengar kritik, konstruktif atau tidak :)

def inplace_merge_sort( lst, start = 0 , end = None ):
  def inplace_merge( lst1_start, lst1_end , lst2_start, lst2_end ): #needs to take in two sets of unsorted indices 
    start, end = lst1_start, lst2_end
    for _ in range( (end - start) ):
      if(lst[lst1_start] < lst[lst2_start]):
        lst1_start += 1

      else:
        lst.insert(lst1_start , lst[lst2_start])
        del lst[lst2_start + 1]
        lst1_start += 1
        lst2_start += 1

      if( lst1_start == lst2_start or lst2_start == lst2_end):
        break

    return start, end #returns indices of sorted newly sublist



  if( len(lst) == 1 or len(lst) == 0): #catches edge cases
    return lst

  if end is None: end = len(lst) #so I don't have to input parameters on first call 

  
  length_sublist = end - start 

  if( length_sublist > 1):
    start1, end1 = inplace_merge_sort( lst, start, (end + start) // 2  )
    start2, end2 = inplace_merge_sort( lst, (end + start) // 2 , end  )
  
    return inplace_merge(start1, end1, start2, end2)

  else: 
    return start, end

Berikut adalah fungsi pengujiannya

def inplace_driver_helper(f_n):
  def modified_list_returner( lst ):
    f_n(lst)
    return lst
  return modified_list_returner

def driver(f_n):
  # NICK I added these two test cases to catch some popular edge cases.
    assert f_n([]) == []
    assert f_n([4]) == [4]

    assert f_n([1,2,3]) == [1,2,3]

    assert f_n([3,2,1]) == [1,2,3]

    assert f_n([1,2,3,1,2,3]) == [1,1,2,2,3,3]

    assert f_n([1,2,3,1,1,2,3]) == [1,1,1,2,2,3,3]

    assert f_n([-1,0,46,2,3,1,2,3]) == [-1,0,1,2,2,3,3,46]

dan saat kita menjalankan ini,

if __name__ == '__main__':
    driver(inplace_driver_helper(inplace_merge_sort))

    print('done')

Outputnya 'selesai'!

Answer 1

• Penggabungan biasanya O (m) waktu, di mana m adalah jumlah elemen yang terlibat dalam penggabungan. Karena penyisipan dan penghapusan Anda, ini agak O (mn), di mana n adalah panjang dari seluruh daftar. Itu membuat seluruh waktu pengurutan O (n ^ 2 log n) Anda alih-alih O (n log n) biasa penggabungan.
• Anda menyebutnya inplace sort, yang menunjukkan bahwa ia tidak mengembalikan apa pun, tetapi Anda mengembalikan daftar jika pendek dan Anda mengembalikan beberapa indeks awal / akhir sebaliknya. Agak tidak konsisten dan membingungkan. Saya akan membuatnya tidak mengembalikan apa pun (selain default None).
• Fungsi Anda menawarkan untuk mengurutkan hanya sebagian dari daftar, tetapi Anda tidak mengujinya.
• Anda menggunakan beberapa nama variabel yang agak panjang. Saya akan menggunakan yang lebih pendek, terutama idan juntuk indeks utama yang sedang berjalan.
• Anda memasukkan sebelum Anda menghapus. Ini mungkin memerlukan seluruh daftar untuk dialokasikan kembali dan mengambil O (n) ruang ekstra jika tidak memiliki tempat tambahan secara keseluruhan. Menghapus (atau meletuskan) sebelum memasukkan mengurangi risiko itu dan dengan demikian meningkatkan kemungkinan Anda hanya mengambil O (log n) ruang ekstra.
• Mergesort seharusnya stabil. Milik Anda tidak, seperti dalam kasus seri, gabungan Anda lebih memilih nilai berikutnya dari bagian kanan. Misalnya, Anda berubah [0, 0.0]menjadi [0.0, 0].

Versi yang dimodifikasi:

def inplace_merge_sort(lst, start=0, stop=None):
    """Sort lst[start:stop]."""

    def merge(i, j, stop):
        """Merge lst[i:j] and lst[j:stop]."""
        while i < j < stop:
            if lst[j] < lst[i]:
                lst.insert(i, lst.pop(j))
                j += 1
            i += 1

    if stop is None:
        stop = len(lst)

    middle = (start + stop) // 2
    if middle > start:
        inplace_merge_sort(lst, start, middle)
        inplace_merge_sort(lst, middle, stop)
        merge(start, middle, stop)

Oh, saya mengganti namanya endmenjadi stop, karena itulah yang kebanyakan digunakan Python, misalnya:

>>> help(slice)
Help on class slice in module builtins:

class slice(object)
 |  slice(stop)
 |  slice(start, stop[, step])

>>> help(list.index)
Help on method_descriptor:

index(self, value, start=0, stop=9223372036854775807, /)

>>> help(range)
Help on class range in module builtins:

class range(object)
 |  range(stop) -> range object
 |  range(start, stop[, step]) -> range object
```

Answer 2

Selamat datang di Review Kode!

PEP-8

Python memiliki panduan gaya untuk membantu pengembang menulis kode yang bersih, dapat dipelihara, dan dapat dibaca. Ini disebut sebagai PEP-8 . Beberapa hal yang perlu diperhatikan:

1. Hindari spasi yang tidak relevan dalam situasi berikut:
2. Gunakan 4 spasi per tingkat indentasi.

Ketik petunjuk

Namun PEP lain (PEP-484) untuk memasukkan petunjuk tipe untuk variabel dan parameter fungsi Anda.

Komentar

Kecuali untuk komentar di test driver tentang kasus sudut, semua komentar lain sebenarnya tidak diperlukan. Kode menjelaskan apa yang coba dikatakan oleh komentar tersebut.

Ulangi rentang

Anda memiliki loop dengan range:

for _ in range( (end - start) ):

di mana Anda benar-benar memanfaatkan lst1_start. Mengapa tidak memulai iterasi dari indeks ini sendiri?

Nama

Nama-nama variabel: length_sublist, lst1_start/enddan juga lst2_start/endlebih mudah dibaca (dan masuk akal) sebagai sublist_length, start1/end1, start2/end2. Karena Anda tidak memiliki 2 daftar berbeda di mana pun, lst1/2itu lebih membingungkan.

Menguji

Driver untuk lingkungan pengujian Anda memerlukan pembungkusnya sendiri, yang perlu disertakan oleh rangkaian pengujian. Ini terasa salah, dan harus ditangani oleh test driver itu sendiri. Juga, python menyediakan modul pengujian yangunittest sangat baik ,. Untuk pengemudi:

@inplace_driver_helper
def driver(f_n):
    # rest of your code

cukup.

Answer 3

• Anda mendefinisikan inplace_merge()di dalam definisi inplace_merge_sort(), tetapi tidak menggunakan konteks apa pun inplace_merge_sort(), jadi tidak perlu.

  Jika Anda mendefinisikannya di luar definisi (mungkin dengan garis bawah di awal pengenal untuk memperingatkan klien bahwa ini tidak dimaksudkan untuk digunakan secara langsung), Anda akan mendapatkan tiga keuntungan:

  • Definisi tersebut hanya akan dieksekusi sekali pada impor, dan tidak pada setiap panggilan.
  • Itu bisa diuji secara langsung.
  • The startdan endpengidentifikasi tidak akan menyembunyikan pengenal lainnya dengan nama yang sama, dan risiko membingungkan pembaca tentang apa yang mereka disebut.

• Jika Anda mengganti:

   if( len(lst) == 1 or len(lst) == 0): #catches edge cases
  

  dengan

   if len(lst) <= 1:
  

maka panjangnya tidak perlu dihitung dua kali (yang, sejujurnya, mungkin bukan operasi yang lambat).

• Saya setuju dengan jawaban lain bahwa seharusnya tidak ada nilai balik, tetapi jika ada, Anda harus mengujinya. (Faktanya, saya akan menguji bahwa itu selalu mengembalikan Tidak Ada.)