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 image002.png 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 image004.png 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 image002.png 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 image006.png 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 image008.png 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 image004.png …… (゚ Д ゚) 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é. image002.png 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

Recommended Posts

Un débutant en programmation a essayé de vérifier le temps d'exécution du tri, etc.
Le premier débutant en programmation à essayer une analyse de données simple avec programmation
[Python3] Définition d'un décorateur qui mesure le temps d'exécution d'une fonction
Un débutant qui programme depuis 2 mois a tenté d'analyser le PIB réel du Japon en séries chronologiques avec le modèle SARIMA.
J'ai essayé de trouver l'entropie de l'image avec python
J'ai essayé de trouver la moyenne de plusieurs colonnes avec TensorFlow
Comment trouver le coefficient de mise à l'échelle d'une ondelette bipolaire
[Python] Programmation pour trouver le nombre de a dans une chaîne de caractères qui se répète un nombre spécifié de fois.
les débutants en python ont essayé de le découvrir
Je souhaite enregistrer l'heure d'exécution et conserver un journal.
J'ai essayé de créer une expression régulière de "temps" en utilisant Python
Comment trouver l'adresse mémoire de la valeur de la trame de données Pandas
J'ai essayé de couper une image fixe de la vidéo
[Python] Une fonction simple pour trouver les coordonnées du centre d'un cercle
J'ai essayé de trouver la différence entre A + = B et A = A + B en Python, alors notez
J'ai essayé de trier les objets de l'image du plat de steak-② Tri des numéros de chevauchement
À propos de l'ordre d'apprentissage des langages de programmation (de débutant à intermédiaire) Partie 2
J'ai essayé de vérifier la meilleure façon de trouver un bon partenaire de mariage
Comment connaître le nombre de processeurs sans utiliser la commande sar
J'ai essayé de trouver l'itinéraire optimal du pays des rêves par recuit (quantique)
J'ai essayé d'afficher la valeur d'altitude du DTM dans un graphique
J'ai essayé de vérifier le résultat du test A / B avec le test du chi carré
Python: je souhaite mesurer proprement le temps de traitement d'une fonction
Je voulais utiliser le module de recherche d'Ansible2, mais cela a pris du temps, alors prenez note
Comment passer le résultat de l'exécution d'une commande shell dans une liste en Python
[Circuit x Python] Comment trouver la fonction de transfert d'un circuit en utilisant Lcapy
Découvrez comment diviser uniformément un fichier avec un certain nombre de lignes
Je souhaite stocker les résultats de% time, %% time, etc. dans un objet (variable)
J'ai essayé de refactoriser le code de Python débutant (lycéen)
J'ai essayé de créer un modèle avec l'exemple d'Amazon SageMaker Autopilot
Comment calculer la volatilité d'une marque
Comment trouver la zone du diagramme de Boronoi
Trouver la main de "Millijan" par l'optimisation des combinaisons
Paramètre pour afficher le journal de l'exécution de cron
J'ai essayé de trouver le rapport de circonférence par 100 millions de chiffres
J'ai essayé la programmation python pour la première fois.
Trouvez le nombre de jours dans un mois
J'ai essayé de corriger la forme trapézoïdale de l'image
Découvrez le jour par date / heure
De l'introduction de pyethapp à l'exécution du contrat
J'ai essayé de vectoriser les paroles de Hinatazaka 46!
J'ai étudié comment rationaliser le flux de travail avec Excel x Python ②
J'ai essayé de faire quelque chose comme un chatbot avec le modèle Seq2Seq de TensorFlow
L'histoire du serveur Web et du DAG d'Airflow, dont le chargement prend beaucoup de temps
J'ai étudié comment rationaliser le flux de travail avec Excel x Python ④
J'ai essayé de notifier la mise à jour de "Devenir romancier" en utilisant "IFTTT" et "Devenir un romancier API"
J'ai essayé de savoir comment rationaliser le flux de travail avec Excel x Python ⑤
Un débutant en python a tenté de faire un stage dans une entreprise informatique [Jour 3 vers les nuages ...]
Je ne trouve pas l'horloge tsc! ?? L'histoire d'essayer d'écrire un patch de noyau
J'ai essayé de trier les objets de l'image du plat de steak-④ Clustering
J'ai étudié comment rationaliser le flux de travail avec Excel x Python ①
Mémorandum des commandes, packages, termes, etc. utilisés sous Linux (mis à jour de temps en temps)
Découvrez le nombre maximum de caractères dans un texte multiligne stocké dans un bloc de données