Vous serez ingénieur dans 100 jours ――Jour 61 ――Programmation ――A propos de l'exploration

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

À propos de l'exploration

«Rechercher» dans la programmation consiste à trouver les données souhaitées.

Il existe différentes formes de données et comment rechercher des données.

Recherche linéaire

Lorsque les données sont stockées dans list, dans l'ordre à partir du début de la liste Si vous regardez à la fin de la liste, vous trouverez les données souhaitées.

Une telle méthode de recherche est appelée «recherche linéaire». C'est simple et facile à mettre en œuvre car il vous suffit de vérifier dans l'ordre.

L'exemple suivant est un exemple de recherche linéaire simple.

data = [6342, 4588, 2362, 6812, 6102, 5119, 2631, 3548, 4559, 3570]
target = 4559
flg = False

##Exemple de recherche linéaire
def linear_search(data, val):
    for x in data:
        if x == val:
            return True
    return False

print(linear_search(data, target))

True

Je pense que c'est un algorithme relativement facile à comprendre Ce sera difficile s'il y a plus de données à examiner jusqu'à ce que la valeur soit trouvée.

Je recherche les nombres dans l'ordre à partir du haut de la liste, mais si c'est à la fin de la liste Il faudra longtemps.

En moyenne, le nombre de comparaisons de $ \ frac {n + 1} {2} $ Dans le pire des cas, ce sera un traitement $ O (n) $.

Recherche binaire

Considérer comment le savoir rapidement même si le nombre de données augmente dans la liste La «recherche linéaire» est difficile.

Lorsque vous regardez une certaine valeur, comme un dictionnaire ou un annuaire téléphonique, la valeur souhaitée est supérieure à cela Comme moyen de juger s'il est grand ou petit Méthode de recherche à grande vitesse en répétant l'opération consistant à réduire de moitié la plage de recherche Cela s'appelle «dichotomie».

#Exemple de dichotomie
def binary_search(data, num):
    left , right = 0 , len(data) - 1
    while left <= right:
        m = (left + right) // 2
        if data[m] == num:
            return m
        elif data[m] < num:
            left = m + 1
        else:
            right = m - 1
    return -1

data = [6342, 4588, 2362, 6812, 6102, 5119, 2631, 3548, 4559, 3570]
data.sort()
print(data)
print(binary_search(data, 5119))

Les données doivent être triées pour permettre la «dichotomie». Triez les données avant de rechercher.

Recherche étendue

Pas lors de la recherche de données stockées dans une liste Supposons que vous souhaitiez trouver les données souhaitées dans les données hiérarchiques.

Par exemple, à partir de données avec une structure arborescente comme un site Web Lors de la recherche de la page souhaitée À ce moment-là, la recherche de priorité de largeur et la recherche de priorité de profondeur peuvent être prises en compte.

Première recherche en largeur

Comment répertorier les éléments qui sont proches de l'endroit où vous commencez votre recherche et les examiner de près Elle est appelée «recherche de priorité de largeur (BFS)».

# BFS(Recherche de priorité de largeur)
import os
from collections import deque
 
def bfs(path):
    q = deque([])
    q.append(path)
    while len(q) > 0:
        p = q.popleft()
        print (p)
        for child in os.listdir(p):
            child_path = p + '/' + child
            if os.path.isdir(child_path):
                q.append(child_path)
    return q

print(bfs('./'))

Première recherche en profondeur

Comment passer à la cible pour la `recherche de priorité de largeur 'et revenir quand elle ne peut pas continuer Elle est appelée «recherche de priorité en profondeur (DFS)».

Aussi connue sous le nom de «méthode de retour arrière».

import os
from collections import deque
 
def dfs(path):
    q = deque([]) 
    q.append(path)
    while len(q) > 0:
        p = q.pop()
        print (p)
        for child in os.listdir(p):
            child_path = p + '/' + child
            if os.path.isdir(child_path):
                q.append(child_path) 
    return q

print(dfs('./'))

Résumé

Il existe différentes méthodes de recherche de données La quantité de calcul et la vitesse d'exécution changeront considérablement en fonction de la façon d'assembler et de rechercher les données.

Avec le format de données optimal en fonction des données à traiter Considérez l'algorithme d'exploration.

39 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 61 ――Programmation ――A propos de l'exploration
Vous serez ingénieur dans 100 jours ――Jour 71 ――Programmation ――À propos du scraping 2
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 60 ―― Programmation ―― À propos de la structure des données et de l'algorithme de tri
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 33 - Python - Bases du langage Python 8
Vous serez ingénieur dans 100 jours --Jour 26 --Python --Basiques du langage Python 3
Vous devenez ingénieur en 100 jours - Jour 35 - Python - Ce que vous pouvez faire avec Python
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
Vous devez faire attention aux commandes que vous utilisez quotidiennement dans l'environnement de production.
Ce que les débutants pensent de la programmation en 2016