[PYTHON] In 100 Tagen sind Sie Ingenieur. ――Tag 61 ――Programmieren ――Über Erkundung

Klicken Sie hier bis gestern

Über die Erforschung

"Suchen" in der Programmierung dient dazu, die gewünschten Daten zu finden.

Es gibt verschiedene Arten von Daten und wie man nach Daten sucht.

Lineare Suche

Wenn Daten in der Liste ab dem Anfang der Liste gespeichert werden Wenn Sie bis zum Ende der Liste schauen, finden Sie die gewünschten Daten.

Eine solche Suchmethode wird "lineare Suche" genannt. Es ist einfach und leicht zu implementieren, da Sie nur die Reihenfolge überprüfen müssen.

Das folgende Beispiel ist ein einfaches lineares Suchbeispiel.

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

##Beispiel für eine lineare Suche
def linear_search(data, val):
    for x in data:
        if x == val:
            return True
    return False

print(linear_search(data, target))

True

Ich denke, es ist ein relativ leicht verständlicher Algorithmus Es wird schwierig sein, wenn mehr Daten untersucht werden müssen, bis der Wert gefunden ist.

Ich suche nach Zahlen in der Reihenfolge oben in der Liste, aber wenn sie am Ende der Liste stehen Es wird lange dauern.

Im Durchschnitt die Anzahl der Vergleiche von $ \ frac {n + 1} {2} $ Im schlimmsten Fall handelt es sich um eine $ O (n) $ -Verarbeitung.

Binäre Suche

Überlegen Sie, wie Sie schnell herausfinden können, ob die Anzahl der Daten in der Liste zunimmt "Lineare Suche" ist schwierig.

Wenn Sie sich einen bestimmten Wert wie ein Wörterbuch oder ein Telefonbuch ansehen, ist der gewünschte Wert höher Um zu beurteilen, ob es groß oder klein ist Eine Methode zum Suchen mit hoher Geschwindigkeit, indem der Vorgang des Eingrenzen des Suchbereichs auf die Hälfte wiederholt wird Es heißt "Dichotomie".

#Beispiel für 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))

Die Daten müssen sortiert werden, um eine Dichotomie zu ermöglichen. Sortieren Sie die Daten vor der Suche.

Breitensuche

Nicht bei der Suche nach in einer Liste gespeicherten Daten Angenommen, Sie möchten die gewünschten Daten in den hierarchischen Daten finden.

Zum Beispiel aus Daten mit einer baumartigen Struktur wie einer Website Beim Finden der gewünschten Seite Zu diesem Zeitpunkt können "Suche nach Breitenpriorität" und "Suche nach Tiefenpriorität" in Betracht gezogen werden.

Breite erste Suche

So listen Sie Dinge auf, die sich in der Nähe des Ortes befinden, an dem Sie Ihre Suche starten, und überprüfen Sie die einzelnen Elemente Es heißt "Breitenprioritätssuche (BFS)".

# BFS(Suche nach Breitenpriorität)
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('./'))

Tiefe erste Suche

So fahren Sie mit der Suche nach "Breitenpriorität" so weit fort, wie Sie möchten, und kehren zurück, wenn Sie nicht fortfahren können Es heißt "Tiefenprioritätssuche (DFS)".

Auch als "Backtrack-Methode" bekannt.

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('./'))

Zusammenfassung

Es gibt verschiedene Datensuchmethoden Der Umfang der Berechnung und die Ausführungsgeschwindigkeit hängen stark davon ab, wie die Daten zusammengestellt und durchsucht werden.

Mit dem optimalen Datenformat entsprechend den zu verarbeitenden Daten Betrachten Sie den Explorationsalgorithmus.

39 Tage, bis Sie Ingenieur werden

Informationen zum Autor

HP von Otsu py: http://www.otupy.net/

Youtube： https://www.youtube.com/channel/UCaT7xpeq8n1G_HcJKKSOXMw

Twitter： https://twitter.com/otupython