Algorithme de tri et implémentation en Python

introduction

J'ai résumé quelques algorithmes de tri.

J'ai décrit chaque point, un exemple d'implémentation en Python et chaque mesure de vitesse.

Je l'ai implémenté sans utiliser autant que possible les fonctions intégrées, donc ce n'est pas très rapide, mais je voulais faire quelque chose de plus rapide que sort () et sorted ().

Algorithme de tri à gérer

L'algorithme de tri à gérer est

• Tri des bulles --Sélectionnez le tri --Tri par insertion --Tri par fusion --Tri rapide --Tri de compte

D'autres algorithmes de tri bien connus incluent le tri de tas, le tri de shell et le tri de base, mais cette fois je les ai oubliés. Je veux l'ajouter un jour.

Le tri de tas est assez facile à implémenter avec le module heapq de Python, mais on a l'impression que c'est différent de faire sort () ...

La stabilité signifie que lorsque des données telles que [1-b, 2-a, 1-a, 2-b] sont triées en utilisant des nombres comme clés, l'ordre avant le tri est enregistré, et [1-b, Nous reconnaissons que quelque chose comme 1-a, 2-a, 2-b] est défini comme stable.

Chaque point et implémentation

Tri à bulles

• Comparez et échangez la taille de chaque côté, et faites-le jusqu'à ce qu'il n'y ait pas besoin de changer. --Simple et facile à comprendre.

bubble_sort.py

def bubble_sort(arr):
    change = True
    while change:
        change = False
        for i in range(len(arr) - 1):
            if arr[i] > arr[i + 1]:
                arr[i], arr[i + 1] = arr[i + 1], arr[i]
                change = True
    return arr

Tri sélectif

--Sélectionnez le minimum ou le maximum dans le tableau et déplacez-le vers la fin. --Simple et facile à comprendre.

J'ai l'impression de pouvoir utiliser min () ...

Afin de réduire l'utilisation de la mémoire à $ O (1) $, il est implémenté en le remplaçant au lieu de le mettre dans une nouvelle liste.

sellect_sort.py

def sellect_sort(arr):
    for ind, ele in enumerate(arr):
        min_ind = min(range(ind, len(arr)), key=arr.__getitem__)
        arr[ind], arr[min_ind] = arr[min_ind], ele
    return arr

Insérer un tri

• Dans l'ordre à partir de la gauche, insérez dans la partie appropriée du tableau aligné.
• Lorsque vous recherchez un lieu à insérer, vous pouvez accélérer en utilisant une recherche de 2 minutes.
• Comparé au tri par fusion et au tri rapide, il ne dépend pas de l'état des données.
• Fort contre les tableaux presque triés et les tableaux relativement petits. --Simple et facile à comprendre.

Si vous n'utilisez pas la recherche de 2 minutes

insert_sort.py

def insert_sort(arr):
    for i in range(1, len(arr)):
        j = i - 1
        ele = arr[i]
        while arr[j] > ele and j >= 0:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = ele
    return arr

Lors de l'utilisation de la recherche de 2 minutes,

insert_sort_bin.py

import sys
sys.setrecursionlimit(10 ** 7)

def binary_search(arr, low, hig, ele):
    if low == hig:
        if arr[low] > ele:
            return low
        else:
            return low + 1
    elif low > hig:
        return low
    
    mid = (low + hig) // 2
    if arr[mid] < ele:
        return binary_search(arr, mid + 1, hig, ele)
    elif arr[mid] > ele:
        return binary_search(arr, low, mid - 1, ele)
    else:
        return mid

def insert_sort_bin(arr):
    for i in range(1, len(arr)):
        ele = arr[i]
        ind = binary_search(arr, 0, i - 1, ele)
        arr[:] = arr[:ind] + [ele] + arr[ind:i] + arr[i + 1:]
    return arr

À propos, lors de l'utilisation de bisect, qui est un module de recherche de 2 minutes,

insert_sort_bin_buildin.py

import bisect
def insert_sort_bin_buildin(arr):
    for i in range(1, len(arr)):
        bisect.insort(arr, arr.pop(i), 0, i)
    return arr

Tri par fusion

• Tout d'abord, répétez la division, puis combinez dans l'ordre.
• En conséquence, le fractionnement et la jonction sont effectués de manière récursive.
• Tri en cours de combinaison. ――Parce que les séquences triées sont combinées, imaginez une méthode de combinaison. --Heapq merge peut également être utilisé pour la fusion.
• Si vous pouvez le diviser dans une certaine mesure, vous pouvez l'accélérer en utilisant un autre algorithme de tri. «C'est assez rapide, mais cela utilise beaucoup de mémoire. --Peut être traité en parallèle

merge_sort.py

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    
    mid = len(arr) // 2
    #Faites la séparation ici
    left = arr[:mid]
    right = arr[mid:]
    
    #Fractionner récursivement
    left = merge_sort(left)
    right = merge_sort(right)
    
    #Lorsque le retour est retourné, combinez et passez le suivant combiné
    return merge(left, right)


def merge(left, right):
    merged = []
    l_i, r_i = 0, 0
    
    #Tout ce que vous avez à faire est de regarder par la gauche pour fusionner les tableaux triés.
    while l_i < len(left) and r_i < len(right):
        #ici=La stabilité est maintenue en attachant
        if left[l_i] <= right[r_i]:
            merged.append(left[l_i])
            l_i += 1
        else:
            merged.append(right[r_i])
            r_i += 1
    
    #Si l'une des instructions while ci-dessus devient False, cela se terminera, alors étendez trop
    if l_i < len(left):
        merged.extend(left[l_i:])
    if r_i < len(right):
        merged.extend(right[r_i:])
    return merged

Tri rapide

――Déterminez une valeur de référence et divisez-la en deux séquences, grande et petite selon la valeur de référence.

• Comme méthode de sélection de cette valeur de référence, utilisez le début ou la fin du tableau, la valeur médiane d'environ trois valeurs appropriées, et ainsi de suite.
• Le même traitement est effectué de manière récursive dans les groupes divisés.
• Les performances dépendent de la manière de déterminer la valeur standard.
• Si vous pouvez le diviser dans une certaine mesure, vous pouvez l'accélérer en utilisant un autre algorithme de tri. «C'est assez rapide, mais cela utilise beaucoup de mémoire.
• Pas une sorte stable.

quick_sort.py

def quick_sort(arr):
    left = []
    right = []
    if len(arr) <= 1:
        return arr
    
    #Aléatoire car cela ne dépend pas de l'état des données.choice()Peut être utilisé.
    # ref = random.choice(arr)
    ref = arr[0]
    ref_count = 0
    
    for ele in arr:
        if ele < ref:
            left.append(ele)
        elif ele > ref:
            right.append(ele)
        else:
            ref_count += 1
    left = quick_sort(left)
    right = quick_sort(right)
    return left + [ref] * ref_count + right

Compter le tri

• Comptez le nombre de chaque valeur. --Facile à mettre en œuvre. --Très rapide en fonction de la plage de valeurs.

Le tri par compartiment est un algorithme de tri très similaire au tri par comptage. Le tri par compartiment est comme un algorithme de tri qui crée plusieurs boîtes avec une certaine plage, y met des valeurs, trie chaque boîte, puis les combine.

Le tri par comptage peut également maintenir la stabilité en créant une boîte pour chaque valeur et en l'ajoutant à celle-ci, mais il s'agit de l'implémentation car l'idée est un compartiment plutôt qu'un comptage. Si vous utilisez le module collections.defaultdict, vous pouvez l'implémenter assez facilement et de manière stable.

count_sort.py

def count_sort(arr):
    max_num = max(arr)
    min_num = min(arr)
    count = [0] * (max_num - min_num + 1)
    for ele in arr:
        count[ele - min_num] += 1
 
    return [ele for ele, cnt in enumerate(count, start=min_num) for __ in range(cnt)]

Comparaison de vitesse

Ensemble de données à utiliser

Généré avec numpy.random.

L'ensemble de données créé est

--data1: 100 nombres aléatoires uniformes compris entre 0 et 100 --data2: 10000 nombres aléatoires uniformes dans la plage 0-1000 --data3: 10000 nombres aléatoires uniformes compris entre 0 et 100 --data4: 100 nombres aléatoires de distribution normale standard avec moyenne 10 et écart type 5 --data5: 10000 nombres aléatoires de distribution normale standard dans la plage de la moyenne 100 et de l'écart type 50 --data6: 100 nombres aléatoires uniformes dans la plage 0-100 déjà triés dans l'ordre inverse --data7: déjà trié par 100 nombres aléatoires uniformes d'entiers compris entre 0 et 100, seuls les 10 premiers sont foirés

make_data.py

data_rand_1 = list(randint(0, 10 ** 2, 10 ** 2))
data_rand_2 = list(randint(0, 10 ** 4, 10 ** 4))
data_rand_3 = list(randint(0, 10 ** 2, 10 ** 4))
data_rand_4 = [int(normal(10, 5)) for __ in range(10 ** 2)]
data_rand_5 = [int(normal(10 ** 2, 50)) for __ in range(10 ** 4)]
data_rand_6 = sorted(randint(0, 10 ** 2, 10 ** 2), reverse=True)
data_rand_7 = sorted(randint(0, 10 ** 2, 10 ** 2))
data_rand_7[0: 10] = choice(data_rand_7[0: 10], 10, replace=False)

Mesure de vitesse

Le code ci-dessous a été utilisé pour mesurer 100 fois et la moyenne a été calculée. Je ne pouvais pas bien le mesurer avec la commande timeit du notebook Jupyter.

L'unité est le μs.

Des mesures ont été effectuées pour chaque algorithme afin de réduire au maximum les erreurs. Cela dépend peut-être des spécifications du processeur et de la mémoire, mais si l'implémentation était telle que tous les algorithmes pouvaient être mesurés en même temps à l'aide d'une boucle, les performances chuteraient considérablement.

time.py

datas = [data_rand_1, data_rand_2, data_rand_3,
             data_rand_4, data_rand_5, data_rand_6, data_rand_7]

for ind, data in enumerate(datas):
    print("---- DataSet : {0} ----".format(ind + 1))
    times = []
    for i in range(100):
        start = time.time()
        #Algorithme de tri que vous souhaitez mesurer
        sorted(data)
        elapsed_time = int((time.time() - start) * (10 ** 6))
        times.append(elapsed_time)

    print(sum(times) // 100)

Prise en compte du résultat pour le moment

• Le tri intégré de Python est rapide.
• Le tri par insertion est relativement rapide parmi les tris de bas niveau.
• Cela ne va pas plus vite même si vous recherchez 2 minutes par tri par insertion.
• Le tri par fusion et le tri rapide sont étonnamment lents. Avec des données plus volumineuses, je pense que ce sera beaucoup plus rapide si vous mettez un tri de comptage au milieu du tri rapide. ―― La plupart des algorithmes ne détériorent pas le résultat en fonction de l'état des données, mais seul le tri rapide détériore les performances en fonction de l'état des données.

Recherche d'un algorithme plus rapide que le tri intégré

Pour les plages étroites, le tri par comptage semble être plus rapide que le tri intégré.

Je pense que si nous pouvons mettre en œuvre avec succès le tri par seau, qui est un tri relatif au nombre, nous pouvons construire un algorithme plus rapide.

Pour le moment, combinez le tri rapide et le tri par comptage pour insérer une grande quantité de données.

Les données préparées sont big_data = list (randint (0, 10 ** 3, 10 ** 6)).

quick_sort_with_count.py

def quick_sort_with_count(arr):
    left = []
    right = []
    if len(arr) <= 1:
        return arr
    ref = choice(arr)
    ref_count = 0

    for ele in arr:
        if ele < ref:
            left.append(ele)
        elif ele > ref:
            right.append(ele)
        else:
            ref_count += 1

    if len(left) <= 1000:
        left = count_sort(left)
    else:
        left = quick_sort_with_count(left)

   if len(right) <= 1000:
        right = count_sort(right)
    else:
        right = quick_sort_with_count(right)

    return left + [ref] * ref_count + right

En conclusion

Je n'ai plus de temps pour le moment, alors c'est tout. Si vous avez le temps, prenez un ensemble de données à granularité fine et comparez et validez les tris et dénombrements intégrés de Python.

On dit généralement que le tri par fusion, le tri rapide, etc. sont rapides, mais pour le moment, il semble que ce ne soit pas si rapide car les appels récursifs, etc. prennent du temps en Python.

Si vous connaissez la plage et le type de valeurs, le tri par comptage peut être utile. Wikipédia en japonais n'a même pas d'article, et certains documents anglais sont confondus avec le tri par seau, mais ...

Page de référence

• Wikipedia Sort: Une description complète de l'algorithme de tri.
• Rosetta Code: Une collection d'exemples d'implémentation pour chaque langage d'algorithme. J'ai essayé de le laisser tomber d'ici.
• Résumé de la génération aléatoire par Numpy
• Mesurer et afficher le temps de traitement