Stefan Bosse - Algorithmen und Datenstrukturen - Modul H Tabellen ::

Tabellen

Überblick in die Einführung einfachster Abstrakter Datentypen mit Tabellen:

1. Lineare Arrays als Datenstrukturen
2. Der Stapelspeicher (LIFO)
3. Die Warteschlange (FIFO)
4. Die Hashtabelle

Stefan Bosse - Algorithmen und Datenstrukturen - Modul H Tabellen :: Lineare Arrays

Lineare Arrays

Ein Array ist eine Tabelle mit einer Spalte und n Zeilen.

• Ein Array ist eine monosortige lineare Folge von Werten und somit Speicherzellen.
  • Jede Speicherzelle hat den gleichen Datentpy, z.B. skalare Werte wie Ganzzahlen, aber acuh Datenstrukturen
  • Die Größe des Arrays ist fest (n)
  • Jede Zelle eines Arrays wird über einen eindeutigen Index adressiert, i.A. immer mit 0 beginnend (erstes Element) bis n-1 (letztes Element):

$${T}={\left(\matrix{{v}_{{0}}\\{v}_{{1}}\\..\\{v}_{{{n}-{1}}}}\right)}\\ {A}{d}{d}{r}={I}{\left({T}\right)}={\left\lbrace{0},{1},{2},..,{n}-{1}\right\rbrace}$$

Stefan Bosse - Algorithmen und Datenstrukturen - Modul H Tabellen :: Lineare Arrays

Operationen

1. Elementare (eingbaute) Operationen:

   • Lesen eines Elements T[index]
   • Schreiben eines Elements T[index]=ε
   • RAM Modell: freier Indexzugriff in beliebiger Reihenfolge!

2. Abstrakte Operationen:

   • Suche: Suche den Index eines Elementwertes
   • Sortieren: Sortieren der Werte in einer definierten Reihenfolge
   • usw.

3. Linear Arrays = Mathematische Vektoren
   • Numerik
   • Vektorarithmetik

Stefan Bosse - Algorithmen und Datenstrukturen - Modul H Tabellen :: Lineare Arrays

Schlüssel-Wert Paare

Der Index einer Tabelle ist ein Schlüssel zur Erlangung eines Werts. So könnte man numerischen Indexwerten eine Zecihenkette zuordnen.

T=['Zero','One','Two']
print(T[0])

Schlüssel-Wert Paare für Lookup-Tabellen

• Der große Vorteil: "Suchzeit", d.h. Abbildung eines Schlüssels (Index) auf einen Wert geschieht in konstanter Laufzeit O(1)!

• Der große Nachteil: Die Schlüsselfolge ist fest vorgegeben und startet bei 0. Bei dünn besetzten Schlüsselmengen bräuchte man dünnbesetzte riesig Tabellen!

  • Daher werden noch kompaktere Hashtabellen eingeführt.

Stefan Bosse - Algorithmen und Datenstrukturen - Modul H Tabellen :: Lineare Arrays

• Lineare Tabellen verwenden eine lineare Suchfunktion für Schlüssel, i.A. i=H(k)=k
• Hashtabellen verwenden eine "andere" Suchfunktion H(k) die beliebige Schlüsselverteilungen (theoretisch) auf einen Index i abbilden.

          ┌――――┐ 0                       ┌――――┐        
k=0 ――――▶ │ a  │   ――――▶ a  k=10――――▶H(k)│ a  │ ――――▶ a
          ├――――┤ 1                       ├――――┤        
k=1 ――――▶ │ b  │   ――――▶ b               │ f  │        
          ├――――┤ 2                       ├――――┤        
          │ c  │            k=2 ――――▶H(k)│ e  │ ――――▶ e
          ├――――┤ 3                       ├――――┤        
          │ d  │                         │ d  │        
          ├――――┤ 4                       ├――――┤        
          │ e  │                         │ b  │        
          ├――――┤ 5                       ├――――┤        
          │ f  │                         │ b  │        
          │    │                         └――――┘        
          │    │                                       
          └――――┘

Lineare versa Hashtabellen als Suchtabellen (Look-up tables)

Stefan Bosse - Algorithmen und Datenstrukturen - Modul H Tabellen :: Der Stapelspeicher

Der Stapelspeicher

• Ein Kellerspeicher oder auch Stapelspeicher alias Stack genannt ist eine lineare Tabelle (Array), aber

  • Es gibt aber keine freie Indizierung (kein RAM Modell)
  • Er implementiert aber Operationen mit einer Last-In First-Out Reigenfolge

• Nur abstrakte Operationen:

  • Push: Lege einen neuen Wert auf den Stapel ab (Last-In)
  • Pop: Holt den obersten Wert vom Stapel (Last-Out)

Stefan Bosse - Algorithmen und Datenstrukturen - Modul H Tabellen :: Der Stapelspeicher

Der Stapelspeicher

type Stack(T)
operators
  empty : → Stack(n)
  new : n → Stack(n)
  push : Stack × T → Stack
  pop : Stack → Stack
  top : Stack → T
  is_empty : Stack → Bool
  is_full : Stack → Bool
axioms ∀s : Stack, ∀x : T
  pop (push (s, x)) = s
  top (push (s, x)) = x
  is_empty (empty) = true 
  is_empty (push (s, x)) = false
  is_full (empty) = false
  is_full (n*push (s, x)) = true

ADT-Spezifikation eines Stacks

Stefan Bosse - Algorithmen und Datenstrukturen - Modul H Tabellen :: Der Stapelspeicher

Der Stapelspeicher

• Die Operation push packt ein Element des Parametertyps T auf den Stapel, pop entfernt das oberste Element.
• Mittels top kann man sich das oberste Element anschauen (ohne es zu entfernen).
• All diese Operationen sind als Funktionen mit einem (ersten) Parameter vom Typ Stack (genauer natürlich Stack(T)!) als Eingabe definiert.
• empty erzeugt einen leeren neuen Stapel, is_empty testet auf leeren Stack.

Stefan Bosse - Algorithmen und Datenstrukturen - Modul H Tabellen :: Der Stapelspeicher

Der Stapelspeicher

addp Verdeutlichung des Stack-Prinzips

Stefan Bosse - Algorithmen und Datenstrukturen - Modul H Tabellen :: Der Stapelspeicher

Der Stapelspeicher

• Dies kann über eine Ausnahme (Exception, Signal) des Typs StackException signalisiert werden, die beim Aufruf der Methoden pop, push und top auftreten kann.

• Der Datentyp der Datenelemente kann beliebig sein:

  • Numerische Werte
  • Zeichenketten
  • Datenstrukturen

• Statisch typisierte Programmiersprachen erfordern entweder ein virtuelles Template oder für jeden Datensatztyp eine eigene Implementierung. Dynamisch typisierte und teils auch funktionale Sprachen haben dieses Problem nicht.

Stefan Bosse - Algorithmen und Datenstrukturen - Modul H Tabellen :: Der Stapelspeicher

Der Stapelspeicher

Algorithmik

• Am einfachsten ist sowohl beim LIFO als noch beim folgenden FIFO Speicher die Einführung zweier Indexzeiger:

  • TOP: Zeigt auf das nächste freie Element in der lienaren Tabelle
  • BOTTOM: Zeigt auf das letzte belegte Element

• Man kann hier aber einfach nur einen Zeiger verwenden:

  • SP: Der Stackzeiger der auf das nächste freie Element zeigt und (SP-1) welches auf den obersten letzten Wert des Stapels verweist.

Stefan Bosse - Algorithmen und Datenstrukturen - Modul H Tabellen :: Der Stapelspeicher

Der Stapelspeicher

function Stack(N) {
  return {SP:0,N:N,T:Array(N)}
}
function push(S,x) {
  if (full(S)) throw "Full";
  S.T[S.SP]=x;
  S.SP++;
}
function pop(S) {
  if (empty(S)) throw "Empty";
  x=S.T[S.SP-1];
  S.SP--;
  return x
}
function full(S) { return S.SP==S.N-1 } function empty(S) { return S.SP==0 }

Implementierung der Stackoperationen

Stefan Bosse - Algorithmen und Datenstrukturen - Modul H Tabellen :: Der Stapelspeicher

Der Stapelspeicher

Applikationen

Stefan Bosse - Algorithmen und Datenstrukturen - Modul H Tabellen :: Der Stackprozessor

Der Stackprozessor

1. Es gibt twei Stacks: Einen Daten- und einen Instruktions Stack D und C
2. Es gibt zwei Arten von Operationen:
   • Literale die eine Wert auf dem Stack ablegen (und C → D bewirken)
   • Unäre und binäre Arithmetische Operationen die ihre Operanden vom D-Stack holen und das Ergebnis auch dort wieder ablegen

Wir benötigen noch eine weitere Stack Operation nth die den n-obersten Werte (n>0) vom Stapel liest:

function nth(S,n) { return S.T[S.SP-n] } // n > 0

Jetzt müssen wir Befehle für unsere einfache Numerik VM definieren:

function LITERAL(x) { return x /*number*/ }
function ADD() { return '+' }
function END() { return '.' }

Stefan Bosse - Algorithmen und Datenstrukturen - Modul H Tabellen :: Der Stackprozessor

Wir brauchen nun einen Stackprozessor der das Programm vom Stack abarbeitet:

function run() {
  next=pop(C)
  while (next!='.') {
    switch (next) {
      case '+':
        a=pop(D); b=pop(D)
        push(D,a+b)
        break;
      default: 
        if (typeof next=='number') push(D,next);
        else throw "EEXEC"
    }
    next=pop(C);
  }
}

Stefan Bosse - Algorithmen und Datenstrukturen - Modul H Tabellen :: Der Stackprozessor

Jetzt folgt der Stack und ein kleines Beispielsprogramm:

C=Stack(10)
D=Stack(10)
// Programm
push(C,END())
push(C,ADD())
push(C,LITERAL(3))
push(C,LITERAL(2))
run(C);
print(pop(D))

Jetzt wollen wir noch die Subtraktion hinzufügen. Bei der Addition ist die Reihenfolge der Operanden nicht relevant, bei der Subtraktion schon.

• Was sollen wir machen wenn die Operanden auf dem Stack in der falschen Reihenfolge liegen? Wir könnten eine swap Operation einführen!

Stefan Bosse - Algorithmen und Datenstrukturen - Modul H Tabellen :: Der Stackprozessor

function SUB() { return '-' }
function SWAP() { return '%' }
function run() {
  ...
    case '-': a=pop(D);b=pop(D);push(D,a-b); break;
    case '%': a=pop(D);b=pop(D);push(D,a);push(D,b); break;
  ...

Stefan Bosse - Algorithmen und Datenstrukturen - Modul H Tabellen :: Der Stackprozessor

+

Stefan Bosse - Algorithmen und Datenstrukturen - Modul H Tabellen :: Die Warteschlange

Die Warteschlange

Um die Prinzipien der Spezifikation von parametrisierten Datenstrukturen zu vertiefen, betrachten wir kurz eine weitere Datenstruktur, nämlich die Warteschlange oder englisch Queue.

• Eine Queue realisiert das sogenannte FIFO-Prinzip, also einen First-In-First-Out-Speicher.

  • Das FIFO-Prinzip modelliert eine Warteschlange, bei der man sich hinten anstellt: »Wer zuerst kommt, mahlt zuerst«.

• Es gibt wieder zwei wesentliche Operationen, die zwar auf einer Tabelle operieren, aber ebenfalls wie beim Stack keine explizite Indizierung der Tabelle benörigen (daher auch kein RAM Modell):

  • enter: Schreibt einen neuen Wert in die Queue
  • leave: List einen alten Wert aus der Queue

Stefan Bosse - Algorithmen und Datenstrukturen - Modul H Tabellen :: Die Warteschlange

type Queue(T)
operators
  empty : → Queue
  new : n → Queue(n)
  enter : Queue × T → Queue
  leave : Queue → Queue
  bottom : Queue → T
  top : Queue → T
  is_empty : Queue → Bool
  is_full : Queue → Bool
axioms ∀q : Queue, ∀x, y : T
  leave (enter (empty, x)) = empty
  leave (enter (enter(q, x), y)) =
  enter (leave (enter(q, x)), y)
  top (enter (empty, x)) = x
  top (enter (enter(q, x), y)) =
  top (enter (q, x))
  is_empty (empty) = true
  is_empty (enter(q, x)) = false
  is_full (empty) = false
  is_full (enter(q, x)) = false
  is_full (n * enter(q, x)) = true

Die Spezifikation einer Queue sieht auf den ersten Blick sehr ähnlich zu der eines Stacks aus, obwohl das Verarbeitungsprinzip komplett entgegengesetzt ist

Stefan Bosse - Algorithmen und Datenstrukturen - Modul H Tabellen :: Die Warteschlange

Die Warteschlange

Bezüglich Spezifikation: Im Unterschied zum Stack kann jetzt bei leave und bei front nicht der jeweilig letzte gespeicherte Parameter bearbeitet werden. Stattdessen ist es nötig, durch rekursiv aufgebaute Gleichungen sich bis zum jeweils »innersten« Wert des Queue-Terms vorzuarbeiten.

addp Verdeutlichung des Queue-Prinzips

Stefan Bosse - Algorithmen und Datenstrukturen - Modul H Tabellen :: Die Warteschlange

Anwendungen

Warteschlangen werden ebenfalls in vielfältiger Weise in Softwaresystemen eingesetzt, da sie das Abarbeiten von Aufträgen in Eingangsreihenfolge realisieren können:

• so etwa zur Prozessverwaltung in Betriebssystemen (FIFO Scheduling),
• zur Speicherverwaltung,
• für Warteschlangen bei Druckaufträgen,
• für Nachrichtenpuffer in der Kommunikationssoftware etc.

https://mungfali.com/explore/FIFO-Method-Diagram Beispiel: Einsatz einer Queue im Nachrichtenmuliplexing (Multi-Queue System)

Stefan Bosse - Algorithmen und Datenstrukturen - Modul H Tabellen :: Die Warteschlange

Algorithmik

• Das erste Element befindet sich immer auf der Position 0. Dies hat zur Folge, dass nach jedem Herausnehmen eines Elementes alle verbliebenen Elemente nach links verschoben werden müssten, was natürlich eine eher ungeeignete Variante darstellt.

• Wir brauchen jetzt tatsächlich zwei Zeiger um eine Queue mit einer linearen Tabelle zu implementieren:

  • HEAD: Zeigt auf das nächste freie Element (davor das jüngste)
  • BOTTOM: Zeigt auf das erste (älteste) Element in der Warteschlange

• Die zeiger werden bei enter und leave nur inkrementoiert:

  • enter: HEAD++
  • leave: BOTTOM++

Stefan Bosse - Algorithmen und Datenstrukturen - Modul H Tabellen :: Die Warteschlange

Algorithmik

    BOTTOM ┌―――――――――┐              
     ――┬―▶ │  Used   │  ◀――――┐      
       │   ├―――――――――┤ HEAD  │      
       │   │  Free   │――┬―▶  │      
leave  │   ├―――――――――┤  │    │ enter
       │   │         │  │    │      
   │   │   ├―――――――――┤  │    │      
   │   │   │         │  │    │      
   │   │   ├―――――――――┤  │    │      
   └―― ▼   │         │  ▼ ―――┘      
           └―――――――――┘

Simulierter Ringpuffer mit zwei umlaufenden Zeigern.

Stefan Bosse - Algorithmen und Datenstrukturen - Modul H Tabellen :: Die Warteschlange

Algorithmik

• Es wird ein zyklischer Ringpuffer durch die Modulo-Operation erzeugt: H%N, B%N mit N als Anzahl der Speicherzellen.

• Den Füllstand einer Queue über die beiden Zeigen zu bestimmen (empty, full) ist nicht eindeutig. Gleichheit von HEAD und BOTTOM liegt bei Leere und vollständiger Füllung vor! Daher wird ein Zähler verwendet (pder es dürfen nur N-1 Feldelemente befüllt werden).

function Queue(N)   { return { H:0,B:0,T:Array(N), N:N, n:0 } }
function enter(Q,x) { Q.T[Q.H]=x; Q.H=(Q.H+1) % Q.N; Q.n++; }
function leave(Q,x) { x=Q.T[Q.B]; Q.B=(Q.B+1) % Q.N; Q.n--; return x}
function empty(Q)   { return Q.n==0 }
function full(Q)    { return Q.n==Q.N }
function bottom(Q)  { return Q.n>0 && Q.T[Q.B] }
function top(Q)     { return Q.n>0 && Q.T[abs((Q.H-1)%Q.N)] }

Queue Operationen

Stefan Bosse - Algorithmen und Datenstrukturen - Modul H Tabellen :: Die Warteschlange

Algorithmik

• Die Zeitkomplexität ist konstant und beträgt O(1) für alle Operationen.

• Der Speicherplatzbedarf wird dagegen durch das Anlegen eines Feldes einer vorgegebenen Größe N verursacht und ist somit unabhängig von der tatsächlichen Anzahl der Elemente im Stack bzw. in der Queue. Für die Speicherplatzkomplexität kann demnach O(N) angegeben werden.

Stefan Bosse - Algorithmen und Datenstrukturen - Modul H Tabellen :: Die Warteschlange

+

Stefan Bosse - Algorithmen und Datenstrukturen - Modul H Tabellen :: Hash Tabellen

Hash Tabellen

Das Grundprinzip von Hashverfahren lässt sich mit wenigen Aussagen charakterisieren:

1. Die Speicherung der Datensätze erfolgt in einem Feld mit Indexwerten von 0 bis N− 1, wobei die einzelnen Positionen oft als »Buckets« bezeichnet werden.
2. Eine Hashfunktion h bestimmt für ein Element e die Position h(e) im Feld.
3. Die Funktion h sorgt für eine »gute«, kollisionsfreie bzw. kollisionsarme Verteilung der zu speichernden Elemente.

Wird zwei Elementen dieselbe Position zugewiesen, spricht man von einer Kollision. Neben einer möglichst gut streuenden Hashfunktion ist die Behandlung von Kollisionen ein zentrales Merkmal von Hashverfahren.

Stefan Bosse - Algorithmen und Datenstrukturen - Modul H Tabellen :: Hash Tabellen

AlgoSkript.pdf p 56 Algorithmen und Datenstrukturen, Reith

Algorithmen und Datenstrukturen (Thomas Ottmann, Peter Widmayer) (Z-Library).pdf p 169 Kap. 4 hashverfahren