Suchen und Sortieren

Weiter zu Binäre Suche

Direkt zu Sortieren

Das Ziel einer Suche ist es, in einer grossen Datenmenge möglichst schnell das gesuchte Element zu finden. Beispielsweise suchen wir in einem Lexikon oder Wörterbuch den Eintrag zu einem Begriff, im Telefonbuch die Nummer einer Person oder eines Geschäfts. Heutzutage suchen wir zumeist im Internet - aber wie schafft es dict.leo.org einen Suchbegriff innert Millisekunden zu finden? Wie findet tel.search.ch den richtigen Eintrag?

Gäb si mir wenigschtens d Vorwahl
Per favore
De gäbs nume no zäh Millione Kombinatione, ja
079 het si gseit
„Du weisch immer no nüt“, het si gseit
Nidmau tschüss het si gseit, ey
Und i frage si ob ig ihri - tüt tüt tüt het si gseit, tüt tüt 079 by Lo & Leduc

Der Sänger von 079 will die Telefonnummer der Angebeteten unter allen möglichen Schweizer Mobilfunknummern (10-stellig) mit dem Präfix 079 herausfinden. Dafür probiert er sämtliche Nummern von 079 000 00 00 bis 079 999 99 99 durch, was natürlich ziemlich lange dauert…

Tipp: Höre oder lese den Liedtext genau (Original, Hochdeutsch, Youtube)!

1. Wie viele Telefonnummern muss der Sänger von 079 durchprobieren?
2. Wie lange dauert das Probieren einer Telefonnummer?
3. Wie lange dauert die Suche nach der richtigen Nummer bei 079?
4. Wieso dauert es so lange? Was ist die Rechnung, die hinter der genannten Dauer steckt?
5. Wie lange dauerte die Suche, wenn wir nicht einmal die Vorwahl kennen würden (aber wüssten, dass alle Nummern mit 0 beginnen)?

Der einfachste Such-Algorithmus probiert alle Telefonnummern von der kleinsten zur grössten durch. Die Zeit für die Suche steigt proportional mit der Anzahl möglichen Nummern an - wir sagen auch, dass die Zeit linear mit der Grösse des Suchbereichs wächst, und sprechen von Linearer Suche.

Würden wir statt 079 nicht einmal die Vorwahl kennen, wäre die Suche nochmals zwei Dezimalstellen länger (wenn alle Telefonnummern mit 0 beginnen). Wir müssten also statt 6.5 sogar über 600 Jahre suchen.

Betrachte folgenden Datensatz mit Namen und Telefonnummern. Wir haben zwei parallele Listen, die erste mit Namen, die zweite mit den dazugehörigen Telefonnummern.

Zum Beispiel ist die Telefonnummer von Anela 0790000001.

lineare_suche.py

names = ['Aja', 'Anela', 'Arwen', 'Isra',
         'Juno', 'Kaida', 'Loelia', 'Luna',
         'Lumiel', 'Lyanna', 'Meyra', 'Miriel',
         'Narcissa', 'Nisha', 'Runa', 'Yuna']
numbers = ['0790000000', '0790000001', '00790000002', '0790000003',
           '0790000004', '0790000005', '0790000006', '0790000007',
           '0790000008', '0790000009', '0790000010', '0790000011',
           '0790000012', '0790000013', '0790000014', '0790000015']

1. Schreibe eine Python-Funktion linear_search(l, v). Die Funktion soll in der Liste l nach dem Wert v suchen. Falls er gefunden wird, soll die Position (Index) des Elements in der Liste zurückgegeben werden (nicht geprintet!).
2. Test: Der Funktionsaufruf print(linear_search(names, 'Anela')) soll $1$ ausgeben.
3. Nun wissen wir, dass die gesuchte Dame Lyanna (die Geheimnisvolle) heisst. Nutze nun diese Funktion, um die Telefonnummer von 'Lyanna' zu ermitteln.

Achtung: Generell bei solchen Aufgaben gilt: Verwende keine vordefinierten Suchfunktionen. Es geht genau darum, dass du diese selbst programmierst.

Tipps (zuerst ohne Tipps versuchen!)

Für das kleine Telefonbuch oben ist es nicht so wichtig, wie schnell der Such-Algorithmus ist. Was aber, wenn wir wirklich alle 10 Millionen Kombinationen durchprobieren?

Für diese Aufgabe benötigst du zusätzlich eine weitere Python-Datei, null79.py, die wir in unserem selbstgeschriebenen Code importieren. Dazu verwenden wir ähnlich wie zu Turtle-Zeiten das Schlüsselwort import:

from null79 import names, numbers

Damit das funktioniert, muss die Datei null79.py im gleichen Ordner gespeichert sein, wie unser selbstgeschriebener Code.

Am einfachsten geht das mit diesem WebtigerPython-Link - die Datei ist hier bereits hinterlegt.

Lade die Datei null79.py herunter und speichere sie im selben Verzeichnis wie dein Code.

Du kannst das Telefonbuch wie folgt importieren und den Namen für eine Telefonnummer herausfinden. Der Code muss im gleichen Ordner wie null79.py abgespeichert werden!

from null79 import names, numbers
 
index = 42
name = names[index]
telnr = numbers[index]
print("Die Telefonnummer von " + name + " ist " + telnr)

Verwende deine linear_search() Funktion, um die richtige Telefonnummer von Lyanna herauszufinden. Wie lange dauert die Suche?

Wir möchten genau wissen, wie lange die Suche dauert, auch wenn es hoffentlich nicht 6.5 Jahre sind.

Um in Python die Zeit zu stoppen, kannst du das time Modul verwenden. Wie lange dauert die Suche für die Lyanna? Wie lange für Annina? Weshalb der Unterschied?

import time
start = time.time()
# do something
elapsed = time.time() - start
print("do something took " + str(elapsed) + "s")

Finde heraus, wem die Telefonnummer 0791234567 gehört.

Lösung

Wenn wir nach einem Namen suchen, der gar nicht in der Liste vorkommt, z.B. Alaska, so dauert die Suche lange, weil die ganze Liste durchsucht wird.

Nun sind die Namen in null79.names alphabetisch sortiert. Sobald wir einen Namen antreffen, der alphabetisch nach dem gesuchten Wert liegt, können wir die Suche abbrechen. Strings können in Python mit den > und < Operatoren verglichen werden:

s1 = 'Alaska'
s2 = 'Alberta'
if s1 < s2:
    print(s1 + ' liegt im Alphabet vor ' + s2)
else:
    print(s1 + ' liegt im Alphabet nach ' + s2)

Erweitere deine Funktion linear_search() wie folgt:

• Füge einen Parameter mit Default-Argument is_sorted=False hinzu.
• Wenn die Liste nicht sortiert ist, soll die Suche wie bisher ablaufen.
• Ist die Liste sortiert, soll die Suche abbrechen, wenn wir im Alphabet bereits weiter sind als der gesuchte Wert.

Hast du eine Idee für einen besseren, sprich effizienteren Suchalgorithmus einer bereits sortierten Liste? Bespreche mit der Lehrperson und implementiere danach in Python.

Weiter zu Binäre Suche