0 Daumen
848 Aufrufe
Guten Morgen,
folgende Frage habe ich gestellt bekommen:
"Nennen Sie einen Programmiertrick zur Vereinfachung der Abfragen bei der Suche nach einem bestimmten Eintrag in einer Liste."
Kenne allerdings kein Programmiertrick, was meint ihr?
Avatar von

Durchsuchen einer Liste nach einem bestimmten Eintrag ist so ziemlich das einfachste, was man mit einer Liste machen kann (mal abgesehen von den elementaren Operationen "Zum nächsten Element gehen", "Liste zerschneiden" und "Listen zusammenfügen").

Man könnte eine seperate Datenstruktur als Index verwenden. Zum Beispiel einen binären Suchbaum. Dadurch wird die Abfrage aber nicht einfacher, sondern eben nur schneller. Außerdem durchsucht man dann keine Liste mehr, sondern die separate Datenstruktur.

Es ist eine sehr unklar formulierte Frage.

Hallo oswald,

günstig ist es wenn die Datenstruktur bereits als array [ von .. bis ]
oder als array of pointer to Datenstruktur vorliegt

Den Quicksortalsuchgorithmus  hatte ich nur einmal allgmein programmiert und
dann die jeweilige Datenstruktur als Variable übergeben.

Das alles in Borland-Pascal und mit Objekten.

mfg Georg

> günstig ist es wenn die Datenstruktur bereits als array [ von .. bis ] oder als array of pointer to Datenstruktur vorliegt

Dann verliert man eine wesentliche Eigenschaft von Listen, nämlich dass neue Elemente an der aktuellen Position in konstanter Zeit eingefügt und entfernt werden können.

Soll der Trick wirklich daraus bestehen, keine Liste zu verwenden, sondern ein Array?

2 Antworten

0 Daumen

Ich gehe davon aus das Liste geordnet ist. Am besten aufsteigend.

Der schnellste Algorithmus ist so eine Art Quicksort-Abfrage.

Anfang = 0
ende = anzahl
Mitte =  [ anfang + ende] / 2

Du gehst zum  Listeneintrag [Mitte] und schaust nach ob der Wert deiner
Abfrage entspricht. Falls ja : Listeneintrag gefunden.

Ist der Listeneintrag [Mitte] < Abfragewert wiederholst du das Ganze mit
anfang = Mitte
ende = anzahl
Mitte =  [ anfang + ende] / 2

Ist der Listeneintrag [Mitte] > Abfragewert wiederholst du das Ganze mit
anfang = 0
ende = Mitte
Mitte =  [ anfang + ende] / 2

Dies ist die schnellste Methode zur Abfrage.

Avatar von

> Du gehst zum  Listeneintrag [Mitte]

Das geht bei einem Feld schnell. Bei einer Liste muss man sich dazu vom Anfang durch die Hälfte aller Listeneinträge bis zu Mitte entlanghangeln.

Das mache ich auch.

Anfang = 0
Anzahl = 120

Mitte = 60

Ich frage nur Feld [60] ab.

Nix hangeln.

Das hängt immer davon ab wie die Liste vorliegt. Möchte man einen Datensatz einer Festplatte lesen wäre es unklug wenn man dazu die Festplatte immer von ganz Vorne anfangen müsste zu lesen.

Es wäre also unklug eine einfach oder eine doppelt verkettete Liste nur in dieser Form vorliegen zu haben. Weiterhin ist so eine Liste meist nur nach einem Kriteriem sortiert. Also z.B. nach einer Nummer.

Ich denke wir müssen ersteinmal das Grundsätzliche klären.

ich habe unter " Liste " ein Feld ( array )  im Hauptspeicher verstanden.

Ein Feld, über eine Index-Nummer ansprechbar, hat für mich deutliche
Vorteile gegenüber völlig dynamischen Datenstrukturen gehabt.

Deshalb habe ich immer nur mit Feldern bzw mit Feldern von Zeigern gearbeitet.

Das Array of pointer hat als Grundstruktur nur wenig Speicherplatz eingenommen.
Die Belegung erfolgte dann dynamisch.

Die Suche nach einem Datensatz auf einer Festplatte kam bei mir nie vor.

> Ein Feld, über eine Index-Nummer ansprechbar, hat für mich deutliche  Vorteile gegenüber völlig dynamischen Datenstrukturen gehabt.

Das geht nicht nur dir so. Es ist oft der Fall, dass sich ein Feld über seine gesamte Lebenszeit gerechnet als effizienter erweist, als eine Liste. Auch dann wenn auf den ersten Blick eine Liste angesagt ist. Der wahlfreie Zugriff auf die Elemente anhand ihrer Position innerhalb der Datenstruktur ist ein Grund dafür, Lokalität ist ein anderer.

Allerdings würde ich dann nicht mehr von einer Liste sprechen, sondern eben von einem Feld. Eine Liste ist für mich definiert durch effizientes (= konstante Laufzeit) Einfügen und Enfernen an der aktuellen Position und effizientes Weitergehen zum nächsten Element. Ein Feld ist definiert durch Effizientes ansprechen jedes Elementes anhand seiner Position innerhalb des Feldes. Dann ist aber effizientes Einfügen und Enfernen an der aktuellen Position nicht mehr möglich, weil alle folgenden Einträge des Feldes nach hinten verschoben werden müssen um für das neue Element Platz zu schaffen.

Kann ich so nicht bestätigen.

Beispiel : ich arbeite also mit einem Zeigerfeld.

Ich verende einmal die Syntax von Borland Pascal / Delphi

Beim Löschen von feld [a] wird der Zeigereintrag mit dispose
gelöscht, dann wird mit move ( feld[a+1], feld[ende], Anzahl der Bytes )
ruckzuck das Zeigerfeld ein wenig am Block verschoben, feld[ende] wird
der Wert NIL  zugewiesen und ende = ende - 1 gesetzt.

Ein Einfügen an beliebiger Position geht genauso schnell.

mfg Georg

> dann wird mit move ( feld[a+1], feld[ende], Anzahl der Bytes ) ruckzuck das Zeigerfeld ein wenig am Block verschoben

Wie lange das dauert hängt davon ab, wie weit es von a bis ende ist. Es hat also keine konstante Laufzeit, wie ich das von Listen erwarte. Selbst dann wenn es praktisch gesehen ruckzuck geht.

0 Daumen

Damit Listen schnell nach bestimmten Einträgen durchsucht werden können müssen sie sortiert sein.

Nehmen wir man an du suchst alle Manfred's aus Paderborn. Warum ist das Telefonbuch evtl. für diese Suche nicht geeignet selbst wenn tatsächlich alle Manfred's aus Paderborn darin gelistet wären.

Geschickt wäre auch noch wenn man die Suchmänge in jedem Schritt halbieren könnte.

Wenn ich mir also das Mittlere Element einer sortierten Liste heraus picke und mich Fragen kann ob Manfred aus Paderborn vor oder hinter diesem Eintrag kommt.

Avatar von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community