[PYTHON] In 100 Tagen sind Sie Ingenieur. ――Tag 60 ――Programmieren ――Über Datenstruktur und Sortieralgorithmus

Klicken Sie hier bis gestern

Datenstruktur

Die Datenstruktur ist wichtig für Lernalgorithmen. Da der Algorithmus eine Prozedur ist, habe ich gesagt, welche Art von Daten und wie man sie manipuliert. Die Struktur der Daten ist ebenfalls ein wichtiger Punkt im Algorithmus.

aufführen

Der Python-Listentyp ist ein Datentyp im Array-Format, der einen Index verwendet Sie können der Reihe nach darauf zugreifen.

Im Listentyp können verschiedene Daten als Elemente gespeichert werden. Sie können Elemente hinzufügen, ändern, ersetzen und löschen.

#Listendefinition
l = [1,2,3,4,5]
print(l)

#Elementreferenz
print(l[0])

#Elemente ändern
l[1] = 8
print(l)

#Element hinzufügen
l.append(6)
print(l)

#Element löschen
l.pop(3)
print(l)

#Element einfügen
l.insert(4,9)
print(l)

#Elemente tauschen
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]

Stapel und Warteschlangen

"Stapel" und "Warteschlange" sind auch eine der Möglichkeiten, mit Daten umzugehen.

Stapel ・ Daten können am Anfang der Spalte hinzugefügt und Daten am Anfang der Spalte abgerufen werden. ・ Last-In-First-Out-LIFO (Last-In-First-Out)

Das Einfügen von Daten in den Stapel wird als "Push" und das Herausnehmen von Daten als "Pop" bezeichnet.

Warteschlange

Fügen Sie Daten vom Ende der Spalte hinzu und rufen Sie Daten vom Anfang der Spalte ab ・ First-In-First-Out (Tokoroten-Methode) FIFO (First-In-First-Out) -Das Einfügen von Daten in eine Warteschlange wird als "Warteschlange" bezeichnet, und das Abrufen von Daten wird als "Warteschlange" bezeichnet.

Referenz: Wikipedia

In Python kann es nach Listentyp oder ç realisiert werden.

Stapel

stack = []

#drücken
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]

Warteschlange

from collections import deque

#Warteschlangendefinition
queue = deque(["A","B","C"])
print(queue)

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

#Entscheidung
queue.popleft()
print(queue)

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

Haufen

Was ist ein Heap? Untergeordnete Elemente sind immer größer oder gleich (oder immer kleiner oder gleich) als übergeordnete Elemente Es handelt sich um baumstrukturierte Daten mit der Einschränkung.

Wenn wir einfach "Haufen" sagen, beziehen wir uns oft auf "halben Haufen" unter Verwendung eines Dichotomiebaums.

Referenz: Wikipedia

Der Heap kann in Python mit der Heapq-Bibliothek implementiert werden. Der minimale (oder maximale) Wert kann sofort im Heap abgerufen werden.

import heapq

#Erstelle eine Liste
heap = [1, 6, 8, 0, -1]
print(heap)

#Bestehende Liste häufen(Mindestwert)
heapq.heapify(heap)
print(heap)

#Element hinzufügen
heapq.heappush(heap, 10)
print(heap)

#Mindestwert entfernen
print(heapq.heappop(heap))
print(heap)

max_heap = [3,7,5,9,-2]
print(max_heap)
#Erstellen Sie einen Heap mit maximalem Wert
heapq._heapify_max(max_heap) 
print(max_heap)

#Maximalwert entfernen
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]

Über den Sortieralgorithmus

Der "Sortieralgorithmus" ist der Sortieralgorithmus. Es gibt viele Variationen zum einfachen Sortieren.

Eine stabile "stabile" Sortierung liegt vor, wenn die Datensätze mehrere Datensätze mit demselben Schlüssel enthalten. Nach dem Sortieren bleibt die Bestellbeziehung der Datensätze vor dem Sortieren erhalten.

Sortieren, damit die Positionsbeziehung vor dem Sortieren durch Sortieren unterbrochen wird Es wird eine instabile "instabile" Sorte genannt.

Es ist wünschenswert, einen Sortieralgorithmus zu verwenden, der die Sortierung schnell beendet und stabil ist.

Im Sortieralgorithmus ist der Rechenaufwand ebenfalls ein Richtwert. Der Umfang der Berechnung des Sortieralgorithmus, der allgemein gesagt wird, ist wie folgt.

Algorithmus	Stabilität	Durchschnittliche Zeit	Schlimmste Zeit	Beste Zeit	Schlechtester Raum
Blasensorte	Stabil	\mathcal{O}(n^2)	\mathcal{O}(n^2)	\mathcal{O}(n)	\mathcal{O}(1)
Selektive Sortierung	instabil	\mathcal{O}(n^2)	\mathcal{O}(n^2)	\mathcal{O}(n)	\mathcal{O}(n)
Sortierung einfügen	Stabil	\mathcal{O}(n^2)	\mathcal{O}(n^2)	\mathcal{O}(n)	\mathcal{O}(n)
Haufen sortieren	instabil	\mathcal{O}(n\log n)	\mathcal{O}(n\log n)	\mathcal{O}(n\log n)	\mathcal{O}(1)
Zusammenführen, sortieren	Stabil	\mathcal{O}(n\log n)	\mathcal{O}(n\log n)	\mathcal{O}(n\log n)	\mathcal{O}(n)
Schnelle Sorte	instabil	\mathcal{O}(n\log n)	\mathcal{O}(n^2)	\mathcal{O}(n)	\mathcal{O}(n)
Python-Sortierung(Tim sort)	Stabil	\mathcal{O}(n\log n)	\mathcal{O}(n\log n)	\mathcal{O}(n)	\mathcal{O}(n)

Schauen wir uns nun verschiedene Sortieralgorithmen an. Ich habe auch ein Implementierungsbeispiel beigefügt, aber ich denke, es gibt einen besseren Weg, es zu schreiben.

Blasensorte

Bubble Sort vergleicht die Werte zweier benachbarter Elemente in einer Liste Dies ist ein Ausrichtungsalgorithmus, der gemäß den Bedingungen ausgetauscht wird.

Sortieren Sie die Liste in absteigender Reihenfolge (absteigende Reihenfolge) oder aufsteigender Reihenfolge (aufsteigende Reihenfolge).

#Blasensorte
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

Wählen Sie Sortieren

Selektive Sortierung sucht nach dem Element mit dem minimalen (maximalen) Wert des Arrays Es ist ein Algorithmus, der ausgerichtet wird, indem er mit dem ersten Element des Arrays ausgetauscht wird.

#Selektive Sortierung
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

Sortierung einfügen

Sortierung einfügen erfolgt durch Einfügen eines neuen Elements an der entsprechenden Position für den ausgerichteten Teil der Liste. Dies ist ein Ausrichtungsalgorithmus.

#Sortierung einfügen
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

Haufen sortieren

Heap sort ist ein Sortieralgorithmus, der eine Liste mit einem dichotomisierten Heap Tree sortiert.

Nimmt Elemente aus der nicht ausgerichteten Liste und fügt sie der Reihe nach dem Heap hinzu. Wiederholen Sie diesen Vorgang, bis Sie alle Elemente hinzugefügt haben (nehmen Sie die Route und fügen Sie sie der ausgerichteten Liste hinzu).

#Haufen sortieren
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

Verwenden Sie in Python die Bibliothek heapq, die die Heap-Warteschlange realisiert Sie können auch einfach eine Heap-Sortierung schreiben.

import heapq

#Heap-Sortierung mit Heapq
def heap_sort2(data):
    h = data.copy()
    heapq.heapify(h)
    return [heapq.heappop(h) for _ in range(len(h))]

Zusammenführen, sortieren

Sortierung zusammenführen teilt das zu sortierende Array rekursiv und führt es erneut zusammen` Es ist ein Sortieralgorithmus, der versucht, die Sortierung zu realisieren.

#Zusammenführen, sortieren
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

Schnelle Sorte

Das Merkmal der "schnellen Sortierung" ist, dass die Anzahl der Datenvergleiche und -austausche sehr gering ist. Sie können die zufällig verteilten Daten effizient sortieren. Es ist ein Algorithmus, der nicht stabil ist.

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

Python-Standardsortierung

Pythons Standardsortierung ist (wahrscheinlich) Timsort.

Timsort ist ein stabiler Hybrid, der von Merge Sort und Insert Sort abgeleitet ist Der Sortieralgorithmus ist so konzipiert, dass er mit verschiedenen Datentypen gut funktioniert.

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

Vergleichen Sie die Ausführungszeit des Sortieralgorithmus

Lassen Sie uns die Ausführungszeit des obigen Sortieralgorithmus messen. Sie können leicht mit dem folgenden Code messen.

Sortiert 10000 Nummern. Mit jupyter notebook können Sie die Zeit mit% time messen.

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

Die kürzeste Zeit ist übrigens die Standardsortierung von Python.

Ich denke, dass sich dies erheblich ändern wird, je nachdem, wie Sie es implementieren. Ich denke, es ist ziemlich schwierig, eine Geschwindigkeit zu erreichen, die über der Standardsorte liegt. Normalerweise müssen Sie zum Sortieren kein eigenes Programm schreiben.

Zusammenfassung

Die Python-Sortierung ist so leistungsfähig, dass Sie sich normalerweise nicht darum kümmern. Es gibt nur wenige Probleme beim Sortieren.

Wie erfolgt die Sortierung? Wenn Sie vergleichen, wie unterschiedlich jede Methode ist Sie werden die Tiefe des Algorithmus verstehen.

40 Tage, bis Sie Ingenieur werden

Informationen zum Autor

HP von Otsu py: http://www.otupy.net/

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

Twitter： https://twitter.com/otupython