Einen Datenbestand durchsuchen

Manuelle Suche in einem ungeordneten bzw. geordneten Datenbestand

Umfangreiche Datenbestände gibt es in Hülle und Fülle. Oft steht man vor dem Problem, nach einem bestimmten Datensatz im gegebenen Datenbestand zu suchen.

Wir spielen das im Folgenden hier einmal durch. Gegeben ist eine Datei mit Adressen von Personen.

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
...

Beachte, dass die Adressen hier Pseudo-Adressen sind. Die Personen gibt es in der Wirklichkeit nicht. Auch die Straßenangaben gibt es (in der Regel) in den betreffenden Orten nicht.

Aufgabe 1

(a) Lade die Adressdatei adressdaten.csv herunter und öffne sie mit einem Texteditor.

Suche jetzt den Datensatz zur Person "Katja Herrmann aus Queidersbach". Eine vom Texteditor zur Verfügung gestellte Suchfunktion darfst du natürlich nicht benutzen.

(b) Lade auch die sortierte Datei adressdaten_sortiert_name.csv herunter und öffne sie mit einem Texteditor.

Suche jetzt nochmal den Datensatz zur Person "Katja Herrmann aus Queidersbach". Warum fällt einem die Suche jetzt viel leichter?

(c) Begründe, warum man gerade bei großen Datenbeständen Operationen benötigt, die die Datensätze nach bestimmten Kriterien sortiert anordnen.

Algorithmische Suche in einem ungeordneten Datenbestand

Umfangreiche Datenbestände werden heute in der Regel automatisiert verarbeit. Wir spielen auch diese Situation hier durch. Zur Vereinfachung der Darstellung und Vorgehensweise betrachten wir im Folgenden nur einen Auszug aus dem größeren Datenbestand und setzen voraus, dass die Daten in Listenform vorliegen. Wir betrachten zunächst einen ungeordneten Datenbestand.

listeDaten = [
    ('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'),
    ('Bergmann', 'Laura', 'Schmarjestrasse 76', '93497', 'Willmering'),
    ('Schulz', 'Alexander', 'Anhalter Strasse 45', '67744', 'Seelen'),
    ('Kortig', 'Stefanie', 'Mühlenstrasse 76', '97201', 'Höchberg'),
    ('Nussbaum', 'Florian', 'Kurfürstendamm 56', '08004', 'Zwickau'),
    ('Gruenewald', 'Marco', 'Nuernbergerstrasse 15', '26386', 'Wilhelmshaven'),
    ('Reinhard', 'Kevin', 'An Der Urania 15', '25856', 'Hattstedt'),
    ('Mahler', 'Sophia', 'Charlottenstrasse 87', '01463', 'Langebrück'),
    ('Loewe', 'Ulrike', 'Messedamm 69', '06054', 'Halle'),
    ('Keller', 'Christina', 'Alt Reinickendorf 24', '87542', 'Blaichach'),
    ('Frey', 'Kristian', 'Hans-Grade-Allee 7', '24870', 'Ellingstedt')
    ]

Aufgabe 2

(a) Entwickle einen Algorithmus, mit dem man in der gezeigten Datenliste nach einer Person mit einem vorgegebenen Nachnamen suchen kann.

Wenn der übergebene Name in der Datenliste vorkommt, dann soll der Index des zugehörigen Datensatzes zurückgegeben werden. Kommt der Name mehrfach vor, dann soll der Index des ersten passenden Datensatzes zurückgegeben werden. Kommt der Name in der Datenliste nicht vor, dann soll der Index -1 zurückgegeben werden.

(b) Implementiere den Algorithmus und teste ihn.

Algorithmische Suche in einem geordneten Datenbestand

Der Datenbestand soll jetzt in einer geordneten Form vorliegen (hier: alphabetische Sortierung nach dem Nachnamen).

listeDaten = [
    ('Bergmann', 'Laura', 'Schmarjestrasse 76', '93497', 'Willmering'),
    ('Brandt', 'Mandy', 'Scharnweberstrasse 84', '68199', 'Mannheim Almenhof'),
    ('Ebersbacher', 'Michelle', 'Alt-Moabit 10', '06691', 'Zeitz'),
    ('Frey', 'Kristian', 'Hans-Grade-Allee 7', '24870', 'Ellingstedt'),
    ('Gruenewald', 'Marco', 'Nuernbergerstrasse 15', '26386', 'Wilhelmshaven'),
    ('Herzog', 'Marco', 'Scharnweberstrasse 90', '61130', 'Nidderau'),
    ('Keller', 'Christina', 'Alt Reinickendorf 24', '87542', 'Blaichach'),
    ('Koertig', 'Christine', 'Hardenbergstraße 82', '66887', 'Niederalben'),
    ('Kortig', 'Stefanie', 'Mühlenstrasse 76', '97201', 'Höchberg'),
    ('Krause', 'Stefanie', 'Brandenburgische Str. 20', '74343', 'Sachsenheim'),
    ('Loewe', 'Ulrike', 'Messedamm 69', '06054', 'Halle'),
    ('Mahler', 'Sophia', 'Charlottenstrasse 87', '01463', 'Langebrück'),
    ('Meister', 'Stephan', 'Fasanenstrasse 17', '22605', 'Hamburg Othmarschen'),
    ('Möller', 'Jens', 'Schoenebergerstrasse 47', '08313', 'Bernsbach'),
    ('Nussbaum', 'Florian', 'Kurfürstendamm 56', '08004', 'Zwickau'),
    ('Reinhard', 'Kevin', 'An Der Urania 15', '25856', 'Hattstedt'),
    ('Schmidt', 'Vanessa', 'Paderborner Strasse 44', '86359', 'Gersthofen'),
    ('Schmitz', 'Andreas', 'Meininger Strasse 84', '66539', 'Neunkirchen Ludwigsthal'),
    ('Schreiber', 'Barbara', 'Stresemannstr. 56', '66592', 'St Wendel'),
    ('Schulz', 'Alexander', 'Anhalter Strasse 45', '67744', 'Seelen')
    ]

Aufgabe 3

(a) Betrachte verschiedene Szenarien. Wann kann man jeweils die Suche abbrechen, wenn man die Daten des Datenbestandes der Reihe nach durchläuft?

(b) Passe den Suchalgorithmus entsprechend an. Implementiere und teste ihn anschließend.

Aufgabe 4

Die folgende (in Python implementierte) Funktion benutzt ein Suchverfahren, das den Namen "binäre Suche" hat.

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

(a) Beschreibe den hier zu Grunde liegenden Algorithmus in eigenen Worten. Verdeutliche ihn auch anhand von Beispielen.

(b) Teste die Funktion mit dem oben gegebenen Datenbestand.