Python3-マージソート、O（n）スペース効率

Question

マージソートの私の実装に対する批評は大歓迎です！ドライバー関数（以下に表示）を使用してテストしましたが、すべてが機能します。しかし、それでも扱いにくいと感じています。私は初心者なので、建設的かどうかにかかわらず、批判を本当に聞きたいです:)

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

これがテスト機能です

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]

これを実行すると、

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

    print('done')

出力は「完了」です！

Answer 1

• マージは通常O（m）時間です。ここで、mはマージに関係する要素の数です。挿入と削除があるため、O（mn）になります。ここで、nはリスト全体の長さです。これにより、マージソートの通常のO（n log n）ではなく、ソート全体がO（n ^ 2 log n）時間になります。
• これをインプレースソートと呼びます。これは、何も返さないことを示していますが、リストが短い場合はリストを返し、それ以外の場合は開始/終了インデックスを返します。むしろ一貫性がなく、混乱を招きます。私はそれが何も返さないようにします（デフォルト以外None）。
• 関数はリストの一部のみをソートすることを提案しますが、それをテストしません。
• かなり長い変数名を使用します。私は特に、短いものを使用したいiとjメインランニングインデックスのために。
• 削除する前に挿入します。これには、リスト全体を再割り当てする必要があり、余分なスポットが過剰に割り当てられていない場合は、O（n）個の余分なスペースが必要になる場合があります。挿入する前に削除（またはポップ）すると、そのリスクが軽減されるため、O（log n）の余分なスペースのみを使用する可能性が高くなります。
• マージソートは安定している必要があります。同点の場合のように、あなたのマージは右半分の次の値を優先しません。たとえば、あなたはターン[0, 0.0]へ[0.0, 0]。

変更されたバージョン：

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)

ああ、私は名前endをに変更しましたstop。これは、Pythonが主に使用するものです。たとえば、次のようになります。

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

コードレビューへようこそ！

PEP-8

Pythonには、開発者がクリーンで保守可能で読みやすいコードを作成するのに役立つスタイルガイドがあります。これはPEP-8と呼ばれます。注意点：

1. 次の状況では、余分な空白を避けてください。
2. インデントレベルごとに4つのスペースを使用します。

タイプヒント

変数と関数パラメーターの型ヒントを入力するためのさらに別のPEP（PEP-484）。

コメント

コーナーケースに関するテストドライバーのコメントを除いて、他のすべてのコメントは実際には必要ありません。コードは、コメントがとにかく何を言おうとしているのかを説明しています。

範囲をループする

範囲のあるループがあります。

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

実際に利用する場所lst1_start。このインデックス自体から反復を開始してみませんか？

名前

変数名は：length_sublist、lst1_start/end同様にlst2_start/end、より読みやすい（かつ賢明な）されていますsublist_length、start1/end1、start2/end2。どこにlst1/2も2つの異なるリストがないので、もっと混乱します。

テスト

テスト環境のドライバーには、テストスイートに組み込む必要のある独自のラッパーが必要です。これは間違っていると感じ、テストドライバー自身が処理する必要があります。また、pythonは優れたテストモジュールをunittest提供します。ドライバーの場合：

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

十分です。

Answer 3

• の定義inplace_merge()内で定義inplace_merge_sort()しますがinplace_merge_sort()、のコンテキストを使用しないため、必要ありません。

  定義外で定義した場合（おそらく、直接使用することを意図していないことをクライアントに警告するために識別子の先頭にアンダースコアを付けて）、次の3つの利点があります。

  • 定義はインポート時に1回だけ実行され、すべての呼び出しで実行されるわけではありません。
  • 直接テストすることができます。
  • startそしてend、識別子と同じ名前の他の識別子を隠し、そしてリスクは、彼らが言及かについて、読者を混乱されません。

• 交換した場合：

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

  と

   if len(lst) <= 1:
  

その場合、長さを2回計算する必要はありません（公平を期すために、これはおそらく遅い操作ではありません）。

• 戻り値があってはならないという他の回答にも同意しますが、もしあれば、それをテストする必要があります。（実際、常にNoneを返すことをテストします。）