Vous serez ingénieur dans 100 jours ―― Jour 60 ―― Programmation ―― À propos de la structure des données et de l'algorithme de tri

Cliquez ici jusqu'à hier

Structure de données

La structure des données est importante pour l'apprentissage des algorithmes. Puisque l'algorithme est une procédure, j'ai dit quel type de données et comment les manipuler. La structure des données est également un élément important de l'algorithme.

liste

Le type de liste Python est un type de données au format tableau utilisant un index Vous pouvez y accéder dans l'ordre.

Dans le type liste, diverses données peuvent être stockées sous forme d'éléments. Vous pouvez ajouter, modifier, remplacer et supprimer des éléments.

#Définition de liste
l = [1,2,3,4,5]
print(l)

#Référence d'élément
print(l[0])

#Changer les éléments
l[1] = 8
print(l)

#Ajouter un élément
l.append(6)
print(l)

#Supprimer l'élément
l.pop(3)
print(l)

#Insérer un élément
l.insert(4,9)
print(l)

#Swap éléments
l[0], l[3] = l[3], l[0]
print(l)

[1, 2, 3, 4, 5] 1 [1, 8, 3, 4, 5] [1, 8, 3, 4, 5, 6] [1, 8, 3, 5, 6] [1, 8, 3, 5, 9, 6] [5, 8, 3, 1, 9, 6]

Piles et files d'attente

La «pile» et la «file d'attente» sont également l'un des moyens de gérer les données.

empiler ・ Les données peuvent être ajoutées depuis le début de la colonne, et les données peuvent être récupérées depuis le début de la colonne. ・ LIFO dernier entré, premier sorti (dernier entré, premier sorti) -Passer des données dans la pile s'appelle «push», et les retirer s'appelle «pop».

queue -Ajouter des données à partir de la fin de la colonne, récupérer les données du début de la colonne ・ Premier entré, premier sorti (méthode Tokoroten) FIFO (premier entré, premier sorti) -Passer des données dans une file d'attente est appelé ʻenqueue, et les récupérer est appelé dequeue`.

Référence: wikipedia

En Python, il peut être réalisé par type de liste ou ç.

empiler

stack = []

#pousser
stack.append(1)
stack.append(2)
stack.append(3)
print(stack)

#pop
stack.pop()
print(stack)
stack.pop()
print(stack)

[1, 2, 3] [1, 2] [1]

queue

from collections import deque

#Définition de la file d'attente
queue = deque(["A","B","C"])
print(queue)

#Encue
queue.append("D")
print(queue)

#Decue
queue.popleft()
print(queue)

deque(['A', 'B', 'C']) deque(['A', 'B', 'C', 'D']) deque(['A', 'B', 'C'])

Tas

Qu'est-ce qu'un tas? Les éléments enfants sont toujours plus grands ou égaux (ou toujours plus petits ou égaux) que les éléments parents C'est une donnée arborescente avec la contrainte.

Lorsque nous disons simplement «tas», nous nous référons souvent au «demi-tas» en utilisant un arbre dichotomisé.

Référence: wikipedia

Le tas peut être implémenté en Python avec la bibliothèque heapq. Vous pouvez récupérer rapidement la valeur minimale (ou maximale) du tas.

import heapq

#Créer une liste
heap = [1, 6, 8, 0, -1]
print(heap)

#Liste existante de tas(valeur minimum)
heapq.heapify(heap)
print(heap)

#Ajouter un élément
heapq.heappush(heap, 10)
print(heap)

#Supprimer la valeur minimale
print(heapq.heappop(heap))
print(heap)

max_heap = [3,7,5,9,-2]
print(max_heap)
#Créer un tas avec une valeur maximale
heapq._heapify_max(max_heap) 
print(max_heap)

#Supprimer la valeur maximale
print(heapq._heappop_max(max_heap))
print(max_heap)

[1, 6, 8, 0, -1] [-1, 0, 8, 1, 6] [-1, 0, 8, 1, 6, 10] -1 [0, 1, 8, 10, 6] [3, 7, 5, 9, -2] [9, 7, 5, 3, -2] 9 [7, 3, 5, -2]

À propos de l'algorithme de tri

L'algorithme de tri est l'algorithme de tri. Il existe de nombreuses variantes à trier simplement.

Le tri "stable" est stable lorsqu'il y a plusieurs enregistrements avec la même clé dans les données. Après le tri, l'ordre des enregistrements avant le tri est conservé.

Tri pour que la relation de position avant le tri soit rompue par le tri C'est ce qu'on appelle un tri «instable» instable.

Il est souhaitable d'adopter un algorithme de tri qui termine le tri rapidement et qui soit stable.

Dans l'algorithme de tri, la quantité de calcul est également un guide. La quantité de calcul de l'algorithme de tri qui est généralement dit est la suivante.

algorithme	Stabilité	Temps moyen	Le pire moment	Meilleur temps	Pire espace
Tri à bulles	Stable	\mathcal{O}(n^2)	\mathcal{O}(n^2)	\mathcal{O}(n)	\mathcal{O}(1)
Tri sélectif	instable	\mathcal{O}(n^2)	\mathcal{O}(n^2)	\mathcal{O}(n)	\mathcal{O}(n)
Insérer un tri	Stable	\mathcal{O}(n^2)	\mathcal{O}(n^2)	\mathcal{O}(n)	\mathcal{O}(n)
Tri de tas	instable	\mathcal{O}(n\log n)	\mathcal{O}(n\log n)	\mathcal{O}(n\log n)	\mathcal{O}(1)
Tri par fusion	Stable	\mathcal{O}(n\log n)	\mathcal{O}(n\log n)	\mathcal{O}(n\log n)	\mathcal{O}(n)
Tri rapide	instable	\mathcal{O}(n\log n)	\mathcal{O}(n^2)	\mathcal{O}(n)	\mathcal{O}(n)
tri python(Tim sort)	Stable	\mathcal{O}(n\log n)	\mathcal{O}(n\log n)	\mathcal{O}(n)	\mathcal{O}(n)

Examinons maintenant divers algorithmes de tri. J'ai également inclus un exemple d'implémentation, mais je pense qu'il existe une meilleure façon de l'écrire.

Tri à bulles

Bubble Sort compare les valeurs de deux éléments adjacents dans une liste Il s'agit d'un algorithme d'alignement qui échange selon les conditions.

Triez la liste par ordre décroissant (ordre décroissant) ou croissant (ordre croissant).

#Tri à bulles
def bubble_sort(data):
    for i in range(len(data)):
        for j in range(len(data) - i - 1):
            if data[j] > data[j + 1]:
                data[j], data[j + 1] = data[j + 1], data[j]
    return data

Sélectionnez le tri

Le tri sélectif recherche l'élément avec la valeur minimale (maximale) du tableau C'est un algorithme qui s'aligne en l'échangeant avec le premier élément du tableau.

#Tri sélectif
def select_sort(data):
    for i in range(len(data)):
        min = i
        for j in range(i + 1, len(data)):
            if data[min] > data[j]:
                min = j
        data[i], data[min] = data[min], data[i]
    return data

Insérer un tri

ʻInsert Sort` consiste à insérer un nouvel élément à la position appropriée pour la partie alignée de la liste. Ceci est un algorithme d'alignement.

#Insérer un tri
def insert_sort(data):
    for i in range(1, len(data)):
        temp = data[i]
        j = i - 1
        while (j >= 0) and (data[j] > temp):
            data[j + 1] = data[j]
            j -= 1
        data[j + 1] = temp
    return data

Tri de tas

Heap sort est un algorithme de tri qui trie une liste en utilisant un arbre de tas dichotomisé.

Prend des éléments de la liste non alignée et les ajoute au tas dans l'ordre. Répétez jusqu'à ce que vous ajoutiez tous les éléments (prenez l'itinéraire et ajoutez-le à la liste alignée)

#Tri de tas
def heap_sort(data):
    for i in range(len(data)):
        j = i
        while (j > 0) and (data[(j - 1) // 2] < data[j]):
            data[(j - 1) // 2], data[j] = data[j], data[(j - 1) // 2]
            j = (j - 1) // 2

    for i in range(len(data), 0, -1):
        data[i - 1], data[0] = data[0], data[i - 1]
        j = 0
        while ((2 * j + 1 < i - 1) and (data[j] < data[2 * j + 1]))\
            or ((2 * j + 2 < i - 1) and (data[j] < data[2 * j + 2])):
            if (2 * j + 2 == i - 1) or (data[2 * j + 1] > data[2 * j + 2]):
                data[j], data[2 * j + 1] = data[2 * j + 1], data[j]
                j = 2 * j + 1
            else:
                data[j], data[2 * j + 2] = data[2 * j + 2], data[j]
                j = 2 * j + 2
    return data

En python, en utilisant la bibliothèque heapq qui réalise la file d'attente du tas Vous pouvez également facilement écrire un tri de tas.

import heapq

#Tri de tas à l'aide de heapq
def heap_sort2(data):
    h = data.copy()
    heapq.heapify(h)
    return [heapq.heappop(h) for _ in range(len(h))]

Tri par fusion

Merge sort divise récursivement le tableau que vous voulez trier et fusionne à nouveau` C'est un algorithme de tri qui tente de réaliser le tri.

#Tri par fusion
def merge_sort(data):
    if len(data) <= 1:
        return data
    m = len(data) // 2
    l = merge_sort(data[:m])
    r = merge_sort(data[m:])
    return merge(l , r)

def merge(left, right):
    res , i , j = [], 0, 0
    while (i < len(left)) and (j < len(right)):
        if left[i] <= right[j]:
            res.append(left[i])
            i += 1
        else:
            res.append(right[j])
            j += 1
    if i < len(left):
        res.extend(left[i:])
    if j < len(right):
        res.extend(right[j:])
    return res

Tri rapide

La caractéristique du «tri rapide» est que le nombre de comparaisons et d'échanges de données est très faible. Vous pouvez trier efficacement les données dispersées de manière aléatoire, C'est un algorithme qui n'est pas stable.

def quick_sort(data):
    def quick(list, left, right):
        pl = left
        pr = right
        y = list[(pl + pr) // 2]
        while True:
            while list[pl] < y: pl += 1
            while list[pr] > y: pr -= 1
            if pl <= pr:
                list[pl], list[pr] = list[pr], list[pl]
                pl += 1
                pr -= 1
            if pl > pr:
                break
        if left < pr: quick(list, left, pr)
        if pl < right: quick(list, pl, right)
        return data
    quick(data, 0, len(data) - 1)
    return data

Tri standard Python

Le tri standard de Python est (probablement) Timsort.

«Timsort» est un hybride stable dérivé de «tri par fusion» et «tri d'insertion» L'algorithme de tri est conçu pour bien fonctionner avec différents types de données.

def python_sort(data):
    data.sort()
    return data

Comparez le temps d'exécution de l'algorithme de tri

Mesurons le temps d'exécution de l'algorithme de tri ci-dessus. Vous pouvez facilement mesurer avec le code suivant.

Trie 10000 nombres. Avec jupyter notebook, vous pouvez utiliser% time pour mesurer le temps.

import numpy as np
import sys
sys.setrecursionlimit(20000)

data = np.arange(10000)
np.random.shuffle(data)
data = list(data)

print('bubble_sort')
%time l = bubble_sort(data)
print('select_sort')
%time l = select_sort(data)
print('insert_sort')
%time l = insert_sort(data)
print('heap_sort')
%time l = heap_sort(data)
print('heap_sort2')
%time l = heap_sort2(data)
print('merge_sort')
%time l = merge_sort(data)
print('quick_sort')
%time l = quick_sort(data)
print('python_sort')
%time l = python_sort(data)

bubble_sort CPU times: user 18 µs, sys: 0 ns, total: 18 µs Wall time: 20 µs select_sort CPU times: user 18 µs, sys: 1 µs, total: 19 µs Wall time: 21 µs insert_sort CPU times: user 7 µs, sys: 0 ns, total: 7 µs Wall time: 10 µs heap_sort CPU times: user 38 µs, sys: 1 µs, total: 39 µs Wall time: 40.1 µs heap_sort2 CPU times: user 11 µs, sys: 0 ns, total: 11 µs Wall time: 12.9 µs merge_sort CPU times: user 31 µs, sys: 1e+03 ns, total: 32 µs Wall time: 33.1 µs quick_sort CPU times: user 13 µs, sys: 1 µs, total: 14 µs Wall time: 14.8 µs python_sort CPU times: user 4 µs, sys: 0 ns, total: 4 µs Wall time: 6.2 µs

À propos, le temps le plus court est le tri standard de Python.

Je pense que cela changera considérablement en fonction de la façon dont vous le mettez en œuvre. Je pense qu'il est assez difficile d'atteindre une vitesse qui dépasse le tri standard. Normalement, vous n'avez pas besoin d'écrire votre propre programme pour le tri.

Résumé

Le tri Python est si puissant que vous ne vous en souciez généralement pas. Il y a peu de problèmes de tri.

Comment se déroule le tri? Si vous comparez en quoi chaque méthode est différente Vous comprendrez la profondeur de l'algorithme.

40 jours avant de devenir ingénieur

Informations sur l'auteur

HP d'Otsu py: http://www.otupy.net/

Youtube： https://www.youtube.com/channel/UCaT7xpeq8n1G_HcJKKSOXMw

Twitter： https://twitter.com/otupython