Python3 - Sortierung zusammenführen, O (n) Raumeffizienz

Question

Jede Kritik an meiner Implementierung von Merge sort wäre sehr dankbar! Ich habe es mit einer Treiberfunktion (siehe unten) getestet und alles funktioniert. Es fühlt sich jedoch immer noch unhandlich an, ich bin ein Anfänger, also möchte ich wirklich jede Kritik hören, konstruktiv oder nicht :)

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

Hier ist die Testfunktion

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]

und wenn wir das laufen lassen,

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

    print('done')

Die Ausgabe ist 'erledigt'!

Answer 1

• Die Zusammenführung ist normalerweise die O (m) -Zeit, wobei m die Anzahl der an der Zusammenführung beteiligten Elemente ist. Aufgrund Ihrer Einfügungen und Löschungen ist es eher O (mn), wobei n die Länge der gesamten Liste ist. Das macht Ihre gesamte Sortierzeit O (n ^ 2 log n) anstelle der üblichen O (n log n) von Mergesort.
• Sie nennen es Inplace-Sortierung, was darauf hindeutet, dass nichts zurückgegeben wird, aber Sie geben die Liste zurück, wenn sie kurz ist, und Sie geben ansonsten einige Start- / Endindizes zurück. Eher inkonsistent und verwirrend. Ich würde dafür sorgen, dass nichts zurückgegeben wird (außer der Standardeinstellung None).
• Ihre Funktion bietet an, nur einen Teil der Liste zu sortieren, aber das testen Sie nicht.
• Sie verwenden einige ziemlich lange Variablennamen. Ich würde kürzere verwenden, insbesondere iund jfür die wichtigsten laufenden Indizes.
• Sie fügen ein, bevor Sie löschen. Dies kann erfordern, dass die gesamte Liste neu zugewiesen wird und O (n) zusätzlichen Speicherplatz benötigt, wenn kein zusätzlicher Platz insgesamt zugewiesen ist. Das Löschen (oder Poppen) vor dem Einfügen verringert dieses Risiko und erhöht somit die Wahrscheinlichkeit, dass Sie nur O (log n) zusätzlichen Speicherplatz belegen.
• Mergesort sollte stabil sein. Ihre ist nicht, wie im Falle eines Unentschieden, Ihre Zusammenführung bevorzugt den nächsten Wert der rechten Hälfte. Zum Beispiel verwandeln Sie sich [0, 0.0]in [0.0, 0].

Eine modifizierte Version:

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, ich habe umbenannt endin stop, da Python dies meistens verwendet, zum Beispiel:

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

Willkommen bei Code Review!

PEP-8

Python verfügt über einen Styleguide, mit dem Entwickler sauberen, wartbaren und lesbaren Code schreiben können. Es wird als PEP-8 bezeichnet . Einige Punkte zu beachten:

1. Vermeiden Sie in den folgenden Situationen überflüssige Leerzeichen:
2. Verwenden Sie 4 Leerzeichen pro Einrückungsstufe.

Geben Sie einen Hinweis ein

Noch ein PEP (PEP-484) zum Eingeben von Typhinweisen für Ihre Variablen und Funktionsparameter.

Bemerkungen

Mit Ausnahme des Kommentars beim Testen des Treibers zu Eckfällen werden alle anderen Kommentare tatsächlich nicht benötigt. Der Code erklärt, was die Kommentare sowieso zu sagen versuchen.

Schleife über Reichweite

Sie haben eine Schleife mit Reichweite:

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

wo Sie tatsächlich Gebrauch machen lst1_start. Warum nicht von diesem Index selbst aus iterieren?

Namen

Die Variablennamen: length_sublist, lst1_start/endund in ähnlicher Weise lst2_start/endsind lesbarer (und sinnvoll ist ) , wie sublist_length, start1/end1, start2/end2. Da Sie nirgendwo zwei verschiedene Listen haben, lst1/2sind diese verwirrender.

Testen

Der Treiber für Ihre Testumgebung benötigt einen eigenen Wrapper, den die Testsuite enthalten muss. Dies fühlt sich falsch an und sollte vom Testfahrer selbst erledigt werden. Außerdem bietet Python ein hervorragendes Testmodulunittest . Für den Fahrer:

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

reicht.

Answer 3

• Sie definieren inplace_merge()innerhalb der Definition von inplace_merge_sort(), aber es wird kein Kontext von verwendet inplace_merge_sort(), sodass dies nicht erforderlich ist.

  Wenn Sie es außerhalb der Definition definieren (möglicherweise mit einem führenden Unterstrich in der Kennung, um Clients zu warnen, sollte es nicht direkt verwendet werden), erhalten Sie drei Vorteile:

  • Die Definition wird beim Import nur einmal und nicht bei jedem Aufruf ausgeführt.
  • Es könnte direkt getestet werden.
  • Die startund endBezeichner würden andere gleichnamige Bezeichner nicht verbergen und könnten einen Leser verwirren, auf den sie sich beziehen.

• Wenn Sie ersetzt haben:

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

  mit

   if len(lst) <= 1:
  

dann müsste die Länge nicht zweimal berechnet werden (was, um fair zu sein, wahrscheinlich keine langsame Operation ist).

• Ich stimme anderen Antworten zu, dass es keinen Rückgabewert geben sollte, aber wenn dies der Fall ist, sollten Sie ihn testen. (In der Tat würde ich testen, dass es immer None zurückgibt.)