27. Suchen

Das Suchen ist eine wichtige und sehr häufige Aufgabe, die Rechner ständig ausführen. Suchanfragen werden jedes Mal verwendet, wenn jemand eine Strg-F-Taste für „Suchen“ drückt, wenn ein Benutzer ein Element mit Autovervollständigung schnell auswählt oder wenn ein Webserver Informationen über einen Kunden abruft, um eine angepasste Webseite mit dem Kundenauftrag zu präsentieren.

../../_images/search.png

Es gibt viele Möglichkeiten, nach Daten zu suchen. Google hat eine ganze Multi-Milliarden-Dollar-Firma auf diese Tatsache gegründet. In diesem Kapitel werden die zwei einfachsten Suchmethoden vorgestellt, die lineare Suche und die binäre Suche.

27.1. Aus einer Datei lesen

Bevor wir uns mit der Suche befassen, müssen wir lernen, wie Daten aus einer Datei gelesen werden. Das Einlesen eines Datensatzes aus einer Datei macht wesentlich mehr Spaß, als ihn jedes Mal von Hand einzugeben.

Angenommen, wir müssen ein Programm erstellen, mit dem wir schnell den Namen eines Superschurken finden können. Zu Beginn benötigt unser Programm eine Datenbank mit Superschurken. Um diesen Datensatz herunterzuladen, lade diese Datei herunter und speichere sie:

super_villains.txt

Dies sind zufällige Namen, die von der nine.frenchboys.net-Website generiert wurden. (Obwohl den Superschurken-Generator beim letzten Mal, wo ich nachgesehen habe, nicht mehr gab). Sie haben aber auch andere coole Zufallsgeneratoren.

Speichere diese Datei und merke dir, in welchem ​​Verzeichnis du sie gespeichert hast.

Erstelle im selben Verzeichnis wie „super_villains.txt“ folgendes Python-Programm, speichere es und führe es aus:

Datei einlesen
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
def main():
    """ Read in lines from a file """

    # Open the file for reading, and store a pointer to it in the new
    # variable "file"
    my_file = open("super_villains.txt")

    # Loop through each line in the file like a list
    for line in my_file:
        print(line)


main()

In diesem Code gibt es nur eine neue Anweisung: open. Da es sich um eine integrierte Funktion wie print handelt, ist kein import erforderlich. Ausführliche Informationen zu dieser Funktion findest du in der Python-Dokumentation, die Dokumentation für diese Anweisung ist jedoch zu diesem Zeitpunkt so technisch, dass sie möglicherweise nicht einmal einen Blick wert ist.

Das obige Programm weist zwei Probleme auf, bietet jedoch ein einfaches Beispiel für das Einlesen einer Datei. Zeile 6 öffnet eine Datei und macht sie zum Lesen bereit. Der Name der Datei steht zwischen den Anführungszeichen. Die neue Variable my_file ist ein Objekt, das die gelesene Datei darstellt. Zeile 9 zeigt, wie eine normale for-Schleife verwendet werden kann, um eine Datei zeilenweise durchzulesen. Stelle dir die Datei als eine Liste von Zeilen vor, und die neue Variable line wird auf jede dieser Zeilen gesetzt, wenn das Programm die Schleife durchläuft.

Führe das Programm aus. Eines der Probleme dabei ist, dass der Text mit einer zusätzlichen Leerzeile ausgegeben wird. Der Grund dafür ist, dass jede Zeile, die aus der Datei geholt und in der Variablen line gespeichert wird, das Zeilenende als Teil der Zeichenfolge enthält. Erinnere dich an den Wagenrücklauf und den Zeilenvorschub, die in Kapitel 1 eingeführt wurden? Die print-Anweisung fügt einen weiteres Zeilenende hinzu und das Ergebnis ist eine Ausgabe mit einer zusätzlichen Leerzeile.

Das zweite Problem ist, dass die Datei geöffnet, aber nicht geschlossen wird. Dieses Problem ist nicht so offensichtlich wie das Problem der zusätzlichen Leerzeile, aber es ist wichtig. Das Windows-Betriebssystem kann nur eine bestimmte Anzahl von Dateien gleichzeitig öffnen. Eine Datei kann normalerweise nur von einem Programm gleichzeitig geöffnet werden. Wenn Sie eine Datei geöffnet lassen, können andere Programme nur eingeschränkt mit der Datei arbeiten und Systemressourcen belegen. Es ist notwendig, die Datei zu schließen, um Windows mitzuteilen, dass das Programm nicht mehr mit dieser Datei arbeitet. In diesem Fall ist dies nicht allzu wichtig, da Windows nach dem Ausführen eines Programms alle noch geöffneten Dateien automatisch schließt. Aber da es eine schlechte Angewohnheit ist, so zu programmieren, aktualisieren wir den Code:

Datei einlesen
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
def main():
    """ Read in lines from a file """

    # Open the file for reading, and store a pointer to it in the new
    # variable "file"
    my_file = open("super_villains.txt")

    # Loop through each line in the file like a list
    for line in my_file:
        # Remove any line feed, carriage returns or spaces at the end of the line
        line = line.strip()
        print(line)

    my_file.close()


main()

The listing above works better. It has two new additions. On line 11 is a call to the strip method built into every String class. This function returns a new string without the trailing spaces and carriage returns of the original string. The method does not alter the original string but instead creates a new one. This line of code would not work:

line.strip()

If the programmer wants the original variable to reference the new string, she must assign it to the new returned string as shown on line 11.

The second addition is on line 14. This closes the file so that the operating system doesn’t have to go around later and clean up open files after the program ends.

27.2. Einlesen in ein Array

Es ist nützlich, den Inhalt einer Datei in ein Array einzulesen, damit das Programm sie später verarbeiten kann. Dies kann einfach in Python mit dem folgenden Code durchgeführt werden:

Liest eine Datei von der Festplatte ein und legt sie in einem Array ab
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def main():
    """ Read in lines from a file """

    # Open the file for reading, and store a pointer to it in the new
    # variable "file"
    my_file = open("super_villains.txt")

    # Create an empty list to store our names
    name_list = []

    # Loop through each line in the file like a list
    for line in my_file:
        # Remove any line feed, carriage returns or spaces at the end of the line
        line = line.strip()

        # Add the name to the list
        name_list.append(line)

    my_file.close()

    print( "There were", len(name_list), "names in the file.")


main()

Dies kombiniert das neue Muster zum Lesen einer Datei mit dem zuvor erlernten Muster zum Erstellen eines leeren Arrays und zum Anhängen, wenn neue Daten eingehen. Dies wurde unter An eine Liste anhängen gezeigt. Um zu überprüfen, ob die Datei korrekt in das Array eingelesen wurde, kann ein Programmierer die Länge des Arrays ausgeben:

print( "There were",len(name_list),"names in the file.")

Oder der Programmierer kann den gesamten Inhalt des Arrays ausgeben:

for name in name_list:
    print(name)

Stelle sicher, dass du die Datei lesen kannst, bevor du mit den verschiedenen Suchvorgängen fortfahren.

27.4. Linearer Suchalgorithmus

Lineare Suche
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
# --- Linear search
key = "Morgiana the Shrew"

# Start at the beginning of the list
current_list_position = 0

# Loop until you reach the end of the list, or the value at the
# current position is equal to the key
while current_list_position < len(name_list) and name_list[current_list_position] != key:

    # Advance to the next item in the list
    current_list_position += 1

if current_list_position < len(name_list):
    print("The name is at position", current_list_position)
else:
    print("The name was not in the list.")

Die lineare Suche ist ziemlich einfach. Zeile 5 erstellt eine Inkrementvariable, die genau festhält, wo in der Liste das Programm als nächstes nachsehen muss. Das erste Element, das überprüft werden muss, steht an der Position Null, also wird current_list_position auf Null gesetzt.

Die nächste Zeile ist etwas komplexer. Der Rechner muss so lange eine Schleife ausführen, bis eine der beiden Situationen eintritt: Es findet das Element oder es gehen ihm die Elemente aus. Beim ersten Vergleich wird festgestellt, ob das aktuelle Position, die wir überprüfen, vor dem Ende der Liste liegt. In diesem Fall können wir die Schleife fortsetzen. Beim zweiten Vergleich wird festgestellt, ob das aktuelle Element in der Namensliste dem gesuchten Namen entspricht.

Diese Prüfung, um festzustellen, ob das Programm keine Elemente mehr hat, muss zuerst erfolgen. Andernfalls prüft das Programm auf ein nicht vorhandenes Element, was einen Fehler verursacht.

Zeile 12 wechselt einfach zum nächsten Element, wenn die Bedingungen für die weitere Suche in Zeile 9 erfüllt sind.

Am Ende der Schleife prüft das Programm, ob das Ende der Liste in Zeile 14 erreicht wurde. Denke daran, dass eine Liste mit n Elementen von 0 bis n-1 nummeriert ist. Wenn also i gleich der Länge der Liste ist, ist das Ende erreicht. Wenn es weniger ist, haben wir das Element gefunden.

Das vollständige Beispiel mit dem Einlesen der Datei und der Suche findest du unten:

Lineare Suche
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
def main():
    """ Read in lines from a file """

    # Open the file for reading, and store a pointer to it in the new
    # variable "file"
    my_file = open("super_villains.txt")

    # Create an empty list to store our names
    name_list = []

    # Loop through each line in the file like a list
    for line in my_file:
        # Remove any line feed, carriage returns or spaces at the end of the line
        line = line.strip()

        # Add the name to the list
        name_list.append(line)

    my_file.close()

    print("There were", len(name_list), "names in the file.")

    # --- Linear search
    key = "Morgiana the Shrew"

    # Start at the beginning of the list
    current_list_position = 0

    # Loop until you reach the end of the list, or the value at the
    # current position is equal to the key
    while current_list_position < len(name_list) and name_list[current_list_position] != key:
        # Advance to the next item in the list
        current_list_position += 1

    if current_list_position < len(name_list):
        print("The name is at position", current_list_position)
    else:
        print("The name was not in the list.")


main()

Wir können dieses Beispiel verbessern, indem wir sowohl das Lesen der Datei als auch die Suche in ihre eigenen Funktionen verschieben:

Lineare Suche
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
def read_in_file(file_name):
    """ Read in lines from a file """

    # Open the file for reading, and store a pointer to it in the new
    # variable "file"
    my_file = open(file_name)

    # Create an empty list to store our names
    name_list = []

    # Loop through each line in the file like a list
    for line in my_file:
        # Remove any line feed, carriage returns or spaces at the end of the line
        line = line.strip()

        # Add the name to the list
        name_list.append(line)

    my_file.close()

    return name_list


def linear_search(key, name_list):
    """ Linear search """

    # Start at the beginning of the list
    current_list_position = 0

    # Loop until you reach the end of the list, or the value at the
    # current position is equal to the key
    while current_list_position < len(name_list) and name_list[current_list_position] != key:

        # Advance to the next item in the list
        current_list_position += 1

    return current_list_position


def main():

    key = "Morgiana the Shrew"
    name_list = read_in_file("super_villains.txt")
    list_position = linear_search(key, name_list)

    if list_position < len(name_list):
        print("The name", key, "is at position", list_position)
    else:
        print("The name", key, "was not in the list.")


main()

27.6. Variationen der linearen Suche mit Objekten

Nehmen wir zum Beispiel an, wir hätten eine Liste von Objekten für unser Text-Adventure. Vielleicht möchten wir diese Liste überprüfen und herausfinden, ob sich Gegenstände im selben Raum wie unsere Spielfigur befinden. Oder ob alle Gegenstände im selben Raum sind. Oder wir möchten eine Liste der Gegenstände erstellen, die die Spielfigur mit sich trägt, wenn sich alle in einem „speziellen“ Raum befinden, der das Inventar des Spielers darstellt.

Zunächst müssen wir unsere Klasse für Objekte im Adventure definieren:

Adventure-Objekt-Klasse
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class AdventureObject:
    """ Class that defines an object in a text adventure game """

    def __init__(self, description, room):
        """ Constructor."""

        # Description of the object
        self.description = description

        # The number of the room that the object is in
        self.room = room

27.6.1. Hat mindestens ein Gegenstand eine Eigenschaft?

Befindet sich mindestens ein Objekt im angegebenen Raum? Wir können das überprüfen.

Überprüfen, ob die Liste ein Element enthält, das eine Eigenschaft hat - while-Schleife
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
def check_if_one_item_is_in_room_v1(my_list, room):
    """
    Return true if at least one item has a
    property.
    """
    i = 0
    while i < len(my_list) and my_list[i].room != room:
        i += 1

    if i < len(my_list):
        # Found an item with the property
        return True
    else:
        # There is no item with the property
        return False

Dies könnte auch mit einer for -Schleife geschehen. In diesem Fall wird die Schleife mit einem return vorzeitig beendet, sobald der Gegenstand gefunden wurde. Der Programmcode ist kürzer, aber nicht jeder Programmierer würde ihn bevorzugen. Einige Programmierer sind der Meinung, dass Schleifen nicht mit einer return- oder break-Anweisung vorzeitig beendet werden sollten. Alles hängt von den persönlichen Vorlieben oder den persönlichen Vorlieben der Person ab, die die Rechnung bezahlt.

Überprüfen, ob die Liste ein Element enthält, das eine Eigenschaft hat - for-Schleife
1
2
3
4
5
6
7
8
9
def check_if_one_item_is_in_room_v2(my_list, room):
    """
    Return true if at least one item has a
    property. Works the same as v1, but less code.
    """
    for item in my_list:
        if item.room == room:
            return True
    return False

27.6.2. Haben alle Gegenstände eine Eigenschaft?

Befinden sich alle Adventure-Objekte im selben Raum? Dieser Code ist dem vorherigen Beispiel sehr ähnlich. Erkennst du den Unterschied und siehst du den Grund für die Änderung.

Überprüfen, ob alle Elemente eine Eigenschaft haben
1
2
3
4
5
6
7
8
def check_if_all_items_are_in_room(my_list, room):
    """
    Return true if at ALL items have a property.
    """
    for item in my_list:
        if item.room != room:
            return False
    return True

27.6.3. Erstellen einer Liste mit allen Elementen, die einer Eigenschaft entsprechen

Was ist, wenn du eine Liste der Objekte in Raum 5 haben möchtest? Dies ist eine Kombination aus unserem vorherigen Code und dem Code zum Anhängen von Elementen an eine Liste, die wir bereits kennengelernt haben (siehe Einführung in Listen).

Erstelle eine weitere Liste mit allen Elementen, die einer Eigenschaft entsprechen
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
def get_items_in_room(my_list, room):
    """
    Build a brand new list that holds all the items
    that match our property.
    """
    matching_list = []
    for item in my_list:
        if item.room == room:
            matching_list.append(item)
    return matching_list

Wie würdest du all dies testen? Der obige Code kann mit dem folgenden Code kombiniert werden:

Beispielfunktionen ausführen
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
def main():
    object_list = []
    object_list.append(AdventureObject("Key", 5))
    object_list.append(AdventureObject("Bear", 5))
    object_list.append(AdventureObject("Food", 8))
    object_list.append(AdventureObject("Sword", 2))
    object_list.append(AdventureObject("Wand", 10))

    result = check_if_one_item_has_property_v1(object_list, 5)
    print("Result of test check_if_one_item_has_property_v1:", result)

    result = check_if_one_item_has_property_v2(object_list, 5)
    print("Result of test check_if_one_item_has_property_v2:", result)

    result = check_if_all_items_have_property(object_list, 5)
    print("Result of test check_if_all_items_have_property:", result)

    result = get_matching_items(object_list, 5)
    print("Number of items returned from test get_matching_items:", len(result))


main()

Ein voll funktionsfähiges Beispiel:

linear_search_variations.py
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
class AdventureObject:
    """ Class that defines an alien"""

    def __init__(self, description, room):
        """ Constructor. Set name and color"""
        self.description = description
        self.room = room


def check_if_one_item_is_in_room_v1(my_list, room):
    """
    Return true if at least one item has a
    property.
    """
    i = 0
    while i < len(my_list) and my_list[i].room != room:
        i += 1

    if i < len(my_list):
        # Found an item with the property
        return True
    else:
        # There is no item with the property
        return False


def check_if_one_item_is_in_room_v2(my_list, room):
    """
    Return true if at least one item has a
    property. Works the same as v1, but less code.
    """
    for item in my_list:
        if item.room == room:
            return True
    return False


def check_if_all_items_are_in_room(my_list, room):
    """
    Return true if at ALL items have a property.
    """
    for item in my_list:
        if item.room != room:
            return False
    return True


def get_items_in_room(my_list, room):
    """
    Build a brand new list that holds all the items
    that match our property.
    """
    matching_list = []
    for item in my_list:
        if item.room == room:
            matching_list.append(item)
    return matching_list


def main():
    object_list = []
    object_list.append(AdventureObject("Key", 5))
    object_list.append(AdventureObject("Bear", 5))
    object_list.append(AdventureObject("Food", 8))
    object_list.append(AdventureObject("Sword", 2))
    object_list.append(AdventureObject("Wand", 10))

    result = check_if_one_item_is_in_room_v1(object_list, 5)
    print("Result of test check_if_one_item_is_in_room_v1:", result)

    result = check_if_one_item_is_in_room_v2(object_list, 5)
    print("Result of test check_if_one_item_is_in_room_v2:", result)

    result = check_if_all_items_are_in_room(object_list, 5)
    print("Result of test check_if_all_items_are_in_room:", result)

    result = get_items_in_room(object_list, 5)
    print("Number of items returned from test get_items_in_room:", len(result))


main()

Diese Standardalgorithmen können als Teil einer Lösung für ein größeres Problem verwendet werden. Zum Beispiel, um alle Adressen in einer Liste von Kunden zu finden, die ungültig sind.