Python3 - tri par fusion, efficacité de l'espace O (n)

Oct 19 2020

Toute critique de ma mise en œuvre du tri Merge serait très appréciée! Je l'ai testé en utilisant une fonction de pilote (illustrée ci-dessous), et tout fonctionne. Cependant, cela semble toujours lourd, je suis un débutant donc j'ai vraiment envie d'entendre toutes les critiques, constructives ou non :)

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

Voici la fonction de test

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]

et quand on lance ça,

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

    print('done')

La sortie est «terminée»!

Réponses

17 superbrain Oct 19 2020 at 07:36

La fusion est généralement le temps O (m), où m est le nombre d'éléments impliqués dans la fusion. En raison de vos insertions et suppressions, c'est plutôt O (mn), où n est la longueur de la liste entière. Cela rend votre tri complet O (n ^ 2 log n) au lieu du O habituel de mergesort (n log n).
Vous l'appelez le tri en place, ce qui suggère qu'il ne renvoie rien, mais vous retournez la liste si elle est courte et vous retournez des indices de début / fin sinon. Plutôt incohérent et déroutant. Je le ferais ne rien renvoyer (autre que la valeur par défaut None).
Votre fonction propose de ne trier qu'une partie de la liste, mais vous ne testez pas cela.
Vous utilisez pas mal de noms de variables assez longs. J'utiliserais des plus courts, en particulier iet jpour les principaux indices en cours d'exécution.
Vous insérez avant de supprimer. Cela peut nécessiter la réallocation de la liste entière et prendre de l'espace supplémentaire O (n) s'il n'y a pas de place supplémentaire surutilisée. La suppression (ou l'éclatement) avant l'insertion réduit ce risque et augmente ainsi les chances de ne prendre que O (log n) d'espace supplémentaire.
Mergesort doit être stable. La vôtre n'est pas, comme en cas d'égalité, votre fusion préfère la valeur suivante de la moitié droite. Par exemple, vous vous transformez [0, 0.0]en [0.0, 0].

Une version modifiée:

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, je retitré endà stop, comme c'est ce que Python utilise la plupart du temps, par exemple:

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

9 hjpotter92 Oct 19 2020 at 05:26

Bienvenue dans Code Review!

PEP-8

Python a un guide de style pour aider les développeurs à écrire du code propre, maintenable et lisible. Il est appelé PEP-8 . Quelques points à noter:

Évitez les espaces superflus dans les situations suivantes:
Utilisez 4 espaces par niveau d'indentation.

Indication de type

Encore un autre PEP (PEP-484) pour insérer des indices de type pour vos variables et paramètres de fonction.

commentaires

À l'exception du commentaire du pilote de test sur les cas d'angle, tous les autres commentaires ne sont en fait pas nécessaires. Le code explique ce que les commentaires essaient de dire de toute façon.

Boucle sur la plage

Vous avez une boucle avec range:

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

où vous utilisez réellement lst1_start. Pourquoi ne pas commencer à itérer à partir de cet index lui-même?

Noms

Les noms de variables: length_sublist, lst1_start/endet de même lst2_start/endsont plus lisibles (et sensible) comme sublist_length, start1/end1, start2/end2. Puisque vous n'avez nulle part 2 listes différentes, lst1/2c'est plus déroutant.

Essai

Le pilote de votre environnement de test nécessite son propre wrapper, que la suite de test doit intégrer. Cela semble faux et devrait être géré par le pilote de test lui-même. En outre, python fournit un excellent module de test,unittest . Pour le chauffeur: