[PYTHON] Ein Programmieranfänger versuchte, die Ausführungszeit des Sortierens usw. zu überprüfen.

Überblick

Lesen Sie den Zufallsauswahlalgorithmus für Mathematikmädchen Letztes Mal (http://qiita.com/RyuSA/items/0be781f38fa7fc38f69d) Timed einige Arten → Ich möchte eine festere Verteilung → Möchten Sie es messen?

Ausführungsumgebung

DELL venue 11pro 5300 OS : Windows10 CPU : Atom Z3770 1.46GHz Memory : 2GB Language : Python 2.7

Suchalgorithmus

Messmethode

Wiederholen Sie den folgenden Vorgang 10000 Mal und vergleichen Sie die Zeiten.

1. Generieren Sie mit numpy.random.randint (1.100000.100000) zufällig 100.000 Zahlen von 1 bis 100.000.
2. Generieren Sie ein Suchziel mit random.randint (1.100000)
3. Führen Sie jeden Suchalgorithmus aus (Messung von hier aus starten)
4. Wenn True / False zurückkehrt, endet die Messung und die gemessene Zeit wird in einer Datei gespeichert.
5. Kehren Sie zu 1 zurück.

Lineare Suche

Der einfachste Suchalgorithmus. Einfach von vorne einchecken. Der Quellcode ist unten

import numpy as np

def LINER_SERCH(A,n,v):
    k = 1
    while  k < n:
        if A[k] == v:
            return True
        k += 1
    return False

Messergebnis

Nachfolgend finden Sie die Häufigkeitsverteilung der Messergebnisse Es gibt viele zwischen 0,09 Sekunden und 0,10 Sekunden. Es scheint, dass False hier zurückgegeben wird.

Lineare Suche mit Schutz

Fügen Sie einfach das Suchziel am Ende der angegebenen Zahlenfolge hinzu. Es ist schneller als nur eine lineare Suche, da es die Anzahl der Entscheidungen in der While-Schleife verringert. Der Quellcode ist unten

import numpy as np

def SENTINEL_LINER_SERCH(A,n,v):
    A = np.append(A,v)
    k = 0
    while  A[k] != v:
        k += 1
    if k < n:
        return True
    return False

Messergebnis

Nachfolgend finden Sie die Häufigkeitsverteilung der Messergebnisse Es gibt viele zwischen 0,08 Sekunden und 0,085 Sekunden. Es scheint, dass False hier zurückgegeben wird. Bei der vorherigen linearen Suche und der linearen Suche mit Schutzvorrichtungen können Sie feststellen, dass letztere etwas schneller ist.

Bisektionssuchmethode

So vergleichen Sie das Element in der Mitte einer bestimmten Zahlenfolge (sortiert) mit dem Suchziel und reduzieren den Suchbereich entsprechend der Größe Nur in diesem Fall wird der Vorgang des Sortierens der gegebenen Nummernspalte A im Voraus ausgeführt. Der Quellcode ist unten

import numpy as np
import math
def BINARY_SEARCH(A,n,v):
    a = 0
    b = n-1
    A.sorted()
    while  a <= b :
        k = int(math.floor(b + (a-b)/2))
        if A[k] == v:
            return True
        elif A[k] < v:
            a = k+1
        else:
            b = k-1
    return False

Messergebnis

Nachfolgend finden Sie die Häufigkeitsverteilung der Messergebnisse Es gibt viele zwischen 0,015 Sekunden und 0,017 Sekunden. Im Vergleich zu den beiden vorherigen Suchvorgängen können Sie feststellen, dass der Algorithmus überwältigend schneller ist, obwohl er zuerst die Sortierung enthält.

Sortieralgorithmus

Messmethode

Wiederholen Sie den folgenden Vorgang 10000 Mal und vergleichen Sie die Zeiten.

1. Generieren Sie zufällig 1000 Zahlen von 1 bis 1000 mit numpy.random.randint (1,1000,1000).
2. Führen Sie jeden Sortieralgorithmus aus (starten Sie die Messung von hier aus).
3. Wenn die Anzahl der Zeilen zurückgegeben wird, ist die Messung abgeschlossen und die gemessene Zeit wird in einer Datei gespeichert.
4. Kehren Sie zu 1 zurück.

Blasensorte

Eine Methode zum Wiederholen des Vergleichs und des Austauschs mit den Nachbarn in der Reihenfolge ab der ersten der angegebenen Zahlenfolge. Der Quellcode ist unten

import numpy as np

def BUBBLE_SORT(A):
    n = np.size(A)
    m = n-1
    while  m > 1:
        k = 0
        while k < m :
            if A[k] > A[k+1]:
                A[k],A[k+1] = A[k+1],A[k]
            k += 1
        m -= 1
    return A

Messergebnis

Nachfolgend finden Sie die Häufigkeitsverteilung der Messergebnisse 0,7 Sekunden ist der häufigste Wert. Sehr langsam ...

Schnelle Sorte

Die erste der angegebenen Sequenzen wird als Drehpunkt verwendet und in zwei Sequenzen unterteilt, die größer / kleiner als der Drehpunkt sind. Alles was Sie tun müssen, ist den gleichen Vorgang zu wiederholen. Das Übergeben einer sortierten Folge von Zahlen oder einer ähnlichen Folge von Zahlen kann jedoch sehr langsam sein. Der Quellcode ist unten

import numpy as np
def QUICK_SORT(A,L,R):
    if L < R:
        p = L
        k = L+1
        while k <= R:
            if A[k] < A[L]:
                A[p+1], A[k] = A[k], A[p+1]
                p += 1
            k += 1
        A[L], A[p] = A[p], A[L]
        A = QUICK_SORT(A,L,p-1)
        A = QUICK_SORT(A,p+1,R)
    return A

Messergebnis

Nachfolgend finden Sie die Häufigkeitsverteilung der Messergebnisse 0,17 Sekunden ist der häufigste Wert. Im Vergleich zur Blasensortierung war die Geschwindigkeit etwa 75% schneller. Insbesondere dieses Mal, da die übergebene Zahlenfolge durch Pseudozufallszahlen erzeugt wird, fragte ich mich, ob die Ausführungszeit aufgrund der moderaten Unordnung in der Folge relativ stabil war. .. ..

Zufällige schnelle Sortierung

Anstatt die Schwenkmethode auf der linken Seite der Sequenz zu fixieren, erhalten Sie sie zufällig. Auf diese Weise können Sie eine schnelle Sortierung durchführen, ohne von der Zufälligkeit der Sequenz (Wahrscheinlichkeitsverteilung jedes Elements) abhängig zu sein (sollte) Der Quellcode ist unten

import numpy as np
def RANDOMIZED_QUICK_SORT(A,L,R):
    if L < R:
        r = np.random.randint(L,R)
        A[L], A[r] = A[r], A[L]
        p = L
        k = L+1
        while k <= R:
            if A[k] < A[L]:
                A[p+1], A[k] = A[k], A[p+1]
                p += 1
            k += 1
        A[L], A[p] = A[p], A[L]
        A = RANDOMIZED_QUICK_SORT(A,L,p-1)
        A = RANDOMIZED_QUICK_SORT(A,p+1,R)
    return A

Messergebnis

Nachfolgend finden Sie die Häufigkeitsverteilung der Messergebnisse …… (ﾟ Д ﾟ) Poker Aus irgendeinem Grund wurde es sehr spät, als ich eine zufällige Wahl traf. .. .. Und so habe ich np.random.randint (L, R) vergeblich in die ursprüngliche Schnellsortierung eingefügt und sie erneut gemessen. Das ist auch spät! (ﾟ Д ﾟ) Anscheinend ist np.random.randint im Vergleich zu anderen Prozessen ein sehr schwerer Prozess. .. .. Es scheint, dass es als schnelle Sortierung verwendet werden kann, die nicht von einer bestimmten Zahlenfolge abhängt, während die gleiche Ausführungsgeschwindigkeit (mit Ausnahme der zufälligen Generierung) beibehalten wird, selbst wenn es zufällig ist.

abschließend

Als die Ausführungszeit des Such- / Sortieralgorithmus tatsächlich gemessen und aggregiert wurde, waren die Ergebnisse fast genauso theoretisch. Wenn Sie jedoch zufällige Entscheidungen treffen, dauert es einige Zeit, um Zufallszahlen zu generieren, und Sie können auch interessante Fakten kennen, z. B. dass der ursprüngliche Algorithmus schneller ist (lacht).

Verweise

Mathematics Girl Choosing Algorithm Autor: Hiroshi Yuki Programmieranfänger verglichen Sortierzeiten