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

Cliquez ici jusqu'à hier

À 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