0 Daumen
184 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?
Gefragt 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.

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

Beantwortet von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage sofort und kostenfrei

x
Made by a lovely community
...