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

Vous deviendrez ingénieur dans 100 jours - Jour 59 - Programmation - À propos des algorithmes

Vous deviendrez ingénieur dans 100 jours --- Jour 53 --Git --À propos de Git

Vous deviendrez ingénieur dans 100 jours --Jour 42 --Cloud --À propos des services cloud

Vous deviendrez ingénieur dans 100 jours - Jour 36 --Base de données --À propos de la base de données

Vous deviendrez ingénieur dans 100 jours-24 jours-Python-Bases du langage Python 1

Vous deviendrez ingénieur dans 100 jours --Jour 18 --Javascript --Les bases de JavaScript 1

Vous deviendrez ingénieur dans 100 jours - Jour 14 --CSS --CSS Basics 1

Vous deviendrez ingénieur dans 100 jours - Jour 6 --HTML - Bases du HTML 1

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

Recommended Posts

Vous serez ingénieur dans 100 jours ―― Jour 60 ―― Programmation ―― À propos de la structure des données et de l'algorithme de tri
Vous serez ingénieur dans 100 jours ――Jour 71 ――Programmation ――À propos du scraping 2
Vous serez ingénieur dans 100 jours ――Jour 61 ――Programmation ――A propos de l'exploration
Vous serez ingénieur dans 100 jours ――Jour 74 ――Programmation ――À propos du scraping 5
Vous serez ingénieur dans 100 jours ――Jour 73 ――Programmation ――À propos du scraping 4
Vous serez ingénieur dans 100 jours ――Jour 75 ――Programmation ――À propos du scraping 6
Vous deviendrez ingénieur dans 100 jours --Jour 68 --Programmation --A propos de TF-IDF
Vous serez ingénieur dans 100 jours ――Jour 70 ――Programmation ――À propos du grattage
Vous serez ingénieur dans 100 jours ――Jour 81 ――Programmation ――À propos de l'apprentissage automatique 6
Vous serez ingénieur dans 100 jours ――Jour 82 ――Programmation ――À propos de l'apprentissage automatique 7
Vous serez ingénieur dans 100 jours ――Jour 79 ――Programmation ――À propos de l'apprentissage automatique 4
Vous serez ingénieur dans 100 jours ――Jour 76 ――Programmation ――À propos de l'apprentissage automatique
Vous serez ingénieur dans 100 jours ―― Jour 80 ―― Programmation ―― À propos de l'apprentissage automatique 5
Vous serez ingénieur dans 100 jours ――Jour 78 ――Programmation ――À propos de l'apprentissage automatique 3
Vous serez ingénieur dans 100 jours ――Jour 84 ――Programmation ――À propos de l'apprentissage automatique 9
Vous serez ingénieur dans 100 jours ――Jour 83 ――Programmation ――À propos de l'apprentissage automatique 8
Vous serez ingénieur dans 100 jours ――Jour 77 ――Programmation ――À propos de l'apprentissage automatique 2
Vous serez ingénieur dans 100 jours ――Jour 85 ――Programmation ――À propos de l'apprentissage automatique 10
Vous serez ingénieur dans 100 jours ――Jour 63 ――Programmation ――À propos de la probabilité 1
Vous serez ingénieur dans 100 jours ――Jour 65 ――Programmation ――A propos de la probabilité 3
Vous serez ingénieur dans 100 jours ――Jour 64 ――Programmation ――À propos de la probabilité 2
Vous serez ingénieur dans 100 jours --Jour 86 --Base de données -
Vous serez ingénieur dans 100 jours - Jour 27 - Python - Exercice Python 1
Vous serez ingénieur dans 100 jours - Jour 34 - Python - Exercice Python 3
Vous serez ingénieur dans 100 jours - Jour 31 - Python - Python Exercice 2
Vous devenez ingénieur en 100 jours ――Jour 67 ――Programmation ――A propos de l'analyse morphologique
Vous devenez ingénieur en 100 jours ――Jour 66 ――Programmation ――À propos du traitement du langage naturel
Vous serez ingénieur dans 100 jours ――Jour 24 ―― Python ―― Bases du langage Python 1
Vous serez ingénieur dans 100 jours ――Jour 30 ―― Python ―― Bases du langage Python 6
Vous serez ingénieur dans 100 jours ――Jour 25 ―― Python ―― Bases du langage Python 2
Vous serez ingénieur dans 100 jours - Jour 29 - Python - Bases du langage Python 5
Vous serez ingénieur dans 100 jours --Jour 26 --Python --Basiques du langage Python 3
Vous serez ingénieur dans 100 jours --Jour 32 --Python --Basiques du langage Python 7
Vous serez ingénieur dans 100 jours --Jour 28 --Python --Les bases du langage Python 4
Algorithme de tri et implémentation en Python
Vous devez faire attention aux commandes que vous utilisez quotidiennement dans l'environnement de production.