Artikel pedia
| Home | Kontakt | Artikel einreichen | Oberseite 50 artikel | Oberseite 50 autors
 
 


Artikel kategorien
Letztes fugte hinzu
    Ms-access

   Instrumentation + schnittstellen

   Pc tuning - volle kraft voraus für ihr system

   Informatorische grundlagen

   Javascript

   Interne sortieralgorithmen - der kern der sache

   Plotter und sonstige drucker

   Frage 20 (rössl priska)

   Internet - programmierung

   Monitore

   Semesterarbeit und spezialgebiet für informatik

   Erörterungs zum thema

   Inhaltsverzeichnis

   Einführung in die entwicklung ganzheitlicher informationssysteme:

   Titel dokument
alle kategorien




  Suchen (searching)



Suchen (Searching) Das Suchen verkörpert die meistbenutzte Operation neben dem Anlegen. Sogar das Löschen ist eine Erweiterung des Suchens, denn bevor etwas gelöscht werden kann, muß es erst einmal gefunden werden. Zur Erklärung der Punkte Sequentielles und Binäres Suchen sei als Beispiel die Sozielversicherungsnummer angeführt. Sie hat insgesamt 12 Stellen. Die ersten 4 sind ein Code, die nachfolgenden 6 das Geburtsdatum im Format <TT:MM:JJ>   Wir unterscheiden Arrays (sortiert, unsortiert) und Bäume.   Das Suchen in Arrays Das Sequentielle Suchen Bei diesem Suchverfahren wird jedes Feld des Arrays nacheinander durchgelaufen, bis das entsprechende Feld gefunden ist.

Im Durchschnitt benötigt man dafür N/2 Operationen. Best Case: das Erste Feld entspricht der gesuchten Sozialversicherungsnummer. Worst Case: Das n-te Feld entspricht der gesuchten Sozialversicherungsnummer. Eine neues Feld wird am Ende des Arrays angefügt (n+1).  3502 120456    n Felder 7113 031291         Für den hohen Durchschnitt der benötigten Operationen, die man bis zum Finden der gesuchten Sozialversicherungsnummer braucht (8 Mio Felder), ist das Sequentielles Suchen nicht gerade zweckführend. Eine andere Möglichkeit des Suchens ist   Das Binäre Suchen Bei unserem zweiten Versuch ist ein sortiertes Array vorliegend, d.

h. die Felder sind aufsteigend sortiert. Man nennt das auch ein sortiertes Array. Neue Felder werden am Ende der Liste angefügt, unabhängig davon, ob es sich um eine Neugeburt oder um einen Zuwanderer handelt. Siehe auch Kapitel Indexreorganisation.   Funktion: Beim Binären Suchen wird die Anzahl der Felder immer weiter halbiert.

Dadurch gelangt man viel schneller zum gesuchten Feld gegenüber dem Sequentiellen Suchen, da sich die Menge der zu suchenen Felder systematisch verkleinert. Bei 8 Mio. Felder entspricht das 23 Suchschritten. 3502 120456 7113 031291        4 Mio immer weiter halbieren        n-1 -tes Feld    n-tes Feld         Frage: Wie oft kann man n Felder halbieren? -> ld n   2^x = 8 Mio x = ld 8 Mio x » 23   Average Case entspricht ungefähr dem Worst Case beim Binären Suchen (=2^x).   Indexreorganisation Beim Binären Suchen ist das Einfügen teurer als bei der Sequentiellen Sortierung, da die Reihenfolge erhalten werden muß. Angenommen im Laufe eines Tages werden zu den 8 Mio.

Feldern 30 neue hinzugefügt, so dauert die Suche der zuletzt angefügten Felder am Längsten. Das kommt daher, da zwar die ersten 8 Mio. Felder binär in 23 Schritten durchlaufen, die neu angefügten 30 Felder aber sequentiell im Worst Case bis zu 30 Mal zusätzlich abgeklappert werden. Indexreorganisation wird meistens über Nacht oder zu Zeiten geringer Abfragen durchgeführt.  Gestaltung einer Baumstruktur aufgrund einer Reihenfolge Bäume   (15,8,12,21,30,14,16) 15      8 21    12 30     14       Knoten und Tiefen                 Knoten 1 3 7 Tiefe 0 1 2 Baum b.B.

b.B. balancierter Baum     Anmerkung: balancierter Baum: kurzes Suchen unbalancierter Baum: langes Suchen (bei vorsortierten Daten) 2^(T+1) = K+1 T-1 = ld (K+1) -1 T= ld (K+1)-1   AVL Baum Erfunden von drei russischen Mathematikern (AVL steht für die drei Anfangsbuchstaben der Nachnamen der Mathematiker). Ein AVL Baum ist ein Baum, bei dem jeder einzelne Knoten eine Tiefendifferenz von ±1 hat.   Degenerierter Baum Bei einem Degenerierten Baum ist die Struktur vollig unbalanciert. Jeder Knoten hat nur rechte bzw.

linke Nachfoger. Beispiel: das Wort W-U-R-M-L-I-E-D ist degeneriert. Aber auch: S-O-N-N-I-GW  S    U  O  R  N    M  N  L  I    I  G  E      D   Baum Beim 2-3-4 Baum hat man nmax 3 Zahlen, die daraus folgend in maximal 4 Einteilungen unterteilt werden können.    8 13 70          >= 70 <= 8  14-70 9-13         Lazy Deletion Ausgehend von der Grundlage, kleinere Kinder eines Knotens werden linke, größere jeweils rechts angeornet, ergibt sich folgendes Verfahren zum füllen der Lücke, an der ein Knoten gelöscht wurde. An Stelle des gelöschten Knotens können nur die Schwarz markierten Knoten stehen.         DELETE                             HASHING Operatoren beim Suchen: -MINMAX -MERGE (verschmelzen)  Beim Hashing gibt es nicht eine große, sondern viele kleine Suchstrukturen.




Ein Beispiel wäre 26 (26 Buchstaben im Alphabet) Schülertabellen anzulegen.   Allgemein: Bevor man eine Strukur entwickelt entschließt man sich für eine der folgenden Operationsgruppen:   nur Hinzufügen & Löschen oder MINMAX & Löschenandere Ansätze: h1 erster Buchstabe h2 letzter Buchstabe h3 länge des Namens  Ziel des Hashings ist es, gleichmäßige Hashfunktionen zu finden. Einzelstruktur = Bucket (engl. Kübel)  Hashfunktion h(Pk...

Primary key) Mittels eines Algorithmuses wird bestimmt, wo das Objekt eingeordnet wird. Der Algorithmus muß so aufgebaut sein, das die Verteilung gleichmäßig erfolgt. Der ASCII- Zeichensatz ist dabei ein erster Ansatz. Das Wort <R-O-T> besteht aus den drei unterschiedlichen Zeichencodes 200, 170 und 150. Man summiert die drei Codes, dividiert durch die Anzahl der Buchstaben im Alphabet (26!) und erhält einen Rest (modulo).Das Verfahren ist aber nur dann optimal, wenn es mit 10 Datensätzen pro Bucket gefahren wird.

Die Suche innerhalb des Buckets ist ein Array oder einfach eine verkettet Liste (Separate Chaining).    Verkettete Liste             Linear Probing Bei der Methode des Linear Probing verwenden wir pro Bucket einen Datensatz.. . . .

. . h1 (Österreicher 3) h1 (Österreicher 1) 14730                                   Was geschieht aber, wenn durch das Linear Probing ein Österreicher in ein Feld geschoben werden mußm daß schon besetzt ist? Die Lösung sind verschiedene Schrittweiten z.B. 2 Funktionen, auch genannt Double Hashing (gleichmäßigere Vererbung). Die Vorraussetzung für dieses Verfahren ist, daß es mehr Buckets als Datensätze geben muß.

Indirektes Suchen (Indirect Search) (vgl. Buchindex am Ende eines Buches = Sortierte Datenstruktur mit einem Pointer auf Seiten)  4205 3113 5602 2814 2020 2060 3040 PAUER 5602 Adr ... SCHELLNER 5602 Adr ..

. XXX ... ..

. PAUER 2020 SCHELLNER 2060 INDEX 3060 3080                                                           INDEX= Für jedes Suchkriterium ein eigener Hilfsbaum (für schnelle Rückantwort) für langsame Rückantwort Þ sequentiell Statt dem Baum kann man auch eine geordnete Liste erstellen.                           Sortieralgorithmen Parameter der Leistungsfähigkeit   Laufzeit: ist die Zeit, die ein Algorithmus dazu benötigt eine Anzahl von n Elementen zu sortieren. Stabilität: Ein Sortierverfahren wird stabil genannt, wenn es die Reihenfolge gleicher Schlüssel in der Datei beibehält, z.B. eine Menge von Schülern wird nach Noten (Schlüssel) sortiert.

Bei einer stabilen Methode sind die Schüler noch immer in alphabetischer Reihenfolge in der Liste angeführt; bei einer instabilen ist von einer alphabetischen Reihenfolge keine Rede mehr.   Insertion Sort Eine unsortierte bestehende Liste wird systematisch vom Anfang weg sortiert, indem die nächstkleinere Zahl links, die nächstgrößere Zahl rechts eingeordnet wird. Der Insertion Sort ist sehr langsam, da nur benachbarte Elemente ausgetauscht werden.    43 5 18 30 19               Selection Sort = Sortieren durch direktes Auswählen.  Der Selection Sort sucht aus einem Feld das kleinste Element und tauscht es gegen das an erster Stelle stehende Element. Dann wird das zweitkleinste Element gesucht und gegen das an zweiter Stelle stehende Element getauscht, u.

sw. bis das gesamte Feld sortiert ist.   1. Durchgang ³ 5 9 7 ¬ 6 3 2. Durchgang 1 ° 9 7 8 6 ® 3. Durchgang 1 3 ´ 7 8 6 ° 4.

Durchgang 1 3 5 ² 8 ± 9 5. Durchgang 1 3 5 6 ³ ² 9 6. Durchgang 1 3 5 6 7 8 9   Bubble Sort =Sortieren durch direktes Austauschen  Beim durchlaufen der Datei werden jeweils 2 Elemente paarweise verglichen. Wenn dabei das linke Element kleiner ist als das rechte, wird es vertauscht, wenn nicht, wird weitergegangen, bis das rechte Ende des Feldes erreicht ist.   Indirect Sort Beim Insertion Sort sortiert man einen Index auf die Tabelle.     Shell Sort Der Shell Sort stellt das schnellste Sortierverfahren dar, wobei niemand weiß wieso.

Es ist auch das einzige Sortierverfahren, das sich Mathematisch nicht erklären läßt und in keine Formel packen läßt.   Der Insertion Sort ist sehr langsam, weil nur benachbarte Elemente ausgetauscht werden. Wenn sich zum Beispiel das kleinste Element zufällig am Ende des Feldes befindet, so werden n Schritte benötigt, um es dorthin zu bekommen, wo es hingehört. Shellsort ist einfach eine Erweiterung von Insertion Sort, bei dem eine Erhöhung der Geschwindigkeit dadurch erzielt wird, daß ein Vertauschen von Elementen ermöglicht wird, die weit voneinander entfernt sind.   Es wird eine Schrittreihenfolge gewählt (z.B.

13-h). Vom Ersten Element ausgehend wird jedes h-te Element herausgenommen und in die richtige Reihenfolge gebracht. Dieser Vorgang wird mit jedem Element durchgeführt bis man am Ende angelangt ist. Dann wird eine neue Schrittreihenfolge gewählt (kleiner als die erste z.B.: 5-h) und der Prozeß beginnt von vorne.

  Aus Versuchsreihen hat es sich herausgestellt, daß die Distanzen 1,4,13,40,121,... (3n+1) das schnellste Sortierverfahren darstellen. Es ist allerdings möglich, den Shellsort mit anderen Folgen von Distanzen noch effizienter zu machen. Doch es ist für relativ große n schwer, das Programm um mehr als 20% schneller zu machen.

  Quick Sort > 1000 <= 1000 =rennt rekursiv durch      1.)    Quick Sort  Quick Sort    Partitionselement gew. Zahl = 1000        2.)  36 36    212 212    Wenn unsortiert, rennen die Pointer unterschiedlich langsam (bei wenigen Elementen). Beim Quick Sort werden die 2 Teilfelder getrennt durchgegangen. Der linke Teil von links nach rechts, der rechte Teil von rechts nach links.

Es wird immer dann unterbrochen, wenn ein Element kleiner ist als das Partitionselement ist. Wenn die beiden im Diagramm kleinen, nach oben zeigenden Pfeile stehengeblieben sind, werden die zwei Elemente vertauscht.   Der Nachteil des Quick Sort besteht darin, daß er rekursiv und störanfällig ist und daß er im Worst Case n² Operationen benötigt.   Distribution Counting Eine sehr spezielle Situation, für die ein einfacher Sortieralgorithmus existiert, wenn eine Datei mit n Datensätzen viele verschiedene Zahlenschlüssel hat. Die Idee besteht darin, die Anzahl der Schlüssel mit jedem Wert zu ermitteln und dann die Ergebnisse der Zählung zu verwenden, um bei einem zweiten Durchlauf durch die Datei die Datensätze in die richtige Postition zu bringen.  

Suchen artikel im kategorien
Schlüsselwort
  
Kategorien
  
  
   Zusammenfassung Der Vorleser

   sachtextanalyse

   interpretation zwist

   Fabel interpretation

   literarische charakteristik

   interpretation bender heimkehr

   felix lateinbuch

   interpretation der taucher von schiller

   textbeschreibung

   charakterisierung eduard selicke


Anmerkungen:

* Name:

* Email:

URL:


* Diskussion: (NO HTML)




| impressum | datenschutz

© Copyright Artikelpedia.com