Anwendung der Suchalgorithmen

Zielsetzung

Bei der Entwicklung von Suchalgorithmen haben wir bisher Zahlen als einfachste sortierbare Daten betrachtet. Bei realen Anwendungen hat man es meist mit komplexeren Datensätzen zu tun, die aus verschiedensten Daten bestehen. So könnte eine Datei mit Adressdaten wie den folgenden gegeben sein, die nach einem bestimmten Kriterium (z.B. dem Nachnamen) sortiert werden soll.

Krause,Stefanie,Brandenburgische Str. 20,74343,Sachsenheim
Brandt,Mandy,Scharnweberstrasse 84,68199,Mannheim Almenhof
Möller,Jens,Schoenebergerstrasse 47,08313,Bernsbach
Herzog,Marco,Scharnweberstrasse 90,61130,Nidderau
Schmitz,Andreas,Meininger Strasse 84,66539,Neunkirchen Ludwigsthal
Ebersbacher,Michelle,Alt-Moabit 10,06691,Zeitz
Koertig,Christine,Hardenbergstraße 82,66887,Niederalben
Schmidt,Vanessa,Paderborner Strasse 44,86359,Gersthofen
Meister,Stephan,Fasanenstrasse 17,22605,Hamburg Othmarschen
Schreiber,Barbara,Stresemannstr. 56,66592,St Wendel
...

Download: Datenbestand unsortiert: adressdaten.csv

Download: Datenbestand nach Name sortiert: adressdaten.csv

Ziel ist es, ein gegebenes Suchprogramm so anzupassen, dass man beim vorliegenden Datenbestand benutzen kann.

Ein gegebenes Suchprogramm

Wir gehen von einem getesteten Programm zum Suchen in einer Liste mit Zahlen aus. Im vorliegenden Fall handelt es sich um eine Implementierung der binären Suche

# binäre Suche
def suchen(name, liste):
    indexErgebnis = -1
    gefunden = False
    links = 0
    rechts = len(liste)-1
    while not gefunden and links <= rechts:
        mitte = (links + rechts) // 2
        if name == liste[mitte][0]:
            gefunden = True
            indexErgebnis = mitte
        elif name < liste[mitte][0]:
            rechts = mitte-1
        else:
            links = mitte+1
    return indexErgebnis

Aufgabe 1

Teste das gegebene Suchprogramm mit geeigneten Testdaten.

Anpassung des Suchprogramms

Wir gehen nach wie vor davon aus, dass die Daten in der oben gezeigten Weise in einer Datei vorliegen.

Bevor der gegebene Suchalgorithmus auf diesen Daten operieren kann, müssen die Daten zunächst in eine Listenform überführt werden.

[
('Krause','Stefanie','Brandenburgische Str. 20','74343,Sachsenheim'),
('Brandt','Mandy','Scharnweberstrasse 84','68199','Mannheim Almenhof'),
('Möller','Jens','Schoenebergerstrasse 47','08313,Bernsbach'),
...
]

Diese Datentransformationen können mit Funktionen des Python-Programms listenoperationen_zum_laden_und_speichern.py durchgeführt werden:

Wenn man jetzt das oben gezeigte Suchprogramm anwenden möchte, muss man auf die vorgegebenen Funktionen zur Datentransformation zurückgreifen und den Vergleich der Datenobjekte anpassen. Der folgende Quelltext zeigt, wie das geht.

from listenoperationen_zum_laden_und_speichern import *

# binäre Suche
def suchen(name, liste):
    indexErgebnis = -1
    gefunden = False
    links = 0
    rechts = len(liste)-1
    while not gefunden and links <= rechts:
        mitte = (links + rechts) // 2
        if name == liste[mitte][0]:
            gefunden = True
            indexErgebnis = mitte
        elif name < liste[mitte][0]:
            rechts = mitte-1
        else:
            links = mitte+1
    return indexErgebnis

# Test
text = textAusDatei('adressdaten_sortiert_name.csv')
listeDaten = tupelListeAusText(text)
index = suchen('Schmitt', listeDaten)
print(index)

Aufgabe 2

Teste das angepasste Suchprogramm. Beachte, dass die Dateien listenoperationen_zum_laden_und_speichern.py und adressdaten_sortiert_name.csv im selben Verzeichnis wie das Programm vorliegen müssen.

Aufgabe 3

Passe analog ein Programm zur linearen Suche in einer Zahlenliste an die vorliegende Situation mit komplexen Datensätzen an. Teste mit derselben Datenbasis wie bei der binären Suche. Eventuell muss du etwas Geduld bei der Ausführung des angepassten Programms haben. Erkläre, woran das liegt. (Hinweis: Zum Vorabtesten kann man kleinere Datenbestände benutzen.)