Unsere Datenschutzrichtlinie wird in Kürze aktualisiert. Bitte sehen Sie sich die Vorschau an.

Grundlagen der Programmierung: Datenstrukturen

Arrays durchsuchen

Testen Sie unsere 2016 Kurse

10 Tage kostenlos!

Jetzt testen Alle Abonnements anzeigen
Durchschnittliche Arrays können nur mit Hilfe einer sequenziellen Suche durchforstet werden. Das Problem dabei: Die Suche kann sehr langsam sein, wenn Sie größere Datenmengen durchsuchen müssen.

Transkript

Wie finden wir nun einen speziellen Eintrag in einem durchschnittlichen Array? Wenn es ein Array mit Integern ist, oder eins mit Zeichenketten oder mit was-auch-immer, und ich nichts anderes wissen will als ob ein bestimmter Eintrag existiert oder nicht. In sehr einfachen, rudimentären Arrays wie in C gibt's keine wie auch immer geartete Suchfunktionalität. Und wenn Sie tausend Elemente haben, wird's nicht leicht sein, etwas zu finden. Oder eine Index-Funktion. Die werden Sie nicht aufrufen können, weil es einfach keine gibt. Das einzige, was Sie tun können, und was auch sicher funktionieren wird: Sie müssen sich jeden Einträg händisch anschauen, um herauszufinden, wo er liegt. Wenn ich also wissen möchte, ob der Wert 99 irgendwo in einem Array mit Integer-Werten existiert, und bei dem jeder Wert an jeder beliebigen Position stehen könnte, würde ich versuchen, etwas wie diesen Pseudocode hier anzuwenden. Dabei setze ich einen initialen Indexwert auf Null und dann gehe ich in einer while-Schleife – Es könnte auch eine for-, eine for-each- oder eine do-Schleife sein, solange nur i niedriger ist als die Länge des Arrays. Wir kontrollieren jetzt also den Wert an der derzeitigen Position. Wir schauen nach, ob er 99 erreicht. Wenn er erreicht ist, bekommen wir wahr zurückgegeben, wenn nicht, addieren wir 1 und machen einfach weiter. Und das, bis wir entweder den gesuchten Wert finden und wahr ausgegeben bekommen, oder wir erreichen das Ende der Schleife, ohne dass dieser Wert gesehen wurde und wir falsch ausgegeben bekommen. In diesem Beispiel geht's nur darum, ob ein Wert vorhanden ist oder nicht. Existiert dieser Wert? Das beste, was wir hoffen können, ist dass der Wert als erstes oder zweites Element auftaucht. Es würde sofort wahr zurückgegeben und das war's dann. Wir müssen nicht weiter suchen. Im schlimmsten Fall taucht der Wert 99 nirgends auf. Wir würden dann jedes einzelne Element durchforsten. Egal, ob 100 Elemente oder eine Million, um herauszufinden, wo dieser Wert liegt. Jetzt haben wir diese Methode mit der linearen Suche, die auch als sequentielle Suche bezeichnet wird. Das ist eine sehr unelegante Gewaltmethode. Wir planen einfach alles zu durchforsten. Eins nach dem anderen. Von Anfang bis Ende. Lineare Suchen sind einfach zu verstehen. Und sie sind einfach zu schreiben. Und sie funktionieren auch. Sie sind lediglich sehr langsam. Je mehr Material Sie haben, um so langsamer wird's werden. Je größer die Anzahl der Elemente in einem Array wird, um so länger braucht auch die Suche. Wenn Ihnen die Landau-Schreibweise oder Landau-Komplexität vertraut ist, werden Sie wissen, was gemeint ist. Eine lineare Suche würde als O aus N bezeichnet werden oder als Ordnung-N-Komplexität. Das ist ein linearer Zeitalgorithmus mit der Bedeutung, dass sie in linearer Weise zunimmt, zusammen mit dem Größerwerden der Eingaben. Das bedeutet ganz einfach: Wenn wir die Anzahl der Elemente im Array verdoppeln, dann verdoppelt sich auch die Suchzeit. Wenn wir zehnmal so viele Elemente haben, wird die zehnfache Suchzeit erforderlich. Wir müssen das Schlimmste annehmen. Der Wert, nachdem wir suchen, existiert gar nicht oder es ist der allerletzte Wert. Aber wir müssen absolut alles durchsuchen, um genau das herausfinden zu können. Und wie wir gleich sehen werden, ist das genau die Art von Suche, die Sie verwenden, wenn Sie sich an die eingebaute Suchfunktion in einem Array oder sogar in jeder anderen Datenstruktur halten. Das ist genau die Art von Suche, die Sie verwenden, wenn Sie sich an die eingebaute Suchfunktion in einem Array oder sogar in jeder anderen Datenstruktur halten. Wenn Sie ein einfaches Array haben, egal, ob numerisch oder mit Textinhalt oder sogar mit eigenen Objekten, und das Element könnte in jeder Position innerhalb des Arrays sein, dann ist eine lineare Suche genau das, was Sie wollen. Dann gibt's vielleicht keine andere Option als die, alles zu durchforsten. Aber wenn es sich um geordnete Daten handelt, wenn es eine Art vorhersehbare Sequenz gibt, wo die Elemente in einer streng auf- oder absteigenden Ordnung liegen, dann gibt's viel bessere Optionen für das Suchen als die lineare Suche. Zum Beispiel die binäre Suche. Wenn Sie also nach Elementen innerhalb eines Arrays suchen müssen oder auch in anderen Datenstrukturen. Wenn das wichtig für Ihr Tun ist, dann ist eine gewisse Ordnung dieser Elemente mehr und mehr von Bedeutung. OK, werden Sie denken, dann sorgen wir dafür, dass all unsere Arrays sortiert sind. Dann sind sie einfacher zu durchsuchen. Fast. Hier ist das Problem. Wir haben bereits gesehen, dass der Wunsch, eine Datenstruktur zu sortieren, sehr rechenintensiv ist. Es ist sehr fordernd. Und wenn Sie große Datenmengen haben oder Daten, die sich oft ändern, dann gilt das nochmal mehr. Sie werden sich dann eher für eine langsame Suche entscheiden. Die einzige Art, dieses Problem zu lösen – alles sortiert zu halten wird so viele Leistungseinbußen mit sich bringen, dass es unrentabel ist. Das ist das Schwierige an der Arbeit mit Datenstrukturen. Sie können keine Datenstrukturen haben, die alle Situationen gut meistern.

Grundlagen der Programmierung: Datenstrukturen

Erhalten Sieeinen klaren Eindruck von Datenstrukturen und deren Eigenheiten und verstehen, wie Sie diese am besten einsetzen können – ganz unabhängig von den einzelnen Programmiersprachen.

2 Std. 51 min (29 Videos)
Derzeit sind keine Feedbacks vorhanden...
 

Dieser Online-Kurs ist als Download und als Streaming-Video verfügbar. Die gute Nachricht: Sie müssen sich nicht entscheiden - sobald Sie das Training erwerben, erhalten Sie Zugang zu beiden Optionen!

Der Download ermöglicht Ihnen die Offline-Nutzung des Trainings und bietet die Vorteile einer benutzerfreundlichen Abspielumgebung. Wenn Sie an verschiedenen Computern arbeiten, oder nicht den ganzen Kurs auf einmal herunterladen möchten, loggen Sie sich auf dieser Seite ein, um alle Videos des Trainings als Streaming-Video anzusehen.

Wir hoffen, dass Sie viel Freude und Erfolg mit diesem Video-Training haben werden. Falls Sie irgendwelche Fragen haben, zögern Sie nicht uns zu kontaktieren!