Get best of the week

Tri en douceur


Nous continuons à nous immerger dans une variété de tas.

Aujourd'hui, nous analyserons une méthode de commande élégante qui utilise des tas spéciaux basés sur les chiffres de Leonardo.

Beaucoup ont entendu parler de ce tri, mais peu de gens savent exactement comment cela fonctionne. Aujourd'hui, nous verrons qu'il n'y a rien de compliqué. La méthode a été inventée par le légendaire Edsger Dijkstra. En plus des nombreuses réalisations les plus brillantes de la théorie des algorithmes, il est également l'auteur d'une telle déclaration pleine d'esprit: «Les étudiants qui ont étudié le Basic auparavant, il est presque impossible d'enseigner une bonne programmation. En tant que programmeurs potentiels, ils ont subi une dégradation mentale irréversible. » J'espère que ce n'est pas un blasphème que l'animation de l'article ait été créée en utilisant VBA :-)







Logiciel EDISON - développement web
EDISON.

, Android iOS.

! ;-)

Le tri en tas est en soi très bon, car sa complexité temporelle est O ( n log n ) quelles que soient les données. Afin de ne pas représenter un tableau, la complexité du heapsort ne se dégrade jamais en O ( n 2 ) , ce qui peut se produire, par exemple, avec un tri rapide. Le revers de la médaille est que le tri par tas binaire ne peut pas être accéléré, la complexité O ( n ) ne peut pas non plus être attendue (mais le même tri rapide, dans certaines conditions, peut atteindre de tels indicateurs).

En général, il y avait une question à l'ordre du jour: est-il possible de concevoir de telle sorte que la complexité temporelle du tri par tas, d'une part, ne soit pas inférieure àO ( n log n ) , mais dans un scénario favorable (en particulier, si un tableau presque trié est traité) augmenté à O ( n ) ?

Ce problème a été personnellement abordé par Edsger Dijkstra lui-même, qui a découvert que oui, c'est possible.

Il est supposé que ceux qui lisent cet article comprennent comment fonctionne le tri par tas en général, ils savent ce qu'est l'arbre de tri et pourquoi un tri est nécessaire. Si quelqu'un a des lacunes dans ces connaissances, avant de continuer la lecture, je vous recommande de lire l'article précédent .

Quel est le problème avec un tas binaire


Voyons comment heapsort trie un tableau presque ordonné et voyons pourquoi cet algorithme ne traite pas ces données entrantes plus rapidement.


Cliquez sur l'animation pour aller à l'article "Tri par une n-pyramide".

La première chose qui attire votre attention est que lors du tamisage, les maxima sont constamment poussés à la racine du tas, ce qui correspond au premier élément du tableau. Si le tableau d'entrée est presque ordonné, alors pour l'algorithme, cela n'ajoutera qu'un peu de travail. Les éléments plus petits descendent toujours en premier dans l'arbre, c'est-à-dire rapprochez-vous de la fin du tableau, pas de son début.

Le deuxième facteur de ralentissement, qui n'est pas si évident, est que le tas binaire standard lui-même est toujours un arbre équilibré. Dans le cas de données initialement ordonnées, cela joue un rôle négatif. S'il y a des données aléatoires dans le tableau d'origine, alors elles sont réparties uniformément dans un arbre équilibré, et le tri multiple passe par toutes les branches environ le même nombre de fois. Pour les données presque ordonnées, un arbre déséquilibré est plus préférable - dans ce cas, les données sur la partie du tableau qui correspond à des branches plus longues de l'arbre seront traitées moins souvent que les autres.

Numéros de Leonardo


Pour résoudre ces deux problèmes, Dijkstra a proposé d'utiliser des tas binaires spéciaux basés sur les nombres de Leonardo.

Les chiffres de Leonardo sont presque comme les chiffres de Fibonacci, mais en mieux.
Une série de nombres de Leonardo est donnée récursivement:

L 0 = 1
L 1 = 1
L n = L n - 1 + L n - 2 + 1

Les 20 premiers nombres de Leonardo:
1, 1, 3, 5, 9, 15, 25, 41, 67 , 109, 177, 287, 465, 753, 1219, 1973, 3193, 5167, 8361, 13529

Absolument tout entier peut être représenté comme la somme des nombres Leonardo ayant des numéros de série différents.

Ceci est très utile dans notre cas. Tableau de nles éléments ne peuvent pas toujours être représentés comme un seul tas de Leonardo (si n n'est pas un nombre de Leonardo). Mais alors, tout tableau peut toujours être divisé en plusieurs sous-réseaux qui correspondront à différents nombres de Leonardo, c'est-à-dire être des tas d'ordre différent.

Voici un exemple d'un tableau du 21e élément, composé de trois tas de Leonard. Dans chacun des tas, le nombre de nœuds correspond à n'importe quel nombre de Leonardo.


Points importants à savoir:

  1. Chaque pile Leonardov est un arbre binaire déséquilibré.
  2. La racine de chaque segment est le dernier (et non le premier, comme dans un segment binaire normal) du sous-tableau correspondant.
  3. Tout nœud avec tous ses descendants est également un tas Leonard d'un ordre plus petit.

Construire et démonter des tas


Dans la formule de récurrence des nombres de Leonardo,

L n = L n - 1 + L n - 2 + 1 est

très satisfait de l'unité à la fin.

Et c'est pourquoi. Supposons que nous ayons deux sous-réseaux adjacents dans le tableau qui correspondent à des tas construits sur deux nombres Leonardo adjacents. En utilisant l'élément immédiatement après ces sous-réseaux, ces sous-réseaux peuvent être combinés en un tas commun, qui correspond au numéro de Leonard suivant.



En parcourant les éléments du tableau, nous construisons un tas de tas de Leonard. Si vous utilisez l'élément, vous pouvez combiner les deux tas précédents (cela est possible si et seulement si les deux tas précédents correspondent à deux nombres Leonardo consécutifs), alors combinez. Si la combinaison n'est pas possible (les deux tas précédents ne correspondent pas à deux nombres Leonardo consécutifs), alors l'élément courant forme simplement un nouveau tas d'un élément correspondant au premier (ou second, si le premier est utilisé avant) nombre Leonardo.

À la deuxième étape de l'algorithme, le processus inverse se produit - nous analysons les tas. Si nous supprimons la racine dans le tas, nous obtenons alors deux tas plus petits correspondant aux deux nombres de Leonardo précédents. Cela peut être fait parce que:

L n - 1 = L n - 1+ L n - 2

Dans les nombres de Fibonacci il n'y a pas une telle unité utile, donc nous n'utilisons pas le tas de Fibonacci.

Tri en douceur :: Smoothsort


L'algorithme final:

  • I. Créez un tas de tas de Leonard à partir du tableau, chacun étant un arbre de tri.
    • I.1. Itérer sur les éléments du tableau de gauche à droite.
    • II.1. Nous vérifions si en utilisant l'élément courant, il est possible de combiner les deux tas les plus à gauche dans le tas existant de tas de Leonard:
      • II.1.a. Si oui, alors nous combinons les deux tas les plus à gauche en un seul, l'élément courant devient la racine de ce tas, nous faisons un tri pour le tas combiné.
      • II.1.b. Si ce n'est pas le cas, ajoutez l'élément actuel en tant que nouveau tas (constitué d'un nœud jusqu'à présent) au tas existant de tas Leonard.
  • II. , :
    • II.1. . , .
    • II.2. ( ) ( ).
    • II.3. , . .
    • II.4. ( ), .
    • II.5. Après avoir déplacé l'élément maximal jusqu'à la fin, la partie triée du tableau a augmenté et la partie non triée a diminué. Répétez les étapes II.1 à II.4 pour la partie non triée restante de la baie.



Exemple d'implémentation de Python


import random

def smoothsort(lst):

    #    
    leo_nums = leonardo_numbers(len(lst))


    #       
    heap = []

    #   
    #       
    #       
    for i in range(len(lst)):
        if len(heap) >= 2 and heap[-2] == heap[-1] + 1:
            heap.pop()
            heap[-1] += 1
        else:
            if len(heap) >= 1 and heap[-1] == 1:
                heap.append(0)
            else:
                heap.append(1)
        restore_heap(lst, i, heap, leo_nums)

    #  
    for i in reversed(range(len(lst))):
        if heap[-1] < 2:
            heap.pop()
        else:
            k = heap.pop()
            t_r, k_r, t_l, k_l = get_child_trees(i, k, leo_nums)
            heap.append(k_l)
            restore_heap(lst, t_l, heap, leo_nums)
            heap.append(k_r)
            restore_heap(lst, t_r, heap, leo_nums)

#   ,     
def leonardo_numbers(hi):

    a, b = 1, 1
    numbers = []
    while a <= hi:
        numbers.append(a)
        a, b = b, a + b + 1
    return numbers

#        
def restore_heap(lst, i, heap, leo_nums):
    
    #      
    
    current = len(heap) - 1
    k = heap[current]

    while current > 0:
        j = i - leo_nums[k]
        if (lst[j] > lst[i] and
            (k < 2 or lst[j] > lst[i-1] and lst[j] > lst[i-2])):
            lst[i], lst[j] = lst[j], lst[i]
            i = j
            current -= 1
            k = heap[current]
        else:
            break

    # 
    
    while k >= 2:
        t_r, k_r, t_l, k_l = get_child_trees(i, k, leo_nums)
        if lst[i] < lst[t_r] or lst[i] < lst[t_l]:
            if lst[t_r] > lst[t_l]:
                lst[i], lst[t_r] = lst[t_r], lst[i]
                i, k = t_r, k_r
            else:
                lst[i], lst[t_l] = lst[t_l], lst[i]
                i, k = t_l, k_l
        else:
            break

#         ,
#     
def get_child_trees(i, k, leo_nums):

    t_r, k_r = i - 1, k - 2
    t_l, k_l = t_r - leo_nums[k_r], k - 1
    return t_r, k_r, t_l, k_l

#  
def main(n):
    lst = list(range(n))
    random.shuffle(lst)
    print(lst)
    smoothsort(lst)
    print(lst)

Complexité temporelle


Si nous prenons un tableau presque ordonné en entrée, la visualisation montre pourquoi un tel tableau est traité beaucoup plus rapidement.



Les économies se produisent uniquement grâce au tamisage. Dans des données presque ordonnées, le tamisage coule peu profond dans l'arbre, y compris après que les tas ont été progressivement dissous au cours de la deuxième étape. Dans les données initialement aléatoires, le criblage est plus cher, car il tombe souvent dans son tas jusqu'au dernier niveau.

Estimons la complexité totale du temps.

À la première étape, nous itérons sur n éléments, en l'ajoutant aux tas déjà existants à gauche. L'ajout au tas lui-même est ignoré dans O (1), mais pour le tas, vous devez effectuer un tri. Dans les données ordonnées, un tamisage superficiel coûte souvent O (1) pour un élément ajouté au tas. Dans les données non ordonnées, le criblage pour chaque ajout est évalué en O (log n ), car en raison du caractère aléatoire, le tamisage doit passer souvent par les niveaux de l'arbre jusqu'au fond.

Par conséquent, à la première étape, la meilleure complexité temporelle est:
pour des données presque ordonnées - O ( n ),
pour des données aléatoires - O ( n log n ).

Pour la deuxième étape, la situation est similaire. Lors de l'échange du maximum suivant, vous devez à nouveau tamiser le tas à la racine duquel il se trouvait. Et les métriques de tri pour les données ordonnées et désordonnées seront différentes.

Au deuxième stade, la meilleure complexité temporelle est la même qu'au premier:
pour des données presque ordonnées - O ( n ),
pour des données aléatoires - O ( n log n ).

Ajout de la complexité temporelle pour les première et deuxième étapes:
pour les données presque ordonnées - O (2 n ) = O ( n ),
pour les données aléatoires - O (2 n log n ) = O ( n log n ).

En général, la complexité temporelle la plus mauvaise et moyenne pour un tri en douceur est O ( n log n ).
Dijkstra dans ses calculs (dont je ne vous ennuierai pas) a prouvé que la meilleure complexité tend vers O ( n ) en douceur que les données entrantes les plus ordonnées. D'où le nom - un tri en douceur.

Complexité de mémoire supplémentaire


Pour décomposer les données en un tas de tas de Leonard, il vous suffit de vous rappeler exactement quels numéros Leonardo sont impliqués à chaque étape. Connaissant ces nombres, les tas eux-mêmes sont alignés algorithmiquement. Cette série de nombres croît très rapidement, donc même pour les grands tableaux, vous aurez besoin d'un très petit ensemble de nombres Leonard.

Tri par tas binomial :: Tri par tas binomial


Il y a une structure arborescente, très similaire à celle que nous avons triée - un tas binomial . Il s'agit également d'un tas de tas de tailles différentes, dans chacun desquels le nombre de nœuds est une puissance de deux. Tout tableau de n'importe quel nombre d'éléments peut être développé dans ce tas, car tout nombre naturel est décomposé en la somme de deux degrés différents.

En principe, vous pouvez effectuer un tri en douceur basé sur des binômes:



Cela fonctionnera-t-il plus rapidement? À peine. Le tas binomial n'est pas binaire, et dans le dernier article, nous avons découvert que l'augmentation du nombre de descendants n'accélère pas, mais ralentit l'écran . De plus, vous pouvez remarquer que le tas binomial a des branches plus longues, c'est pourquoi les régions ordonnées voisines de la matrice seront légèrement plus lentes à se connecter les unes aux autres.

On ne sait pas si le tas binomial de Dijkstra était généralement considéré comme une base possible pour son algorithme. Quoi qu'il en soit, le tas Leonardov est probablement plus optimal.

Remorque de la série suivante


Cependant, même si une pile binomiale n'est pas la meilleure option pour un tri en douceur, vous ne devez pas la jeter complètement.

Si l'arbre binomial est légèrement modifié et que des idées complètement différentes (très audacieuses) sont utilisées pour le contourner, alors nous obtenons un algorithme original et efficace qui a ses propres avantages. De quoi allons-nous parler la prochaine fois?


Cliquez sur l'animation pour accéder à l'article avec le prochain tri par tas.

Références


Le nombre de Leonardo lisse / lisse , tas binomial / tas binomial



Articles de série:



Le tri fluide d'aujourd'hui a été ajouté à l'application AlgoLab. Ainsi qu'un bonus - et le tri avec une pile binomiale. Alors, qui veut conduire personnellement les données sur les tas de tas - mettez à jour le fichier Excel avec des macros.

More articles:


All Articles