[PYTHON] Un débutant en programmation a essayé de vérifier le temps d'exécution du tri, etc.

Aperçu

Lire l'algorithme de choix aléatoire de math girl Dernière fois (http://qiita.com/RyuSA/items/0be781f38fa7fc38f69d) Chronométré certaines sortes → Je veux une distribution plus solide → Voulez-vous le mesurer?

Environnement d'exécution

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

Algorithme de recherche

Méthode de mesure

Répétez la procédure suivante 10000 fois et comparez les heures.

1. Générez au hasard 100 000 numéros de 1 à 100 000 avec numpy.random.randint (1 100 000 100 000)
2. Générez une cible de recherche avec random.randint (1 100 000)
3. Exécutez chaque algorithme de recherche (commencez la mesure à partir d'ici)
4. Lorsque Vrai / Faux revient, la mesure se termine et le temps mesuré est enregistré dans un fichier.
5. Revenez à 1.

Recherche linéaire

L'algorithme de recherche le plus simple. Vérifiez simplement de l'avant. Le code source est ci-dessous

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

Résultat de la mesure

Vous trouverez ci-dessous la distribution de fréquence des résultats de mesure Il y en a beaucoup entre 0,09 sec et 0,10 sec. Il semble que False soit renvoyé ici.

Recherche linéaire avec garde

Ajoutez simplement la cible de recherche à la fin de la séquence de nombres donnée. C'est plus rapide qu'une simple recherche linéaire car cela réduit le nombre de décisions dans la boucle While. Le code source est ci-dessous

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

Résultat de la mesure

Vous trouverez ci-dessous la distribution de fréquence des résultats de mesure Il y en a beaucoup entre 0,08 sec et 0,085 sec. Il semble que False soit renvoyé ici. Dans la recherche linéaire précédente et la recherche linéaire avec des gardes, vous pouvez voir que cette dernière est un peu plus rapide.

Méthode de recherche par bisection

Comment comparer l'élément au milieu d'une séquence de nombres donnée (triée) avec la cible de recherche et réduire la plage de recherche en fonction de la taille Seulement dans ce cas, l'opération de tri de la colonne numérique A donnée est effectuée à l'avance. Le code source est ci-dessous

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

Résultat de la mesure

Vous trouverez ci-dessous la distribution de fréquence des résultats de mesure Il y en a beaucoup entre 0,015 et 0,017 s. Par rapport aux deux recherches précédentes, vous pouvez voir que l'algorithme est extrêmement plus rapide même s'il inclut le tri en premier.

Algorithme de tri

Méthode de mesure

Répétez la procédure suivante 10000 fois et comparez les heures.

1. Générez au hasard 1 000 nombres de 1 à 1 000 avec numpy.random.randint (1,1000,1000)
2. Exécutez chaque algorithme de tri (commencez la mesure à partir d'ici)
3. Lorsque le nombre de lignes est renvoyé, la mesure est terminée et le temps mesuré est enregistré dans un fichier.
4. Revenez à 1.

Tri à bulles

Une méthode de répétition de comparaison et d'échange avec les voisins dans l'ordre à partir du premier de la séquence de nombres donnée. Le code source est ci-dessous

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

Résultat de la mesure

Vous trouverez ci-dessous la distribution de fréquence des résultats de mesure 0.7sec est la valeur la plus fréquente. Très lent ...

Tri rapide

La première de la séquence donnée est prise comme pivot, et elle est divisée en deux séquences plus grandes / plus petites que le pivot. Il ne vous reste plus qu'à répéter la même opération. Cependant, passer une séquence triée de nombres, ou une séquence similaire de nombres, peut être très lent. Le code source est ci-dessous

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

Résultat de la mesure

Vous trouverez ci-dessous la distribution de fréquence des résultats de mesure 0,17 s est la valeur la plus fréquente. Par rapport au tri à bulles, la vitesse était environ 75% plus rapide. Surtout cette fois, puisque la séquence de nombres passée est générée par des nombres pseudo aléatoires, je me suis demandé si le temps d'exécution était relativement stable car la séquence de nombres était modérément désordonnée. .. ..

Tri rapide aléatoire

Plutôt que de fixer la méthode de pivotement sur le côté gauche de la séquence, obtenez-la au hasard. Cela vous permettra d'effectuer un tri rapide sans dépendre du caractère aléatoire de la séquence (distribution de probabilité de chaque élément) (devrait) Le code source est ci-dessous

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

Résultat de la mesure

Vous trouverez ci-dessous la distribution de fréquence des résultats de mesure …… (ﾟ Д ﾟ) Poker Eh bien, pour une raison quelconque, il est devenu très tard lorsque j'ai fait un choix aléatoire. .. .. Et donc j'ai mis np.random.randint (L, R) dans le tri rapide original en vain et l'ai remesuré. C'est aussi tard! (ﾟ Д ﾟ) Apparemment, np.random.randint est un processus très lourd par rapport à d'autres processus. .. .. Il semble qu'il puisse être utilisé comme un tri rapide qui ne dépend pas d'une séquence de nombres donnée tout en conservant la même vitesse d'exécution (sauf pour la génération aléatoire) même s'il est randomisé.

en conclusion

Lorsque le temps d'exécution de l'algorithme de recherche / tri a été réellement mesuré et agrégé, les résultats étaient presque aussi théoriques. D'un autre côté, si vous faites des choix aléatoires, il faudra du temps pour générer des nombres aléatoires, et vous pouvez également connaître des faits intéressants tels que l'algorithme d'origine est plus rapide (rires)

Les références

Mathematics Girl Choosing Algorithm Auteur: Hiroshi Yuki Programmation des temps de tri comparés par les débutants