CCWiki - Benutzerbeiträge [de]

UML Klassendiagramm

2021-01-07T17:16:56Z

192.168.192.1: Die Seite wurde neu angelegt: „TODO: * Was ist ein Klassendiagramm? * Wozu wird es benötigt? * Welche Elemente gibt es? Erkläre dies so detailliert und anschaulich wie möglich * Stelle in…“

TODO:
* Was ist ein Klassendiagramm?
* Wozu wird es benötigt?
* Welche Elemente gibt es? Erkläre dies so detailliert und anschaulich wie möglich
* Stelle in einem anschaulichen Beispiel ein Klassendiagramm Code gegenüber

Objektorientiertes Design und UML

2021-01-07T17:13:55Z

192.168.192.1:

Im folgenden wird zuerst auf die Begriffe '''UML''' und '''modellieren''' eingegangen. In weiterer Folge werden wir uns mit zwei gebräuchlichen Diagrammtypen, dem '''Klassendiagramm''' und dem '''Sequenzdiagramm''' beschäftigen.
= Modellieren =
TODO: Hier soll beschrieben werden was '''modellieren''' im allgemeinen und dann speziell in der Softwareentwicklung bedeutet.
= UML =
TODO: Hier soll geklärt werden was UML ist, von der Begriffsbedeutung bis hin zu den Einsatzgebieten in der Softwareentwicklung. Weiters sollen alle Diagrammtypen und deren Einteilung in Kategorien schön dargestellt werden.

== Diagramme ==
[[UML_Klassendiagramm|UML Klassendiagramm]]
 
[[UML_Sequenzdiagramm|UML Sequenzdiagramm]]

Objektorientiertes Design und UML

2021-01-07T17:12:30Z

192.168.192.1: /* Diagramme */

Zuerst sollen die Bregiffe '''UML''' und '''modellieren''' geklärt werden.
= Modellieren =
TODO: Hier soll beschrieben werden was '''modellieren''' im allgemeinen und dann speziell in der Softwareentwicklung bedeutet.
= UML =
TODO: Hier soll geklärt werden was UML ist, von der Begriffsbedeutung bis hin zu den Einsatzgebieten in der Softwareentwicklung. Weiters sollen alle Diagrammtypen und deren Einteilung in Kategorien schön dargestellt werden.

== Diagramme ==
[[UML_Klassendiagramm|UML Klassendiagramm]]
 
[[UML_Sequenzdiagramm|UML Sequenzdiagramm]]

Objektorientiertes Design und UML

2021-01-07T17:12:20Z

192.168.192.1:

Objektorientiertes Design und UML

2021-01-07T17:05:19Z

192.168.192.1: Leere Seite erstellt

Webservices und Client Server Konzepte

2021-01-07T16:58:32Z

192.168.192.1: /* Einheitliche Schnittstelle */

Zu allererst soll geklärt werden, was ein Webservices ist:
<blockquote>Ein Webservice (auch Webdienst) stellt eine Schnittstelle für die Maschine-zu-Maschine- oder Anwendungs-Kommunikation über Rechnernetze wie das Internet zur Verfügung. Dabei werden Daten ausgetauscht und auf entfernten Computern (Servern) Funktionen aufgerufen. Jeder Webservice besitzt einen Uniform Resource Identifier (URI), über den er eindeutig identifizierbar ist, sowie je nach Implementierung eine Schnittstellenbeschreibung in maschinenlesbarem Format (als XML-Artefakt, z. B. WSDL), die definiert, wie mit dem Webservice zu interagieren ist. Die Kommunikation kann über Protokolle aus dem Internetkontext wie HTTP oder HTTPS erfolgen; über diese Protokolle wiederum kann beispielsweise XML oder JSON übertragen werden. Ein Webservice ist plattformunabhängig und steht in der Regel mehreren Programmen zum Aufrufen bereit. [https://de.wikipedia.org/wiki/Webservice]</blockquote>
Was bedeutet dies nun ganz stark vereinfacht. Ein Webservice ist ein Programm, welches auf einem Server läuft, der über das Internet erreichbar ist. Ein Client (Browser, Anwendung, App), sendet Anfragen an diesen Webservice mit einem standardisierten Protokoll (z.B.: HTTP) und erhält darauf Antworten.
 
Im folgenden wollen wir uns nun mit RESTful Webservices beschäftigen, diese erfreuen sich großer beliebtheit und stehen in Konkurrenz zu anderen Varianten wie z.b.:
* ''WSDL/Soap basierten Webservices'' - Stark antiquiertes Konezpt
* ''GraphQL basierten Webservices'' - Damit werden unzulänglichkeiten bei RESTful Webservices behoben, jedoch wird auch auf die einheitliche Schnittstelle verzichtet

= RESTful Webservice =
Ein RESTful Webservice ist nicht eine konkrete Implementierung, es ist vielmehr ein Architekturstil dem gefolgt werden soll dieser besteht aus Prinzipien und Eigenschaften die auf einen Webservice zutreffen müssen, damit es sich um einen RESTful Webservice handelt bzw. einen Webservice der auf den REST Prinzipien beruht. REST steht für '''Represential State Transfer''' und wurde von Roy Fielding "entwickelt".

== Prinzipien ==
Im folgenden wollen wir auf einige der Prinzipien eingehen. Folgender Abschnitt ist jedoch nicht vollständig, soll aber an dieser Stelle ausreichen.

=== Einheitliche Schnittstelle ===
Dies ist ein Hauptunterscheidungsmerkmal zu den meisten anderen Webservice Architekturen. Die einheitliche Schnittstelle besteht aus vier weiteren Eigenschaften, wobei wir im folgenden nur drei besprechen werden. Das Ziel ist, wie der Name schon sagt, eine einheitliche Schnittstelle für Webservices und eine daraus folgende einfache Nutzbarkeit. (HATEOS lassen wir außen vor, wenn dies auch laut Fielding die wichtigste Eigenschaft ist.)
 
==== Addressierbarkeit von Ressourcen ====
Jede Ressource hat einen eindeutigen Bezeichner und ist über eine URL erreichbar ist. Diese Ressourcen können einheitlich manipuliert, abgerufen und identifiziert werden können. Eine Ressource kann z.B. ein Kundenprofil sein.
 
Kunde mit der id 101 -> https://webservice.drlue.at/customer/101

==== Selbstbeschreibende Nachrichten ====
REST Nachrichten sollen selbstbeschreibend sein, dafür sollen Standardmethoden verwendet werden, meist werden hier die HTTP Methoden verwendet.
 
Betrachten wir das Beispiel des Kunden mit der Id 101 und stellen den Vergleich zu den HTTP Methoden her:
{| class="wikitable"
|-
! HTTP Methode !! URL !! Operation
|-
| GET || https://webservice.drlue.at/customer/101 || Holen der Benutzerinformation
|-
| DELETE || https://webservice.drlue.at/customer/101 || Löschen des Benutzers
|-
| PUT || https://webservice.drlue.at/customer/101 || Verändern des Benutzers, es müssen die zu ändernden Daten mitgesendet werden
|-
| POST || https://webservice.drlue.at/customer || Anlegen eines neuen Benutzers, die Benutzerdaten müssen mitgesendet werden
|}

=== Caching ===
HTTP Caching soll implementiert werden. Wobei jede Anfrage die nicht gestellt werden muss, die beste ist.
Klären wir zuerst den Begriff des Cachings. Dieses Konzept gilt natürlich in vielen Bereichen der Informatik, wir erklären den Begriff anhand des Zugriffs auf eine Ressource. Eine Ressource wird geholt, zu einem späteren Zeitpunkt wird diese Ressource erneut geholt. Hat sich diese nicht verändert, so soll sie nicht erneut übertragen werden, sondern aus dem Zwischenspeicher der Anwendung abgerufen werden. 
Durch Caching bei Webanwendungen soll die Übertragung von Daten über das Internet reduziert werden.
In folgender Tabelle wird die Funktionsweise von HTTP Caching mittels ETag beschrieben. Man beachte, die HTTP Anfragen sind ''nicht'' vollständig und beschränken sich auf die fürs Caching wesentlichen Header.
{| class="wikitable"
|+ Ablauf beim Anfragen auf eine Ressource (http://webservice.drlue.at/customer/101)
|-
! Anfrage !! Antwort !! Beschreibung
|- style="vertical-align:top;"
|
<syntaxhighlight lang='http' line>
GET /customer/101 HTTP/1.1
Host: webservice.drlue.at
</syntaxhighlight>
                                                                          
|style="white-space: nowrap;"|
<syntaxhighlight lang='http' line>
HTTP/1.1 200 OK
Etag: "478fb2348f700"

{
"name": "luke",
"id": 101
}
</syntaxhighlight>
                                                             
|Erstmaliges holen der spezifischen Ressource. Server Antwortet mit den Daten und liefert im HTTP Header den ''ETag'' mit
|- style="vertical-align:top;"
|style="white-space: nowrap;"|
<syntaxhighlight lang='http' line="'line'">
GET /customer/101 HTTP/1.1
Host: webservice.drlue.at
If-none-match: "478fb2348f700"
</syntaxhighlight>
|style="white-space: nowrap;"|
<syntaxhighlight lang='http' line="'line'">
HTTP/1.1 304 Not Modified
Etag: "478fb2348f700"
</syntaxhighlight>
|Eine weitere Anfrage des Clients erfolgt mit dem ''ETag'' nun aber im ''If-none-match'' Header. Man könnte diese Anfrage wie folgt interpretieren: Gib mir die Ressource nur zurück, wenn der ''ETag'' nicht mehr zutrifft. Der Server Antwortet mit dem ''HTTP Statuscode 304 Not Modified''. Dies bedeutet, es hat sich nichts geändert. Der Client wird somit darauf hingewiesen die Daten aus seinem eigenen ''Cache'' oder ''Zwischenspeicher'' zu holen.
|- style="vertical-align:top;"
|style="white-space: nowrap;"|
<syntaxhighlight lang='http' line="'line'">
GET /customer/101 HTTP/1.1
Host: webservice.drlue.at
If-none-match: "478fb2348f700"
</syntaxhighlight>
|style="white-space: nowrap;"|
<syntaxhighlight lang='http' line>
HTTP/1.1 200 OK
Etag: "497fb2348f705"

{
"name": "luke1",
"id": 101
}
</syntaxhighlight>
|Zu einem späteren Zeitpunkt holt der Client erneut die Selbe Ressource und sendet wieder den ''ETag'' mit. Die Ressource hat sich jedoch am Server geändert. Dieser sendet die Ressource dem Client zurück und sendet zusätzlich im Header den neuen ''ETag'' mit.
|}

==== Mögliche Implementierung ====
In modernen Technologien wie z.B.: Express für Node.js finden sich automatische mechanismen für die Caching implementierung über ETags. Der Ablauf ist denkbar einfach. Der Server betrachtet vor dem Absenden der Antwort an den Client deren Inhalt. Es geht hier nur um den HTTP Body, die Header spielen hier keine Rolle. Aus dem Body wird eine Hashsumme berechnet und diese wird dann als ''ETag'' verwendet.
'''Hashsumme:''' Mittels eines Hashalgorithmus wie z.b.: (SHA256, MD5, ...) kann aus einer großen Datenmenge ein "eindeutiger" Wert berechnet werden. Bei SHA256 hat dieser Wert '''immer''' eine Länge von 256 Bit, egal wie groß der Input ist. Der Wert kann natürlich nicht eindeut sein, doch die Chance ist verschwindend gering, dass für unterschiedliche Input Daten, die selbe Hashsumme gebildet wird.
Diese Implementierung bietet eine einfache Möglichkeit des Cachings um die Datenübertragung vom Client zum Server deutlich zu reduzieren. Dies reduziert die Netzwerklast auf Client und Serverseite.
 
Eine Rechenauslastung auf Seiten des Servers findet jedoch nicht statt. Der Body der Antwort muss bei jeder Antwort erstellt werden um den ''ETag'' zu generieren. Das bedeutet, der Server muss trotzdem Anfragen an die Datenbank stellen bzw. alle nötigen Berechnungen ausführen um die Antwort zu erstellen.
 
Weiters ist das Bilden der Hashsumme, vorallem wenn es sich um größere Datenmengen handelt, eine Rechenintensive Operation. Ändern sich die Daten regelmäßig, so könnte man sich das bilden der Hashsumme und den daraus resultierenden mehraufwand, sparen.

=== Zustandslosigkeit ===

Webservices und Client Server Konzepte

2021-01-07T11:42:25Z

192.168.192.1: /* RESTful Webservice */

Zu allererst soll geklärt werden, was ein Webservices ist:
<blockquote>Ein Webservice (auch Webdienst) stellt eine Schnittstelle für die Maschine-zu-Maschine- oder Anwendungs-Kommunikation über Rechnernetze wie das Internet zur Verfügung. Dabei werden Daten ausgetauscht und auf entfernten Computern (Servern) Funktionen aufgerufen. Jeder Webservice besitzt einen Uniform Resource Identifier (URI), über den er eindeutig identifizierbar ist, sowie je nach Implementierung eine Schnittstellenbeschreibung in maschinenlesbarem Format (als XML-Artefakt, z. B. WSDL), die definiert, wie mit dem Webservice zu interagieren ist. Die Kommunikation kann über Protokolle aus dem Internetkontext wie HTTP oder HTTPS erfolgen; über diese Protokolle wiederum kann beispielsweise XML oder JSON übertragen werden. Ein Webservice ist plattformunabhängig und steht in der Regel mehreren Programmen zum Aufrufen bereit. [https://de.wikipedia.org/wiki/Webservice]</blockquote>
Was bedeutet dies nun ganz stark vereinfacht. Ein Webservice ist ein Programm, welches auf einem Server läuft, der über das Internet erreichbar ist. Ein Client (Browser, Anwendung, App), sendet Anfragen an diesen Webservice mit einem standardisierten Protokoll (z.B.: HTTP) und erhält darauf Antworten.
 
Im folgenden wollen wir uns nun mit RESTful Webservices beschäftigen, diese erfreuen sich großer beliebtheit und stehen in Konkurrenz zu anderen Varianten wie z.b.:
* ''WSDL/Soap basierten Webservices'' - Stark antiquiertes Konezpt
* ''GraphQL basierten Webservices'' - Damit werden unzulänglichkeiten bei RESTful Webservices behoben, jedoch wird auch auf die einheitliche Schnittstelle verzichtet

= RESTful Webservice =
Ein RESTful Webservice ist nicht eine konkrete Implementierung, es ist vielmehr ein Architekturstil dem gefolgt werden soll dieser besteht aus Prinzipien und Eigenschaften die auf einen Webservice zutreffen müssen, damit es sich um einen RESTful Webservice handelt bzw. einen Webservice der auf den REST Prinzipien beruht. REST steht für '''Represential State Transfer''' und wurde von Roy Fielding "entwickelt".

== Prinzipien ==
Im folgenden wollen wir auf einige der Prinzipien eingehen. Folgender Abschnitt ist jedoch nicht vollständig, soll aber an dieser Stelle ausreichen.

=== Einheitliche Schnittstelle ===
Dies ist ein Hauptunterscheidungsmerkmal zu den meisten anderen Webservice Architekturen.
 
Wir sprechen hier von Ressourcen die einheitlich manipuliert, abgerufen und identifiziert werden können. Eine Ressource kann z.B. ein Kundenprofil sein.
==== Addressierbarkeit von Ressourcen ====
Jede Ressource hat einen eindeutigen Bezeichner und ist über eine URL erreichbar ist
 
Kunde mit der id 101 -> https://webservice.drlue.at/customer/101

==== Selbstbeschreibende Nachrichten ====
REST Nachrichten sollen selbstbeschreibend sein, dafür sollen Standardmethoden verwendet werden, meist werden hier die HTTP Methoden verwendet.
 
Betrachten wir das Beispiel des Kunden mit der Id 101 und stellen den Vergleich zu den HTTP Methoden her:
{| class="wikitable"
|-
! HTTP Methode !! URL !! Operation
|-
| GET || https://webservice.drlue.at/customer/101 || Holen der Benutzerinformation
|-
| DELETE || https://webservice.drlue.at/customer/101 || Löschen des Benutzers
|-
| PUT || https://webservice.drlue.at/customer/101 || Verändern des Benutzers, es müssen die zu ändernden Daten mitgesendet werden
|-
| POST || https://webservice.drlue.at/customer || Anlegen eines neuen Benutzers, die Benutzerdaten müssen mitgesendet werden
|}
=== Caching ===
HTTP Caching soll implementiert werden. Wobei jede Anfrage die nicht gestellt werden muss, die beste ist.
Klären wir zuerst den Begriff des Cachings. Dieses Konzept gilt natürlich in vielen Bereichen der Informatik, wir erklären den Begriff anhand des Zugriffs auf eine Ressource. Eine Ressource wird geholt, zu einem späteren Zeitpunkt wird diese Ressource erneut geholt. Hat sich diese nicht verändert, so soll sie nicht erneut übertragen werden, sondern aus dem Zwischenspeicher der Anwendung abgerufen werden. 
Durch Caching bei Webanwendungen soll die Übertragung von Daten über das Internet reduziert werden.
In folgender Tabelle wird die Funktionsweise von HTTP Caching mittels ETag beschrieben. Man beachte, die HTTP Anfragen sind ''nicht'' vollständig und beschränken sich auf die fürs Caching wesentlichen Header.
{| class="wikitable"
|+ Ablauf beim Anfragen auf eine Ressource (http://webservice.drlue.at/customer/101)
|-
! Anfrage !! Antwort !! Beschreibung
|- style="vertical-align:top;"
|
<syntaxhighlight lang='http' line>
GET /customer/101 HTTP/1.1
Host: webservice.drlue.at
</syntaxhighlight>
                                                                          
|style="white-space: nowrap;"|
<syntaxhighlight lang='http' line>
HTTP/1.1 200 OK
Etag: "478fb2348f700"

{
"name": "luke",
"id": 101
}
</syntaxhighlight>
                                                             
|Erstmaliges holen der spezifischen Ressource. Server Antwortet mit den Daten und liefert im HTTP Header den ''ETag'' mit
|- style="vertical-align:top;"
|style="white-space: nowrap;"|
<syntaxhighlight lang='http' line="'line'">
GET /customer/101 HTTP/1.1
Host: webservice.drlue.at
If-none-match: "478fb2348f700"
</syntaxhighlight>
|style="white-space: nowrap;"|
<syntaxhighlight lang='http' line="'line'">
HTTP/1.1 304 Not Modified
Etag: "478fb2348f700"
</syntaxhighlight>
|Eine weitere Anfrage des Clients erfolgt mit dem ''ETag'' nun aber im ''If-none-match'' Header. Man könnte diese Anfrage wie folgt interpretieren: Gib mir die Ressource nur zurück, wenn der ''ETag'' nicht mehr zutrifft. Der Server Antwortet mit dem ''HTTP Statuscode 304 Not Modified''. Dies bedeutet, es hat sich nichts geändert. Der Client wird somit darauf hingewiesen die Daten aus seinem eigenen ''Cache'' oder ''Zwischenspeicher'' zu holen.
|- style="vertical-align:top;"
|style="white-space: nowrap;"|
<syntaxhighlight lang='http' line="'line'">
GET /customer/101 HTTP/1.1
Host: webservice.drlue.at
If-none-match: "478fb2348f700"
</syntaxhighlight>
|style="white-space: nowrap;"|
<syntaxhighlight lang='http' line>
HTTP/1.1 200 OK
Etag: "497fb2348f705"

{
"name": "luke1",
"id": 101
}
</syntaxhighlight>
|Zu einem späteren Zeitpunkt holt der Client erneut die Selbe Ressource und sendet wieder den ''ETag'' mit. Die Ressource hat sich jedoch am Server geändert. Dieser sendet die Ressource dem Client zurück und sendet zusätzlich im Header den neuen ''ETag'' mit.
|}

==== Mögliche Implementierung ====
In modernen Technologien wie z.B.: Express für Node.js finden sich automatische mechanismen für die Caching implementierung über ETags. Der Ablauf ist denkbar einfach. Der Server betrachtet vor dem Absenden der Antwort an den Client deren Inhalt. Es geht hier nur um den HTTP Body, die Header spielen hier keine Rolle. Aus dem Body wird eine Hashsumme berechnet und diese wird dann als ''ETag'' verwendet.
'''Hashsumme:''' Mittels eines Hashalgorithmus wie z.b.: (SHA256, MD5, ...) kann aus einer großen Datenmenge ein "eindeutiger" Wert berechnet werden. Bei SHA256 hat dieser Wert '''immer''' eine Länge von 256 Bit, egal wie groß der Input ist. Der Wert kann natürlich nicht eindeut sein, doch die Chance ist verschwindend gering, dass für unterschiedliche Input Daten, die selbe Hashsumme gebildet wird.
Diese Implementierung bietet eine einfache Möglichkeit des Cachings um die Datenübertragung vom Client zum Server deutlich zu reduzieren. Dies reduziert die Netzwerklast auf Client und Serverseite.
 
Eine Rechenauslastung auf Seiten des Servers findet jedoch nicht statt. Der Body der Antwort muss bei jeder Antwort erstellt werden um den ''ETag'' zu generieren. Das bedeutet, der Server muss trotzdem Anfragen an die Datenbank stellen bzw. alle nötigen Berechnungen ausführen um die Antwort zu erstellen.
 
Weiters ist das Bilden der Hashsumme, vorallem wenn es sich um größere Datenmengen handelt, eine Rechenintensive Operation. Ändern sich die Daten regelmäßig, so könnte man sich das bilden der Hashsumme und den daraus resultierenden mehraufwand, sparen.

=== Zustandslosigkeit ===

Webservices und Client Server Konzepte

2021-01-07T11:03:29Z

192.168.192.1: /* Mögliche Implementierung */

Zu allererst soll geklärt werden, was ein Webservices ist:
<blockquote>Ein Webservice (auch Webdienst) stellt eine Schnittstelle für die Maschine-zu-Maschine- oder Anwendungs-Kommunikation über Rechnernetze wie das Internet zur Verfügung. Dabei werden Daten ausgetauscht und auf entfernten Computern (Servern) Funktionen aufgerufen. Jeder Webservice besitzt einen Uniform Resource Identifier (URI), über den er eindeutig identifizierbar ist, sowie je nach Implementierung eine Schnittstellenbeschreibung in maschinenlesbarem Format (als XML-Artefakt, z. B. WSDL), die definiert, wie mit dem Webservice zu interagieren ist. Die Kommunikation kann über Protokolle aus dem Internetkontext wie HTTP oder HTTPS erfolgen; über diese Protokolle wiederum kann beispielsweise XML oder JSON übertragen werden. Ein Webservice ist plattformunabhängig und steht in der Regel mehreren Programmen zum Aufrufen bereit. [https://de.wikipedia.org/wiki/Webservice]</blockquote>
Was bedeutet dies nun ganz stark vereinfacht. Ein Webservice ist ein Programm, welches auf einem Server läuft, der über das Internet erreichbar ist. Ein Client (Browser, Anwendung, App), sendet Anfragen an diesen Webservice mit einem standardisierten Protokoll (z.B.: HTTP) und erhält darauf Antworten.
 
Im folgenden wollen wir uns nun mit RESTful Webservices beschäftigen, diese erfreuen sich großer beliebtheit und stehen in Konkurrenz zu anderen Varianten wie z.b.:
* ''WSDL/Soap basierten Webservices'' - Stark antiquiertes Konezpt
* ''GraphQL basierten Webservices'' - Damit werden unzulänglichkeiten bei RESTful Webservices behoben, jedoch wird auch auf die einheitliche Schnittstelle verzichtet

= RESTful Webservice =
Ein RESTful Webservice ist nicht eine konkrete Implementierung, es sind vielmehr Prinzipien und Eigenschaften die auf einen Webservice zutreffen müssen, damit es sich um einen RESTful Webservice handelt bzw. einen Webservice der auf den REST Prinzipien beruht. REST steht für '''Represential State Transfer''' und wurde von Roy Fielding "entwickelt".

== Prinzipien ==
Im folgenden wollen wir auf einige der Prinzipien eingehen. Folgender Abschnitt ist jedoch nicht vollständig, soll aber an dieser Stelle ausreichen.

=== Einheitliche Schnittstelle ===
Dies ist ein Hauptunterscheidungsmerkmal zu den meisten anderen Webservice Architekturen.
 
Wir sprechen hier von Ressourcen die einheitlich manipuliert, abgerufen und identifiziert werden können. Eine Ressource kann z.B. ein Kundenprofil sein.
==== Addressierbarkeit von Ressourcen ====
Jede Ressource hat einen eindeutigen Bezeichner und ist über eine URL erreichbar ist
 
Kunde mit der id 101 -> https://webservice.drlue.at/customer/101

==== Selbstbeschreibende Nachrichten ====
REST Nachrichten sollen selbstbeschreibend sein, dafür sollen Standardmethoden verwendet werden, meist werden hier die HTTP Methoden verwendet.
 
Betrachten wir das Beispiel des Kunden mit der Id 101 und stellen den Vergleich zu den HTTP Methoden her:
{| class="wikitable"
|-
! HTTP Methode !! URL !! Operation
|-
| GET || https://webservice.drlue.at/customer/101 || Holen der Benutzerinformation
|-
| DELETE || https://webservice.drlue.at/customer/101 || Löschen des Benutzers
|-
| PUT || https://webservice.drlue.at/customer/101 || Verändern des Benutzers, es müssen die zu ändernden Daten mitgesendet werden
|-
| POST || https://webservice.drlue.at/customer || Anlegen eines neuen Benutzers, die Benutzerdaten müssen mitgesendet werden
|}
=== Caching ===
HTTP Caching soll implementiert werden. Wobei jede Anfrage die nicht gestellt werden muss, die beste ist.
Klären wir zuerst den Begriff des Cachings. Dieses Konzept gilt natürlich in vielen Bereichen der Informatik, wir erklären den Begriff anhand des Zugriffs auf eine Ressource. Eine Ressource wird geholt, zu einem späteren Zeitpunkt wird diese Ressource erneut geholt. Hat sich diese nicht verändert, so soll sie nicht erneut übertragen werden, sondern aus dem Zwischenspeicher der Anwendung abgerufen werden. 
Durch Caching bei Webanwendungen soll die Übertragung von Daten über das Internet reduziert werden.
In folgender Tabelle wird die Funktionsweise von HTTP Caching mittels ETag beschrieben. Man beachte, die HTTP Anfragen sind ''nicht'' vollständig und beschränken sich auf die fürs Caching wesentlichen Header.
{| class="wikitable"
|+ Ablauf beim Anfragen auf eine Ressource (http://webservice.drlue.at/customer/101)
|-
! Anfrage !! Antwort !! Beschreibung
|- style="vertical-align:top;"
|
<syntaxhighlight lang='http' line>
GET /customer/101 HTTP/1.1
Host: webservice.drlue.at
</syntaxhighlight>
                                                                          
|style="white-space: nowrap;"|
<syntaxhighlight lang='http' line>
HTTP/1.1 200 OK
Etag: "478fb2348f700"

{
"name": "luke",
"id": 101
}
</syntaxhighlight>
                                                             
|Erstmaliges holen der spezifischen Ressource. Server Antwortet mit den Daten und liefert im HTTP Header den ''ETag'' mit
|- style="vertical-align:top;"
|style="white-space: nowrap;"|
<syntaxhighlight lang='http' line="'line'">
GET /customer/101 HTTP/1.1
Host: webservice.drlue.at
If-none-match: "478fb2348f700"
</syntaxhighlight>
|style="white-space: nowrap;"|
<syntaxhighlight lang='http' line="'line'">
HTTP/1.1 304 Not Modified
Etag: "478fb2348f700"
</syntaxhighlight>
|Eine weitere Anfrage des Clients erfolgt mit dem ''ETag'' nun aber im ''If-none-match'' Header. Man könnte diese Anfrage wie folgt interpretieren: Gib mir die Ressource nur zurück, wenn der ''ETag'' nicht mehr zutrifft. Der Server Antwortet mit dem ''HTTP Statuscode 304 Not Modified''. Dies bedeutet, es hat sich nichts geändert. Der Client wird somit darauf hingewiesen die Daten aus seinem eigenen ''Cache'' oder ''Zwischenspeicher'' zu holen.
|- style="vertical-align:top;"
|style="white-space: nowrap;"|
<syntaxhighlight lang='http' line="'line'">
GET /customer/101 HTTP/1.1
Host: webservice.drlue.at
If-none-match: "478fb2348f700"
</syntaxhighlight>
|style="white-space: nowrap;"|
<syntaxhighlight lang='http' line>
HTTP/1.1 200 OK
Etag: "497fb2348f705"

{
"name": "luke1",
"id": 101
}
</syntaxhighlight>
|Zu einem späteren Zeitpunkt holt der Client erneut die Selbe Ressource und sendet wieder den ''ETag'' mit. Die Ressource hat sich jedoch am Server geändert. Dieser sendet die Ressource dem Client zurück und sendet zusätzlich im Header den neuen ''ETag'' mit.
|}

==== Mögliche Implementierung ====
In modernen Technologien wie z.B.: Express für Node.js finden sich automatische mechanismen für die Caching implementierung über ETags. Der Ablauf ist denkbar einfach. Der Server betrachtet vor dem Absenden der Antwort an den Client deren Inhalt. Es geht hier nur um den HTTP Body, die Header spielen hier keine Rolle. Aus dem Body wird eine Hashsumme berechnet und diese wird dann als ''ETag'' verwendet.
'''Hashsumme:''' Mittels eines Hashalgorithmus wie z.b.: (SHA256, MD5, ...) kann aus einer großen Datenmenge ein "eindeutiger" Wert berechnet werden. Bei SHA256 hat dieser Wert '''immer''' eine Länge von 256 Bit, egal wie groß der Input ist. Der Wert kann natürlich nicht eindeut sein, doch die Chance ist verschwindend gering, dass für unterschiedliche Input Daten, die selbe Hashsumme gebildet wird.
Diese Implementierung bietet eine einfache Möglichkeit des Cachings um die Datenübertragung vom Client zum Server deutlich zu reduzieren. Dies reduziert die Netzwerklast auf Client und Serverseite.
 
Eine Rechenauslastung auf Seiten des Servers findet jedoch nicht statt. Der Body der Antwort muss bei jeder Antwort erstellt werden um den ''ETag'' zu generieren. Das bedeutet, der Server muss trotzdem Anfragen an die Datenbank stellen bzw. alle nötigen Berechnungen ausführen um die Antwort zu erstellen.
 
Weiters ist das Bilden der Hashsumme, vorallem wenn es sich um größere Datenmengen handelt, eine Rechenintensive Operation. Ändern sich die Daten regelmäßig, so könnte man sich das bilden der Hashsumme und den daraus resultierenden mehraufwand, sparen.

=== Zustandslosigkeit ===

Webservices und Client Server Konzepte

2021-01-07T10:59:06Z

192.168.192.1: /* Mögliche Implementierung */

Zu allererst soll geklärt werden, was ein Webservices ist:
<blockquote>Ein Webservice (auch Webdienst) stellt eine Schnittstelle für die Maschine-zu-Maschine- oder Anwendungs-Kommunikation über Rechnernetze wie das Internet zur Verfügung. Dabei werden Daten ausgetauscht und auf entfernten Computern (Servern) Funktionen aufgerufen. Jeder Webservice besitzt einen Uniform Resource Identifier (URI), über den er eindeutig identifizierbar ist, sowie je nach Implementierung eine Schnittstellenbeschreibung in maschinenlesbarem Format (als XML-Artefakt, z. B. WSDL), die definiert, wie mit dem Webservice zu interagieren ist. Die Kommunikation kann über Protokolle aus dem Internetkontext wie HTTP oder HTTPS erfolgen; über diese Protokolle wiederum kann beispielsweise XML oder JSON übertragen werden. Ein Webservice ist plattformunabhängig und steht in der Regel mehreren Programmen zum Aufrufen bereit. [https://de.wikipedia.org/wiki/Webservice]</blockquote>
Was bedeutet dies nun ganz stark vereinfacht. Ein Webservice ist ein Programm, welches auf einem Server läuft, der über das Internet erreichbar ist. Ein Client (Browser, Anwendung, App), sendet Anfragen an diesen Webservice mit einem standardisierten Protokoll (z.B.: HTTP) und erhält darauf Antworten.
 
Im folgenden wollen wir uns nun mit RESTful Webservices beschäftigen, diese erfreuen sich großer beliebtheit und stehen in Konkurrenz zu anderen Varianten wie z.b.:
* ''WSDL/Soap basierten Webservices'' - Stark antiquiertes Konezpt
* ''GraphQL basierten Webservices'' - Damit werden unzulänglichkeiten bei RESTful Webservices behoben, jedoch wird auch auf die einheitliche Schnittstelle verzichtet

= RESTful Webservice =
Ein RESTful Webservice ist nicht eine konkrete Implementierung, es sind vielmehr Prinzipien und Eigenschaften die auf einen Webservice zutreffen müssen, damit es sich um einen RESTful Webservice handelt bzw. einen Webservice der auf den REST Prinzipien beruht. REST steht für '''Represential State Transfer''' und wurde von Roy Fielding "entwickelt".

== Prinzipien ==
Im folgenden wollen wir auf einige der Prinzipien eingehen. Folgender Abschnitt ist jedoch nicht vollständig, soll aber an dieser Stelle ausreichen.

=== Einheitliche Schnittstelle ===
Dies ist ein Hauptunterscheidungsmerkmal zu den meisten anderen Webservice Architekturen.
 
Wir sprechen hier von Ressourcen die einheitlich manipuliert, abgerufen und identifiziert werden können. Eine Ressource kann z.B. ein Kundenprofil sein.
==== Addressierbarkeit von Ressourcen ====
Jede Ressource hat einen eindeutigen Bezeichner und ist über eine URL erreichbar ist
 
Kunde mit der id 101 -> https://webservice.drlue.at/customer/101

==== Selbstbeschreibende Nachrichten ====
REST Nachrichten sollen selbstbeschreibend sein, dafür sollen Standardmethoden verwendet werden, meist werden hier die HTTP Methoden verwendet.
 
Betrachten wir das Beispiel des Kunden mit der Id 101 und stellen den Vergleich zu den HTTP Methoden her:
{| class="wikitable"
|-
! HTTP Methode !! URL !! Operation
|-
| GET || https://webservice.drlue.at/customer/101 || Holen der Benutzerinformation
|-
| DELETE || https://webservice.drlue.at/customer/101 || Löschen des Benutzers
|-
| PUT || https://webservice.drlue.at/customer/101 || Verändern des Benutzers, es müssen die zu ändernden Daten mitgesendet werden
|-
| POST || https://webservice.drlue.at/customer || Anlegen eines neuen Benutzers, die Benutzerdaten müssen mitgesendet werden
|}
=== Caching ===
HTTP Caching soll implementiert werden. Wobei jede Anfrage die nicht gestellt werden muss, die beste ist.
Klären wir zuerst den Begriff des Cachings. Dieses Konzept gilt natürlich in vielen Bereichen der Informatik, wir erklären den Begriff anhand des Zugriffs auf eine Ressource. Eine Ressource wird geholt, zu einem späteren Zeitpunkt wird diese Ressource erneut geholt. Hat sich diese nicht verändert, so soll sie nicht erneut übertragen werden, sondern aus dem Zwischenspeicher der Anwendung abgerufen werden. 
Durch Caching bei Webanwendungen soll die Übertragung von Daten über das Internet reduziert werden.
In folgender Tabelle wird die Funktionsweise von HTTP Caching mittels ETag beschrieben. Man beachte, die HTTP Anfragen sind ''nicht'' vollständig und beschränken sich auf die fürs Caching wesentlichen Header.
{| class="wikitable"
|+ Ablauf beim Anfragen auf eine Ressource (http://webservice.drlue.at/customer/101)
|-
! Anfrage !! Antwort !! Beschreibung
|- style="vertical-align:top;"
|
<syntaxhighlight lang='http' line>
GET /customer/101 HTTP/1.1
Host: webservice.drlue.at
</syntaxhighlight>
                                                                          
|style="white-space: nowrap;"|
<syntaxhighlight lang='http' line>
HTTP/1.1 200 OK
Etag: "478fb2348f700"

{
"name": "luke",
"id": 101
}
</syntaxhighlight>
                                                             
|Erstmaliges holen der spezifischen Ressource. Server Antwortet mit den Daten und liefert im HTTP Header den ''ETag'' mit
|- style="vertical-align:top;"
|style="white-space: nowrap;"|
<syntaxhighlight lang='http' line="'line'">
GET /customer/101 HTTP/1.1
Host: webservice.drlue.at
If-none-match: "478fb2348f700"
</syntaxhighlight>
|style="white-space: nowrap;"|
<syntaxhighlight lang='http' line="'line'">
HTTP/1.1 304 Not Modified
Etag: "478fb2348f700"
</syntaxhighlight>
|Eine weitere Anfrage des Clients erfolgt mit dem ''ETag'' nun aber im ''If-none-match'' Header. Man könnte diese Anfrage wie folgt interpretieren: Gib mir die Ressource nur zurück, wenn der ''ETag'' nicht mehr zutrifft. Der Server Antwortet mit dem ''HTTP Statuscode 304 Not Modified''. Dies bedeutet, es hat sich nichts geändert. Der Client wird somit darauf hingewiesen die Daten aus seinem eigenen ''Cache'' oder ''Zwischenspeicher'' zu holen.
|- style="vertical-align:top;"
|style="white-space: nowrap;"|
<syntaxhighlight lang='http' line="'line'">
GET /customer/101 HTTP/1.1
Host: webservice.drlue.at
If-none-match: "478fb2348f700"
</syntaxhighlight>
|style="white-space: nowrap;"|
<syntaxhighlight lang='http' line>
HTTP/1.1 200 OK
Etag: "497fb2348f705"

{
"name": "luke1",
"id": 101
}
</syntaxhighlight>
|Zu einem späteren Zeitpunkt holt der Client erneut die Selbe Ressource und sendet wieder den ''ETag'' mit. Die Ressource hat sich jedoch am Server geändert. Dieser sendet die Ressource dem Client zurück und sendet zusätzlich im Header den neuen ''ETag'' mit.
|}

==== Mögliche Implementierung ====
In modernen Technologien wie z.B.: Express für Node.js finden sich automatische mechanismen für die Caching implementierung über ETags. Der Ablauf ist denkbar einfach. Der Server betrachtet vor dem Absenden der Antwort an den Client deren Inhalt. Es geht hier nur um den HTTP Body, die Header spielen hier keine Rolle. Aus dem Body wird eine Hashsumme berechnet und diese wird dann als ''ETag'' verwendet.
'''Hashsumme:''' Mittels eines Hashalgorithmus wie z.b.: (SHA256, MD5, ...) kann aus einer großen Datenmenge ein "eindeutiger" Wert berechnet werden. Bei SHA256 hat dieser Wert '''immer''' eine Länge von 256 Bit, egal wie groß der Input ist. Der Wert kann natürlich nicht eindeut sein, doch die Chance ist verschwindend gering, dass für unterschiedliche Input Daten, die selbe Hashsumme gebildet wird.
Diese Implementierung bietet eine einfache Möglichkeit des Cachings um die Datenübertragung vom Client zum Server deutlich zu reduzieren. Die Reduziert die Netzwerklast auf Client und Serverseite.
 
Eine Rechenauslastung auf Seiten des Servers findet jedoch nicht statt. Der Body der Antwort muss bei jeder Antwort erstellt werden um den ''ETag'' zu erstellen. Das bedeutet, der Server muss trotzdem Anfragen an die Datenbank stellen bzw. alle nötigen Berechnungen ausführen um die Antwort zu erstellen.

=== Zustandslosigkeit ===

Webservices und Client Server Konzepte

2021-01-07T10:57:06Z

192.168.192.1: /* Caching */

Zu allererst soll geklärt werden, was ein Webservices ist:
<blockquote>Ein Webservice (auch Webdienst) stellt eine Schnittstelle für die Maschine-zu-Maschine- oder Anwendungs-Kommunikation über Rechnernetze wie das Internet zur Verfügung. Dabei werden Daten ausgetauscht und auf entfernten Computern (Servern) Funktionen aufgerufen. Jeder Webservice besitzt einen Uniform Resource Identifier (URI), über den er eindeutig identifizierbar ist, sowie je nach Implementierung eine Schnittstellenbeschreibung in maschinenlesbarem Format (als XML-Artefakt, z. B. WSDL), die definiert, wie mit dem Webservice zu interagieren ist. Die Kommunikation kann über Protokolle aus dem Internetkontext wie HTTP oder HTTPS erfolgen; über diese Protokolle wiederum kann beispielsweise XML oder JSON übertragen werden. Ein Webservice ist plattformunabhängig und steht in der Regel mehreren Programmen zum Aufrufen bereit. [https://de.wikipedia.org/wiki/Webservice]</blockquote>
Was bedeutet dies nun ganz stark vereinfacht. Ein Webservice ist ein Programm, welches auf einem Server läuft, der über das Internet erreichbar ist. Ein Client (Browser, Anwendung, App), sendet Anfragen an diesen Webservice mit einem standardisierten Protokoll (z.B.: HTTP) und erhält darauf Antworten.
 
Im folgenden wollen wir uns nun mit RESTful Webservices beschäftigen, diese erfreuen sich großer beliebtheit und stehen in Konkurrenz zu anderen Varianten wie z.b.:
* ''WSDL/Soap basierten Webservices'' - Stark antiquiertes Konezpt
* ''GraphQL basierten Webservices'' - Damit werden unzulänglichkeiten bei RESTful Webservices behoben, jedoch wird auch auf die einheitliche Schnittstelle verzichtet

= RESTful Webservice =
Ein RESTful Webservice ist nicht eine konkrete Implementierung, es sind vielmehr Prinzipien und Eigenschaften die auf einen Webservice zutreffen müssen, damit es sich um einen RESTful Webservice handelt bzw. einen Webservice der auf den REST Prinzipien beruht. REST steht für '''Represential State Transfer''' und wurde von Roy Fielding "entwickelt".

== Prinzipien ==
Im folgenden wollen wir auf einige der Prinzipien eingehen. Folgender Abschnitt ist jedoch nicht vollständig, soll aber an dieser Stelle ausreichen.

=== Einheitliche Schnittstelle ===
Dies ist ein Hauptunterscheidungsmerkmal zu den meisten anderen Webservice Architekturen.
 
Wir sprechen hier von Ressourcen die einheitlich manipuliert, abgerufen und identifiziert werden können. Eine Ressource kann z.B. ein Kundenprofil sein.
==== Addressierbarkeit von Ressourcen ====
Jede Ressource hat einen eindeutigen Bezeichner und ist über eine URL erreichbar ist
 
Kunde mit der id 101 -> https://webservice.drlue.at/customer/101

==== Selbstbeschreibende Nachrichten ====
REST Nachrichten sollen selbstbeschreibend sein, dafür sollen Standardmethoden verwendet werden, meist werden hier die HTTP Methoden verwendet.
 
Betrachten wir das Beispiel des Kunden mit der Id 101 und stellen den Vergleich zu den HTTP Methoden her:
{| class="wikitable"
|-
! HTTP Methode !! URL !! Operation
|-
| GET || https://webservice.drlue.at/customer/101 || Holen der Benutzerinformation
|-
| DELETE || https://webservice.drlue.at/customer/101 || Löschen des Benutzers
|-
| PUT || https://webservice.drlue.at/customer/101 || Verändern des Benutzers, es müssen die zu ändernden Daten mitgesendet werden
|-
| POST || https://webservice.drlue.at/customer || Anlegen eines neuen Benutzers, die Benutzerdaten müssen mitgesendet werden
|}
=== Caching ===
HTTP Caching soll implementiert werden. Wobei jede Anfrage die nicht gestellt werden muss, die beste ist.
Klären wir zuerst den Begriff des Cachings. Dieses Konzept gilt natürlich in vielen Bereichen der Informatik, wir erklären den Begriff anhand des Zugriffs auf eine Ressource. Eine Ressource wird geholt, zu einem späteren Zeitpunkt wird diese Ressource erneut geholt. Hat sich diese nicht verändert, so soll sie nicht erneut übertragen werden, sondern aus dem Zwischenspeicher der Anwendung abgerufen werden. 
Durch Caching bei Webanwendungen soll die Übertragung von Daten über das Internet reduziert werden.
In folgender Tabelle wird die Funktionsweise von HTTP Caching mittels ETag beschrieben. Man beachte, die HTTP Anfragen sind ''nicht'' vollständig und beschränken sich auf die fürs Caching wesentlichen Header.
{| class="wikitable"
|+ Ablauf beim Anfragen auf eine Ressource (http://webservice.drlue.at/customer/101)
|-
! Anfrage !! Antwort !! Beschreibung
|- style="vertical-align:top;"
|
<syntaxhighlight lang='http' line>
GET /customer/101 HTTP/1.1
Host: webservice.drlue.at
</syntaxhighlight>
                                                                          
|style="white-space: nowrap;"|
<syntaxhighlight lang='http' line>
HTTP/1.1 200 OK
Etag: "478fb2348f700"

{
"name": "luke",
"id": 101
}
</syntaxhighlight>
                                                             
|Erstmaliges holen der spezifischen Ressource. Server Antwortet mit den Daten und liefert im HTTP Header den ''ETag'' mit
|- style="vertical-align:top;"
|style="white-space: nowrap;"|
<syntaxhighlight lang='http' line="'line'">
GET /customer/101 HTTP/1.1
Host: webservice.drlue.at
If-none-match: "478fb2348f700"
</syntaxhighlight>
|style="white-space: nowrap;"|
<syntaxhighlight lang='http' line="'line'">
HTTP/1.1 304 Not Modified
Etag: "478fb2348f700"
</syntaxhighlight>
|Eine weitere Anfrage des Clients erfolgt mit dem ''ETag'' nun aber im ''If-none-match'' Header. Man könnte diese Anfrage wie folgt interpretieren: Gib mir die Ressource nur zurück, wenn der ''ETag'' nicht mehr zutrifft. Der Server Antwortet mit dem ''HTTP Statuscode 304 Not Modified''. Dies bedeutet, es hat sich nichts geändert. Der Client wird somit darauf hingewiesen die Daten aus seinem eigenen ''Cache'' oder ''Zwischenspeicher'' zu holen.
|- style="vertical-align:top;"
|style="white-space: nowrap;"|
<syntaxhighlight lang='http' line="'line'">
GET /customer/101 HTTP/1.1
Host: webservice.drlue.at
If-none-match: "478fb2348f700"
</syntaxhighlight>
|style="white-space: nowrap;"|
<syntaxhighlight lang='http' line>
HTTP/1.1 200 OK
Etag: "497fb2348f705"

{
"name": "luke1",
"id": 101
}
</syntaxhighlight>
|Zu einem späteren Zeitpunkt holt der Client erneut die Selbe Ressource und sendet wieder den ''ETag'' mit. Die Ressource hat sich jedoch am Server geändert. Dieser sendet die Ressource dem Client zurück und sendet zusätzlich im Header den neuen ''ETag'' mit.
|}

==== Mögliche Implementierung ====
In modernen Technologien wie z.B.: Express für Node.js finden sich automatische mechanismen für die Caching implementierung über ETags. Der Ablauf ist denkbar einfach. Der Server betrachtet vor dem Absenden der Antwort an den Client deren Inhalt. Es geht hier nur um den HTTP Body, die Header spielen hier keine Rolle. Aus dem Body wird eine Hashsumme berechnet und diese wird dann als ''ETag'' verwendet.
'''Hashsumme:''' Mittels eines Hashalgorithmus wie z.b.: (SHA256, MD5, ...) kann aus einer großen Datenmenge ein "eindeutiger" Wert berechnet werden. Bei SHA256 hat dieser Wert '''immer''' eine Länge von 256 Bit, egal wie groß der Input ist. Der Wert kann natürlich nicht eindeut sein, doch die Chance ist verschwindend gering, dass für unterschiedliche Input Daten, die selbe Hashsumme gebildet wird.
Diese Implementierung bietet eine einfache Möglichkeit des Cachings um die Datenübertragung vom Client zum Server deutlich zu reduzieren. Der Body der Antwort muss ebenfalls bei jeder Antwort erstellt werden. Das bedeutet, der Server muss trotzdem Anfragen an die Datenbank stellen bzw. alles nötige um die Antwort zu erstellen muss erledigt werden.

=== Zustandslosigkeit ===

Webservices und Client Server Konzepte

2021-01-07T10:37:33Z

192.168.192.1: /* Caching */

Zu allererst soll geklärt werden, was ein Webservices ist:
<blockquote>Ein Webservice (auch Webdienst) stellt eine Schnittstelle für die Maschine-zu-Maschine- oder Anwendungs-Kommunikation über Rechnernetze wie das Internet zur Verfügung. Dabei werden Daten ausgetauscht und auf entfernten Computern (Servern) Funktionen aufgerufen. Jeder Webservice besitzt einen Uniform Resource Identifier (URI), über den er eindeutig identifizierbar ist, sowie je nach Implementierung eine Schnittstellenbeschreibung in maschinenlesbarem Format (als XML-Artefakt, z. B. WSDL), die definiert, wie mit dem Webservice zu interagieren ist. Die Kommunikation kann über Protokolle aus dem Internetkontext wie HTTP oder HTTPS erfolgen; über diese Protokolle wiederum kann beispielsweise XML oder JSON übertragen werden. Ein Webservice ist plattformunabhängig und steht in der Regel mehreren Programmen zum Aufrufen bereit. [https://de.wikipedia.org/wiki/Webservice]</blockquote>
Was bedeutet dies nun ganz stark vereinfacht. Ein Webservice ist ein Programm, welches auf einem Server läuft, der über das Internet erreichbar ist. Ein Client (Browser, Anwendung, App), sendet Anfragen an diesen Webservice mit einem standardisierten Protokoll (z.B.: HTTP) und erhält darauf Antworten.
 
Im folgenden wollen wir uns nun mit RESTful Webservices beschäftigen, diese erfreuen sich großer beliebtheit und stehen in Konkurrenz zu anderen Varianten wie z.b.:
* ''WSDL/Soap basierten Webservices'' - Stark antiquiertes Konezpt
* ''GraphQL basierten Webservices'' - Damit werden unzulänglichkeiten bei RESTful Webservices behoben, jedoch wird auch auf die einheitliche Schnittstelle verzichtet

= RESTful Webservice =
Ein RESTful Webservice ist nicht eine konkrete Implementierung, es sind vielmehr Prinzipien und Eigenschaften die auf einen Webservice zutreffen müssen, damit es sich um einen RESTful Webservice handelt bzw. einen Webservice der auf den REST Prinzipien beruht. REST steht für '''Represential State Transfer''' und wurde von Roy Fielding "entwickelt".

== Prinzipien ==
Im folgenden wollen wir auf einige der Prinzipien eingehen. Folgender Abschnitt ist jedoch nicht vollständig, soll aber an dieser Stelle ausreichen.

=== Einheitliche Schnittstelle ===
Dies ist ein Hauptunterscheidungsmerkmal zu den meisten anderen Webservice Architekturen.
 
Wir sprechen hier von Ressourcen die einheitlich manipuliert, abgerufen und identifiziert werden können. Eine Ressource kann z.B. ein Kundenprofil sein.
==== Addressierbarkeit von Ressourcen ====
Jede Ressource hat einen eindeutigen Bezeichner und ist über eine URL erreichbar ist
 
Kunde mit der id 101 -> https://webservice.drlue.at/customer/101

==== Selbstbeschreibende Nachrichten ====
REST Nachrichten sollen selbstbeschreibend sein, dafür sollen Standardmethoden verwendet werden, meist werden hier die HTTP Methoden verwendet.
 
Betrachten wir das Beispiel des Kunden mit der Id 101 und stellen den Vergleich zu den HTTP Methoden her:
{| class="wikitable"
|-
! HTTP Methode !! URL !! Operation
|-
| GET || https://webservice.drlue.at/customer/101 || Holen der Benutzerinformation
|-
| DELETE || https://webservice.drlue.at/customer/101 || Löschen des Benutzers
|-
| PUT || https://webservice.drlue.at/customer/101 || Verändern des Benutzers, es müssen die zu ändernden Daten mitgesendet werden
|-
| POST || https://webservice.drlue.at/customer || Anlegen eines neuen Benutzers, die Benutzerdaten müssen mitgesendet werden
|}
=== Caching ===
HTTP Caching soll implementiert werden. Wobei jede Anfrage die nicht gestellt werden muss, die beste ist.
Klären wir zuerst den Begriff des Cachings. Dieses Konzept gilt natürlich in vielen Bereichen der Informatik, wir erklären den Begriff anhand des Zugriffs auf eine Ressource. Eine Ressource wird geholt, zu einem späteren Zeitpunkt wird diese Ressource erneut geholt. Hat sich diese nicht verändert, so soll sie nicht erneut übertragen werden, sondern aus dem Zwischenspeicher der Anwendung abgerufen werden. 
Durch Caching bei Webanwendungen soll die Übertragung von Daten über das Internet reduziert werden.
In folgender Tabelle wird die Funktionsweise von HTTP Caching mittels ETag beschrieben. Man beachte, die HTTP Anfragen sind ''nicht'' vollständig und beschränken sich auf die fürs Caching wesentlichen Header.
{| class="wikitable"
|+ Ablauf beim Anfragen auf eine Ressource (http://webservice.drlue.at/customer/101)
|-
! Anfrage !! Antwort !! Beschreibung
|- style="vertical-align:top;"
|
<syntaxhighlight lang='http' line>
GET /customer/101 HTTP/1.1
Host: webservice.drlue.at
</syntaxhighlight>
                                                                          
|style="white-space: nowrap;"|
<syntaxhighlight lang='http' line>
HTTP/1.1 200 OK
Etag: "478fb2348f700"

{
"name": "luke",
"id": 101
}
</syntaxhighlight>
                                                             
|Erstmaliges holen der spezifischen Ressource. Server Antwortet mit den Daten und liefert im HTTP Header den ''ETag'' mit
|- style="vertical-align:top;"
|style="white-space: nowrap;"|
<syntaxhighlight lang='http' line="'line'">
GET /customer/101 HTTP/1.1
Host: webservice.drlue.at
If-none-match: "478fb2348f700"
</syntaxhighlight>
|style="white-space: nowrap;"|
<syntaxhighlight lang='http' line="'line'">
HTTP/1.1 304 Not Modified
Etag: "478fb2348f700"
</syntaxhighlight>
|Eine weitere Anfrage des Clients erfolgt mit dem ''ETag'' nun aber im ''If-none-match'' Header. Man könnte diese Anfrage wie folgt interpretieren: Gib mir die Ressource nur zurück, wenn der ''ETag'' nicht mehr zutrifft. Der Server Antwortet mit dem ''HTTP Statuscode 304 Not Modified''. Dies bedeutet, es hat sich nichts geändert. Der Client wird somit darauf hingewiesen die Daten aus seinem eigenen ''Cache'' oder ''Zwischenspeicher'' zu holen.
|- style="vertical-align:top;"
|style="white-space: nowrap;"|
<syntaxhighlight lang='http' line="'line'">
GET /customer/101 HTTP/1.1
Host: webservice.drlue.at
If-none-match: "478fb2348f700"
</syntaxhighlight>
|style="white-space: nowrap;"|
<syntaxhighlight lang='http' line>
HTTP/1.1 200 OK
Etag: "497fb2348f705"

{
"name": "luke1",
"id": 101
}
</syntaxhighlight>
|Zu einem späteren Zeitpunkt holt der Client erneut die Selbe Ressource und sendet wieder den ''ETag'' mit. Die Ressource hat sich jedoch am Server geändert. Dieser sendet die Ressource dem Client zurück und sendet zusätzlich im Header den neuen ''ETag'' mit.
|}

=== Zustandslosigkeit ===

Webservices und Client Server Konzepte

2021-01-07T10:37:10Z

192.168.192.1: /* Caching */

Zu allererst soll geklärt werden, was ein Webservices ist:
<blockquote>Ein Webservice (auch Webdienst) stellt eine Schnittstelle für die Maschine-zu-Maschine- oder Anwendungs-Kommunikation über Rechnernetze wie das Internet zur Verfügung. Dabei werden Daten ausgetauscht und auf entfernten Computern (Servern) Funktionen aufgerufen. Jeder Webservice besitzt einen Uniform Resource Identifier (URI), über den er eindeutig identifizierbar ist, sowie je nach Implementierung eine Schnittstellenbeschreibung in maschinenlesbarem Format (als XML-Artefakt, z. B. WSDL), die definiert, wie mit dem Webservice zu interagieren ist. Die Kommunikation kann über Protokolle aus dem Internetkontext wie HTTP oder HTTPS erfolgen; über diese Protokolle wiederum kann beispielsweise XML oder JSON übertragen werden. Ein Webservice ist plattformunabhängig und steht in der Regel mehreren Programmen zum Aufrufen bereit. [https://de.wikipedia.org/wiki/Webservice]</blockquote>
Was bedeutet dies nun ganz stark vereinfacht. Ein Webservice ist ein Programm, welches auf einem Server läuft, der über das Internet erreichbar ist. Ein Client (Browser, Anwendung, App), sendet Anfragen an diesen Webservice mit einem standardisierten Protokoll (z.B.: HTTP) und erhält darauf Antworten.
 
Im folgenden wollen wir uns nun mit RESTful Webservices beschäftigen, diese erfreuen sich großer beliebtheit und stehen in Konkurrenz zu anderen Varianten wie z.b.:
* ''WSDL/Soap basierten Webservices'' - Stark antiquiertes Konezpt
* ''GraphQL basierten Webservices'' - Damit werden unzulänglichkeiten bei RESTful Webservices behoben, jedoch wird auch auf die einheitliche Schnittstelle verzichtet

= RESTful Webservice =
Ein RESTful Webservice ist nicht eine konkrete Implementierung, es sind vielmehr Prinzipien und Eigenschaften die auf einen Webservice zutreffen müssen, damit es sich um einen RESTful Webservice handelt bzw. einen Webservice der auf den REST Prinzipien beruht. REST steht für '''Represential State Transfer''' und wurde von Roy Fielding "entwickelt".

== Prinzipien ==
Im folgenden wollen wir auf einige der Prinzipien eingehen. Folgender Abschnitt ist jedoch nicht vollständig, soll aber an dieser Stelle ausreichen.

=== Einheitliche Schnittstelle ===
Dies ist ein Hauptunterscheidungsmerkmal zu den meisten anderen Webservice Architekturen.
 
Wir sprechen hier von Ressourcen die einheitlich manipuliert, abgerufen und identifiziert werden können. Eine Ressource kann z.B. ein Kundenprofil sein.
==== Addressierbarkeit von Ressourcen ====
Jede Ressource hat einen eindeutigen Bezeichner und ist über eine URL erreichbar ist
 
Kunde mit der id 101 -> https://webservice.drlue.at/customer/101

==== Selbstbeschreibende Nachrichten ====
REST Nachrichten sollen selbstbeschreibend sein, dafür sollen Standardmethoden verwendet werden, meist werden hier die HTTP Methoden verwendet.
 
Betrachten wir das Beispiel des Kunden mit der Id 101 und stellen den Vergleich zu den HTTP Methoden her:
{| class="wikitable"
|-
! HTTP Methode !! URL !! Operation
|-
| GET || https://webservice.drlue.at/customer/101 || Holen der Benutzerinformation
|-
| DELETE || https://webservice.drlue.at/customer/101 || Löschen des Benutzers
|-
| PUT || https://webservice.drlue.at/customer/101 || Verändern des Benutzers, es müssen die zu ändernden Daten mitgesendet werden
|-
| POST || https://webservice.drlue.at/customer || Anlegen eines neuen Benutzers, die Benutzerdaten müssen mitgesendet werden
|}
=== Caching ===
HTTP Caching soll implementiert werden. Wobei jede Anfrage die nicht gestellt werden muss, die beste ist. 
Klären wir zuerst den Begriff des Cachings. Dieses Konzept gilt natürlich in vielen Bereichen der Informatik, wir erklären den Begriff anhand des Zugriffs auf eine Ressource. Eine Ressource wird geholt, zu einem späteren Zeitpunkt wird diese Ressource erneut geholt. Hat sich diese nicht verändert, so soll sie nicht erneut übertragen werden, sondern aus dem Zwischenspeicher der Anwendung abgerufen werden. 
Durch Caching bei Webanwendungen soll die Übertragung von Daten über das Internet reduziert werden.
In folgender Tabelle wird die Funktionsweise von HTTP Caching mittels ETag beschrieben. Man beachte, die HTTP Anfragen sind ''nicht'' vollständig und beschränken sich auf die fürs Caching wesentlichen Header.
{| class="wikitable"
|+ Ablauf beim Anfragen auf eine Ressource (http://webservice.drlue.at/customer/101)
|-
! Anfrage !! Antwort !! Beschreibung
|- style="vertical-align:top;"
|
<syntaxhighlight lang='http' line>
GET /customer/101 HTTP/1.1
Host: webservice.drlue.at
</syntaxhighlight>
                                                                          
|style="white-space: nowrap;"|
<syntaxhighlight lang='http' line>
HTTP/1.1 200 OK
Etag: "478fb2348f700"

{
"name": "luke",
"id": 101
}
</syntaxhighlight>
                                                             
|Erstmaliges holen der spezifischen Ressource. Server Antwortet mit den Daten und liefert im HTTP Header den ''ETag'' mit
|- style="vertical-align:top;"
|style="white-space: nowrap;"|
<syntaxhighlight lang='http' line="'line'">
GET /customer/101 HTTP/1.1
Host: webservice.drlue.at
If-none-match: "478fb2348f700"
</syntaxhighlight>
|style="white-space: nowrap;"|
<syntaxhighlight lang='http' line="'line'">
HTTP/1.1 304 Not Modified
Etag: "478fb2348f700"
</syntaxhighlight>
|Eine weitere Anfrage des Clients erfolgt mit dem ''ETag'' nun aber im ''If-none-match'' Header. Man könnte diese Anfrage wie folgt interpretieren: Gib mir die Ressource nur zurück, wenn der ''ETag'' nicht mehr zutrifft. Der Server Antwortet mit dem ''HTTP Statuscode 304 Not Modified''. Dies bedeutet, es hat sich nichts geändert. Der Client wird somit darauf hingewiesen die Daten aus seinem eigenen ''Cache'' oder ''Zwischenspeicher'' zu holen.
|- style="vertical-align:top;"
|style="white-space: nowrap;"|
<syntaxhighlight lang='http' line="'line'">
GET /customer/101 HTTP/1.1
Host: webservice.drlue.at
If-none-match: "478fb2348f700"
</syntaxhighlight>
|style="white-space: nowrap;"|
<syntaxhighlight lang='http' line>
HTTP/1.1 200 OK
Etag: "497fb2348f705"

{
"name": "luke1",
"id": 101
}
</syntaxhighlight>
|Zu einem späteren Zeitpunkt holt der Client erneut die Selbe Ressource und sendet wieder den ''ETag'' mit. Die Ressource hat sich jedoch am Server geändert. Dieser sendet die Ressource dem Client zurück und sendet zusätzlich im Header den neuen ''ETag'' mit.
|}

=== Zustandslosigkeit ===

Webservices und Client Server Konzepte

2021-01-07T10:31:56Z

192.168.192.1: /* Caching */

Webservices und Client Server Konzepte

2021-01-07T10:31:47Z

192.168.192.1: /* Caching */

Webservices und Client Server Konzepte

2021-01-07T10:31:14Z

192.168.192.1: /* Caching */

Webservices und Client Server Konzepte

2021-01-07T10:30:08Z

192.168.192.1: /* Caching */

Webservices und Client Server Konzepte

2021-01-07T10:28:03Z

192.168.192.1: /* Caching */

Webservices und Client Server Konzepte

2021-01-07T10:17:11Z

192.168.192.1: /* Addressierbarkeit von Ressourcen */

Algorithmen und Datenstrukturen

2021-01-06T09:04:13Z

192.168.96.1: /* Code beispiel */

Im folgenden Themenbereich geht es um Algorithmen und Datenstrukturen und um die Landau Symbole oder O - Notation und wie diese im Kontext von Algorithmen und Datenstrukturen verwendet wird.
 
Bei den Alghorithmen werden wir uns auf Sortieralgorithmen beschränken, uns mit deren Laufzeitanalyse (O - Notation) befassen
 
Bei den Datenstrukturen beschränken wir uns auf Arrays, Listen und Bäume und ebenfalls um deren Laufzeitanalyse für verschiedene Operationen

__TOC__

= Landau Symbole oder O - Notation =

'''Landau-Symbole''' (auch '''O-Notation''') werden in der Mathematik und in der Informatik verwendet, um das asymptotische Verhalten von Funktionen und Folgen zu beschreiben. In der Informatik werden sie bei der Analyse von Algorithmen verwendet und geben ein Maß für die Anzahl der Elementarschritte oder der Speichereinheiten in Abhängigkeit von der Größe des gegebenen Problems an. (siehe [[https://de.wikipedia.org/wiki/Landau-Symbole]]).
 
Unter asymptotischem Verhalten verstehen wir hier das Grenzverhalten eines Algorithmus, vereinfacht gesagt, wie kann sich die Laufzeit im schlechtesten Fall entwickeln. Um das Grenzverhalten eines Algorithmus zu betrachten, analysieren wir wieviele Operationen im schlechtesten Fall im bezug auf die größe des Problems (z.B.: Anzahl der Elemente) benötigt werden. Konstante Werte können dabei vernachlässigt werden.

== Beispiel ==
Suchen des kleinsten und größten Elements in einem Array.
{| class="wikitable"
|-
| 1 || 2 || 3 || 4 || 5 || 6
|}
Um das größte Element zu finden, werden 5 Schritte benötigt, dies entspricht der Länge des Arrays - 1. Für die Suche des größten Elements benötigen wir ebenfalls 5 Schritte. Somit ist die Laufzeit für unseren Algorithmus '''2 * (n - 1)''', die Konstanten werden entfernt: '''O(n)'''
<syntaxhighlight lang='java' line="'line'">
public void findMinAndMax(int[] arr) {
int min = arr[0];
int max = arr[0];
for(int i=1; i<arr.length; i++) {
min = Math.min(min, arr[i]);
}
for(int i=1; i<arr.length; i++) {
max = Math.max(max, arr[i]);
}
System.out.println("Min: "+min);
System.out.println("Max: "+max);
}
</syntaxhighlight>
In der O - Notation werden einige gebräuchliche Schranken verwendet, wenn wir einen Algorithmus oder eine Datenstruktur analysieren, verwenden wir diese Schranken und nicht die exakte Mathematische repräsentation des Problems (siehe [[Algorithmen_und_Datenstrukturen#Bubblesort|Bubblesort]])

{| class="wikitable"
|+ Gebräuchliche Beschränkungen (es gibt viele weitere!)
|-
! O - Notation !! Bedeutung !! Beispiel
|-
| O(1) || Das Laufzeitverhalten hängt nicht von der Anzahl der Elemente ab und ist konstant || Element an der Stelle N aus einem Array oder einer ArrayListe holen
|-
| O(n) || Das Laufzeitverhalten verlängert sich linear mit der Anzahl der Element || Suchen eines bestimmten Elements in einem unsortierten Array
|-
| O(n log n) || Super lineares Wachstum :-DDD || Mergesort, Heapsort, durchschnittsfall Quicksort
|-
| O(n2) || Quadratisches Wachstum, die Laufzeit wächst quadratisch zur Anzahl der Elemente || Bubblesort
|-
| O(log2n) || 2er Logarithmisches Wachstum || Suche im Binärbaum
|}

= Datenstrukturen =

In der Informatik und Softwaretechnik ist eine Datenstruktur ein Objekt, welches zur Speicherung und Organisation von Daten dient. Es handelt sich um eine Struktur, weil die Daten in einer bestimmten Art und Weise angeordnet und verknüpft werden, um den Zugriff auf sie und ihre Verwaltung effizient zu ermöglichen. (siehe [[https://de.wikipedia.org/wiki/Datenstruktur]])
 
Im folgenden sollen einige Datenstrukturen erläutert werden, für jede Datenstruktur gibt es andere Einsatzgebiete die für deren Eigenschaften optimal sind.

== Array ==
Ein Array oder Feld ist eine sehr effiziente doch wenig dynamische Datenstruktur. In nahezu allen Programmiersprachen findet sich diese Datenstruktur wieder. Weiter ist auch ein dynamisches vergrößern oder verkleinern in einigen Programmiersprachen automatisch implementiert ('''Javascript''').
 
Gehen wir jedoch von Programmiersprachen wie '''Java''' oder '''C''' aus, so hat ein Array immer eine fixe größe. Das heißt, zur Laufzeit (nach dem das Programm compiliert und gestartet wurde) kann diese nicht verändert werden.
=== Vorteile ===
* '''Der Speicheroverhead ist sehr gering''' - Es wird nur der Speicher reserviert, der für die Anzahl der Elemente benötigt wird.
* '''Geringe Zugriffszeit''' - Wird ein Element an einer stelle angesprochen, so kann für den Zugriff die Exakte Speicheradresse berechnet werden.

=== Nachteile ===
* '''Wenig flexibel''' - Wie bereits erwähnt, muss die größe meist fix definiert werden. Eine vergrößerung/verkleinerung ist nicht möglich, ermöglicht die Programmiersprache dies, so hat dies meist zurfolge, dass das Array neu erstellt wird, und die Elemente kopiert werden müssen.

=== Einsatzgebiete ===
Überall dort, wo eine fixe Speichergröße benötigt und effizient wichtig ist, dort sollte die Verwendung von Arrays in betracht gezogen werden.
* '''Bildmanipulation''' - Wird ein Bild zur Bearbeitung geladen, so kann die ''Bitmap'' in einem Array gespeichert werden. jedes Element im Array entspricht dann einem Pixel.
* '''Puffern von Daten''' - Beim Lesen und Schreiben werden Daten meist in einem Array zwischengespeichert (gepuffert). Danach kann die Bearbeitung erfolgen. Weiters kann bei jedem Lese oder Schreibvorgang erneut das selbe Array verwendet werden, was die Effizienz weiter erhöht.
* '''Jegliches Schachbrettartige Problem mit fixer Größe''' - Schiffe versenken, Schach,...

== Liste ==
Die Liste ist eine sehr gebräuchliche Datenstruktur. Sie ist gekennzeichnet durch, je nach implementierung, gute Zugriffszeiten oder erhöhte Flexibilität.
 
Beziehen wir uns auf die Programmiersprache Java, so ist die Liste ein '''Interface''', das heißt eine Schnittstelle. Diese Schnittstelle definiert einige '''Methoden''' die eine Implementierung erfüllen muss. Einige davon wären:
* <syntaxhighlight lang="java" inline>E get(int index)</syntaxhighlight> - Gibt das Element an der Stelle '''index''' aus
* <syntaxhighlight lang="java" inline>E remove(int index)</syntaxhighlight> - Gibt das Element an der Stelle '''index''' aus
* <syntaxhighlight lang="java" inline>boolean add(E element)</syntaxhighlight> - Fügt ein Element an das Ende der Liste an
* <syntaxhighlight lang="java" inline>boolean add(int index, E element)</syntaxhighlight> - Fügt ein Element an einer bestimmten Position ein, und schiebt nachfolgende Elemente nach rechts (Index wird erhöht)
* ...
Hier ist nun ersichtlich, dass die Flexibilität der Liste ein essenzieller Bestandteil der Definition ist.
 
Anbei einige Implementierungen des Interfaces List.
=== ArrayList ===
Die ArrayList vereint die Eigenschaften einer Liste und eines Arrays. Die interne Implementierung verwendet ein Array von fixer größe um Elemente zu speichern. Wird diese fixe größe überschritten, so wird intern ein neues Array angelegt, je nach implementierung mit einem gewissen Vergrößerungsfaktor. Nach dem neuanlegen des internen Arrays, werden alle Elemente kopiert und in das neue Array eingefügt. Werden Elemente gelöscht, so müssen die Elemente nach dem gelöschten Element um eins nach links verschoben werden.
[[Datei:Removing Element from ArrayList diagram.png|mini|none|400px|Element wird aus ArrayListe entfernt. Quelle: https://beginnersbook.com/2013/12/java-arraylist/]]
In Java wird die größe des internen Arrays nicht automatisch reduziert, wenn Elemente gelöscht werden. Dafür gibt es die Methode <syntaxhighlight lang="java" inline>myArrayList.trim()</syntaxhighlight>

==== Vorteile ====
* '''Relativ geringer Speicheroverhead''' - Dies verhält sich ähnlich wie beim Array. Jedoch können in der ArrayList keine primitiven Datentypen gespeichert werden. Dies bedeutet, es wird nur ein Array von Referenzen erstellt. In jedem Platz findet sich eine Referenz auf das wirkliche Objekt. Dies bedeutet in Bezug auf primitive Datentypen einen weit höheren Speicherbedarf als bei einem Array.
* '''Geringe Zugriffszeit''' - Wird ein Element an einer stelle angesprochen, so kann für den Zugriff die Exakte Speicheradresse berechnet werden.

==== Nachteile ====
* '''Ineffizientes Löschen''' - Laufzeit beim Löschen nicht optimal, Elemente müssen verschoben werden.
* '''Ineffizientes Einfügen''' - Laufzeit beim Einfügen von Elementen an einer gewissen Stelle langsam, wie beim löschen müssen alle Nachfolgenden Elemente verschoben werden.
* '''Ineffizientes Hinzufügen, wenn internes Array voll''' - Laufzeit beim Hinzufügen von Elementen bei vollem Array langsam, ein neues Array muss erstellt werden und alle Elemente

==== Code beispiel ====
<syntaxhighlight lang='Java' line="'line'>
List<Integer> myArrayList = new ArrayList<>();
myArrayList.add(1);
myArrayList.add(1);
myArrayList.add(1);
myArrayList.remove(0);
System.out.println("Element an der Stelle 2: "+myArrayList.get(1));
</syntaxhighlight>
* Zeile 1) Die die ArrayListe wird erzeugt und einer Variable des Typs List zugewiesen. Warum ist das möglich? Weil ArrayList das Interface List implementiert. D.h.: Eine ArrayList ist eine List.
* Zeile 2) - 4) fügen dem Array einen int hinzu. Hier ist zu beachten, der primitive Datentyp '''int''' wird automatisch in die Klasse '''Integer''' umgewandelt. Dieser mechanismus nennt sich Autoboxing.
* Zeile 5) Das Element an der Stelle 0 wird aus der ArrayList entfernt
* Zeile 6) Ausgabe des Elements an der Stelle 2 (Index 1)

=== Einsatzgebiete ===
Die Einsatzgebiete überschneiden sich mit herkömmlichen Arrays. Benötigt man mehr flexibilität und soll '''nicht''' mit primitiven Datentypen gearbeitet werden, so kann anstatt eines Arrays die ArrayListe verwendet werden. Ist die Anzahl der Elemente start fluktuierend (oftmaliges löschen/einfügen/hinzufügen), so sollte man aus oben genannten Gründen auf eine andere Datenstruktur ausweichen.

=== LinkedList oder verkettete Liste ===
Die verkettete Liste ist eine sehr dynamische Datenstruktur. Ihre Größe ist flexibel. Die Daten werden in Knoten gehalten, welche im Falle der einfach verketteten Liste auf den Nachfolger und bei der doppelt verketteten Liste zusätzlich auf den Vorgänger Knoten zeigen. Elemente können einfach an bestimmten Stellen eingefügt oder gelöscht werden, es müssen lediglich die Nachfolger bzw. Vorgänger aktualisiert werden.
[[Datei:Singly linked list and doubly linked list in Java.jpg|mini|none|Einfach und doppelt verkettete Liste. Quelle: https://www.java67.com/2016/01/how-to-implement-singly-linked-list-in-java-using-generics-example.html]]

==== Vorteile ====
* '''Einfügen und Löschen effizient''' - Es müssen lediglich die Zeiger auf den Vorgänger/Nachfolger geändert werden.
* '''Speicherbedarf flexibel''' - Der Speicherbedarf wächst und schrumpft mit der Anzahl der Elemente.

==== Nachteile ====
* '''Zufälliger Zugriff langsam''' - Werden in der LinkedList Elemente mit ihrem Index angesprochen, so muss zuerst die komplette Liste bis zum entsprechenden Index durchlaufen werden.
* '''Speicheroverhead''' - Da die Daten in Knoten gespeichert werden müssen entsteht automatisch ein Speicheroverhead.

==== Einsatzgebiete ====
* Wenn die größe der Liste stark variiert, d.h. oftmals Elemente eingefügt, gelöscht und hinzugefügt werden und '''kein''' zufälliger Zugriff benötigt wird.

==== Code Beispiel ====
''Hinzufügen eines Elements''
<syntaxhighlight lang='Java' line="'line'">
public boolean add(Integer element) {
Node newNode = new Node(element);
if(root == null) {
root = newNode;
} else {
Node current = root;
while(current.next() != null) {
current = current.next();
}
current.setNext(newNode);
}
return true;
}
</syntaxhighlight>

''Holen eines Elements''
<syntaxhighlight lang='Java' line="'line'">
public int get(int index) {
Node current = root;
for(int i=0; i<index && current != null; i++) {
current = current.next();
}
if(current == null) {
throw new IndexOutOfBoundsException();
}
return current.getValue();
}
</syntaxhighlight>

== Assoziatives Array ==
Das '''assoziative Array''' oder auch Map, ist eine Sammlung von '''Key''', '''Value''' Paaren. Sie eignet sich sehr gut dafür, für einen bestimmten Schlüssel einen Wert zu hinterlegen. Die Operationen, einfügen, löschen, abrufen, sind Konstant und weisen im Normalfall ein Laufzeitverhalten von O(1) auf. Die Reihenfolge der Element ist nicht definiert.

== Bäume ==
Bäume sind Datenstrukturen, welche im Kontext von Suchstrukturen, automatisch einer gewissen Ordnung folgen. Bereits nach dem Einfügen sind diese Element sortiert.

==== Code ====
Sortierte Ausgabe eines binären Suchbaums (In-Order)
<syntaxhighlight lang='Java' line="'line'">
public void print(NOde node) {
if(node == null) {
return;
}
//Rekursiver aufruf für den Linken Teilbaum
print(node.getLeft());
System.out.print(" "+node.getValue()+" ");
print(node.getRight());
}

= Sortieralgorithmen =
Sortieralgorithmen werden benötigt um Datenstrukturen nach gewissen Kriterien zu sortieren. Dazu müssen die Elemente natürlich vergleichbar sein, d.h. es muss möglich sein herauszufinden ob ein Element "größer" oder "kleiner" als ein anderes ist.

== Eigenschaften ==
Sortieralgorithmen können über mehrere Eigenschaften verfügen.
=== In-Place ===
Das bedeutet der Sortieralgorithmus benötigt "keinen" weiteren Speicherplatz beim sortieren, bzw. wenn der Speicherbedarf konstant ist, und nicht mit der Anzahl der Elemente wächst. Z.b. der Sortieralgorithmus Mergesort, teilt die Daten der bestehenden Liste in Sublisten auf, er ist somit nicht In-Place.
=== Stabil ===
Ein Sortieralgorithmus arbeitet stabil, wenn dieser eine bestehende korrekte Ordnung nicht verändert.

== Bubblesort ==
Bubblesort ist ein vergleichsweise akademischer Algorithmus. Er ist wenig effizient, arbeitet jedoch '''Stabil''' und '''In-Place'''.
[[Datei:Bubble-sort-example-300px.gif|mini|none|Funktionsweise Bubblesort. Quelle: https://de.wikipedia.org/wiki/Bubblesort]]

=== Code ===
Bubblesort in Java
<syntaxhighlight lang='Java' line="'line'">
public class Bubblesort {
public static void sort(int[] arr) {
int operations = 0;
int n = arr.length;
boolean swapped = false;
do {
swapped = false;
for (int i = 0; i < n - 1; i++) {
operations++;
if (arr[i] > arr[i + 1]) {
int tmp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = tmp;
swapped = true;
}
}
// Letztes Element ist an der richtigen stelle, n um 1 reduzieren
n = n - 1;
} while (swapped);
System.out.println("Operations: " + operations);
}

public static void main(String[] args) {
int[] arr = new int[] { 1, 2, 3, 4, 5, 6 };
sort(arr);
arr = new int[] { 6, 5, 4, 3, 2, 1 };
sort(arr);
arr = new int[] { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 };
sort(arr);
}
}

</syntaxhighlight>

=== Laufzeitanalyse ===
Für die Laufzeitanalyse verwenden wir die maximal mögliche Laufzeit.
Betrachten wir hierfür folgendes Array:
10,8,5,3,2,1
* 1) Durchlauf: Die Zahl 10 wird mit 8,5,3,2 und 1 verglichen und vertauscht.
* 2) Durchlauf: Die Zahl 8 wird mit 5,3,2 und 1 verglichen und vertauscht, '''mit 10 muss nichtmehr verglichen werden'''.
* 3) Durchlauf: Die Zahl 5 wird mit 3,2 und 1 verglichen und vertauscht, '''mit 10, 8 muss nichtmehr verglichen werden'''.
* 4) Durchlauf: Die Zahl 3 wird mit 2 und 1 verglichen und vertauscht, '''mit 10, 8, 5 muss nichtmehr verglichen werden'''.
* 5) Durchlauf: Die Zahl 2 wird mit 1 verglichen und vertauscht, '''mit 10, 8, 5, 3 muss nichtmehr verglichen werden'''.
* Ende, die Zahl 1 muss nichtmehr verglichen werden.

Vergleichen und vertauschen betrachten wir nun als eine Operation.

* 1) Durchlauf -> 5 Operationen
* 2) Durchlauf -> 4 Operationen
* 3) Durchlauf -> 3 Operationen
* 4) Durchlauf -> 2 Operationen
* 5) Durchlauf -> 1 Operation

Das sind für ein Array der Länge 6, 15 Operationen.

==== Die allgemeine Formel lautet ====
* 1) (n-1) + (n-2) + ... 1
* 2) ''Das ist ja der kleine Gauß minus n:'' (n * (n + 1))/2 - n
* 3) (n2 + n - 2*n)/2
* 4) (n2 - n)/2
* 5) 1/2*(n2 - n)
* 6) n2 - n -> Konstante Werte werden bei der O - Notation entfernt
* 7) n2 -> n ist zu n2 vernachlässigbar und wird entfernt

==== Laufzeit ====
'''Somit ist die Laufzeit von Bubblesort O(n2)'''
==== Laufzeit Bestcase ====
Liegt bereits eine sortierte Liste vor, so benötigt Bubblesort nur einen Durchlauf. Dabei erfolgen '''n - 1''' vergleiche. Die Konstante wird entfernt.
 
'''Die Laufzeit im Bestcase ist O(n)'''

Algorithmen und Datenstrukturen

2021-01-06T09:03:25Z

192.168.96.1: /* Datenstrukturen */

Im folgenden Themenbereich geht es um Algorithmen und Datenstrukturen und um die Landau Symbole oder O - Notation und wie diese im Kontext von Algorithmen und Datenstrukturen verwendet wird.
 
Bei den Alghorithmen werden wir uns auf Sortieralgorithmen beschränken, uns mit deren Laufzeitanalyse (O - Notation) befassen
 
Bei den Datenstrukturen beschränken wir uns auf Arrays, Listen und Bäume und ebenfalls um deren Laufzeitanalyse für verschiedene Operationen

__TOC__

= Landau Symbole oder O - Notation =

'''Landau-Symbole''' (auch '''O-Notation''') werden in der Mathematik und in der Informatik verwendet, um das asymptotische Verhalten von Funktionen und Folgen zu beschreiben. In der Informatik werden sie bei der Analyse von Algorithmen verwendet und geben ein Maß für die Anzahl der Elementarschritte oder der Speichereinheiten in Abhängigkeit von der Größe des gegebenen Problems an. (siehe [[https://de.wikipedia.org/wiki/Landau-Symbole]]).
 
Unter asymptotischem Verhalten verstehen wir hier das Grenzverhalten eines Algorithmus, vereinfacht gesagt, wie kann sich die Laufzeit im schlechtesten Fall entwickeln. Um das Grenzverhalten eines Algorithmus zu betrachten, analysieren wir wieviele Operationen im schlechtesten Fall im bezug auf die größe des Problems (z.B.: Anzahl der Elemente) benötigt werden. Konstante Werte können dabei vernachlässigt werden.

== Beispiel ==
Suchen des kleinsten und größten Elements in einem Array.
{| class="wikitable"
|-
| 1 || 2 || 3 || 4 || 5 || 6
|}
Um das größte Element zu finden, werden 5 Schritte benötigt, dies entspricht der Länge des Arrays - 1. Für die Suche des größten Elements benötigen wir ebenfalls 5 Schritte. Somit ist die Laufzeit für unseren Algorithmus '''2 * (n - 1)''', die Konstanten werden entfernt: '''O(n)'''
<syntaxhighlight lang='java' line="'line'">
public void findMinAndMax(int[] arr) {
int min = arr[0];
int max = arr[0];
for(int i=1; i<arr.length; i++) {
min = Math.min(min, arr[i]);
}
for(int i=1; i<arr.length; i++) {
max = Math.max(max, arr[i]);
}
System.out.println("Min: "+min);
System.out.println("Max: "+max);
}
</syntaxhighlight>
In der O - Notation werden einige gebräuchliche Schranken verwendet, wenn wir einen Algorithmus oder eine Datenstruktur analysieren, verwenden wir diese Schranken und nicht die exakte Mathematische repräsentation des Problems (siehe [[Algorithmen_und_Datenstrukturen#Bubblesort|Bubblesort]])

{| class="wikitable"
|+ Gebräuchliche Beschränkungen (es gibt viele weitere!)
|-
! O - Notation !! Bedeutung !! Beispiel
|-
| O(1) || Das Laufzeitverhalten hängt nicht von der Anzahl der Elemente ab und ist konstant || Element an der Stelle N aus einem Array oder einer ArrayListe holen
|-
| O(n) || Das Laufzeitverhalten verlängert sich linear mit der Anzahl der Element || Suchen eines bestimmten Elements in einem unsortierten Array
|-
| O(n log n) || Super lineares Wachstum :-DDD || Mergesort, Heapsort, durchschnittsfall Quicksort
|-
| O(n2) || Quadratisches Wachstum, die Laufzeit wächst quadratisch zur Anzahl der Elemente || Bubblesort
|-
| O(log2n) || 2er Logarithmisches Wachstum || Suche im Binärbaum
|}

= Datenstrukturen =

In der Informatik und Softwaretechnik ist eine Datenstruktur ein Objekt, welches zur Speicherung und Organisation von Daten dient. Es handelt sich um eine Struktur, weil die Daten in einer bestimmten Art und Weise angeordnet und verknüpft werden, um den Zugriff auf sie und ihre Verwaltung effizient zu ermöglichen. (siehe [[https://de.wikipedia.org/wiki/Datenstruktur]])
 
Im folgenden sollen einige Datenstrukturen erläutert werden, für jede Datenstruktur gibt es andere Einsatzgebiete die für deren Eigenschaften optimal sind.

== Array ==
Ein Array oder Feld ist eine sehr effiziente doch wenig dynamische Datenstruktur. In nahezu allen Programmiersprachen findet sich diese Datenstruktur wieder. Weiter ist auch ein dynamisches vergrößern oder verkleinern in einigen Programmiersprachen automatisch implementiert ('''Javascript''').
 
Gehen wir jedoch von Programmiersprachen wie '''Java''' oder '''C''' aus, so hat ein Array immer eine fixe größe. Das heißt, zur Laufzeit (nach dem das Programm compiliert und gestartet wurde) kann diese nicht verändert werden.
=== Vorteile ===
* '''Der Speicheroverhead ist sehr gering''' - Es wird nur der Speicher reserviert, der für die Anzahl der Elemente benötigt wird.
* '''Geringe Zugriffszeit''' - Wird ein Element an einer stelle angesprochen, so kann für den Zugriff die Exakte Speicheradresse berechnet werden.

=== Nachteile ===
* '''Wenig flexibel''' - Wie bereits erwähnt, muss die größe meist fix definiert werden. Eine vergrößerung/verkleinerung ist nicht möglich, ermöglicht die Programmiersprache dies, so hat dies meist zurfolge, dass das Array neu erstellt wird, und die Elemente kopiert werden müssen.

=== Einsatzgebiete ===
Überall dort, wo eine fixe Speichergröße benötigt und effizient wichtig ist, dort sollte die Verwendung von Arrays in betracht gezogen werden.
* '''Bildmanipulation''' - Wird ein Bild zur Bearbeitung geladen, so kann die ''Bitmap'' in einem Array gespeichert werden. jedes Element im Array entspricht dann einem Pixel.
* '''Puffern von Daten''' - Beim Lesen und Schreiben werden Daten meist in einem Array zwischengespeichert (gepuffert). Danach kann die Bearbeitung erfolgen. Weiters kann bei jedem Lese oder Schreibvorgang erneut das selbe Array verwendet werden, was die Effizienz weiter erhöht.
* '''Jegliches Schachbrettartige Problem mit fixer Größe''' - Schiffe versenken, Schach,...

== Liste ==
Die Liste ist eine sehr gebräuchliche Datenstruktur. Sie ist gekennzeichnet durch, je nach implementierung, gute Zugriffszeiten oder erhöhte Flexibilität.
 
Beziehen wir uns auf die Programmiersprache Java, so ist die Liste ein '''Interface''', das heißt eine Schnittstelle. Diese Schnittstelle definiert einige '''Methoden''' die eine Implementierung erfüllen muss. Einige davon wären:
* <syntaxhighlight lang="java" inline>E get(int index)</syntaxhighlight> - Gibt das Element an der Stelle '''index''' aus
* <syntaxhighlight lang="java" inline>E remove(int index)</syntaxhighlight> - Gibt das Element an der Stelle '''index''' aus
* <syntaxhighlight lang="java" inline>boolean add(E element)</syntaxhighlight> - Fügt ein Element an das Ende der Liste an
* <syntaxhighlight lang="java" inline>boolean add(int index, E element)</syntaxhighlight> - Fügt ein Element an einer bestimmten Position ein, und schiebt nachfolgende Elemente nach rechts (Index wird erhöht)
* ...
Hier ist nun ersichtlich, dass die Flexibilität der Liste ein essenzieller Bestandteil der Definition ist.
 
Anbei einige Implementierungen des Interfaces List.
=== ArrayList ===
Die ArrayList vereint die Eigenschaften einer Liste und eines Arrays. Die interne Implementierung verwendet ein Array von fixer größe um Elemente zu speichern. Wird diese fixe größe überschritten, so wird intern ein neues Array angelegt, je nach implementierung mit einem gewissen Vergrößerungsfaktor. Nach dem neuanlegen des internen Arrays, werden alle Elemente kopiert und in das neue Array eingefügt. Werden Elemente gelöscht, so müssen die Elemente nach dem gelöschten Element um eins nach links verschoben werden.
[[Datei:Removing Element from ArrayList diagram.png|mini|none|400px|Element wird aus ArrayListe entfernt. Quelle: https://beginnersbook.com/2013/12/java-arraylist/]]
In Java wird die größe des internen Arrays nicht automatisch reduziert, wenn Elemente gelöscht werden. Dafür gibt es die Methode <syntaxhighlight lang="java" inline>myArrayList.trim()</syntaxhighlight>

==== Vorteile ====
* '''Relativ geringer Speicheroverhead''' - Dies verhält sich ähnlich wie beim Array. Jedoch können in der ArrayList keine primitiven Datentypen gespeichert werden. Dies bedeutet, es wird nur ein Array von Referenzen erstellt. In jedem Platz findet sich eine Referenz auf das wirkliche Objekt. Dies bedeutet in Bezug auf primitive Datentypen einen weit höheren Speicherbedarf als bei einem Array.
* '''Geringe Zugriffszeit''' - Wird ein Element an einer stelle angesprochen, so kann für den Zugriff die Exakte Speicheradresse berechnet werden.

==== Nachteile ====
* '''Ineffizientes Löschen''' - Laufzeit beim Löschen nicht optimal, Elemente müssen verschoben werden.
* '''Ineffizientes Einfügen''' - Laufzeit beim Einfügen von Elementen an einer gewissen Stelle langsam, wie beim löschen müssen alle Nachfolgenden Elemente verschoben werden.
* '''Ineffizientes Hinzufügen, wenn internes Array voll''' - Laufzeit beim Hinzufügen von Elementen bei vollem Array langsam, ein neues Array muss erstellt werden und alle Elemente

==== Code beispiel ====
<syntaxhighlight lang='Java' line="'line'>
List<Integer> myArrayList = new ArrayList<>();
myArrayList.add(1);
myArrayList.add(1);
myArrayList.add(1);
myArrayList.remove(0);
System.out.println("Element an der Stelle 2: "+myArrayList.get(1));
</syntaxhighlight>
* Zeile 1) Die die ArrayListe wird erzeugt und einer Variable des Typs List zugewiesen. Warum ist das möglich? Weil ArrayList das Interface List implementiert. D.h.: Eine ArrayList ist eine List.
* Zeile 2) - 4) fügen dem Array einen int hinzu. Hier ist zu beachten, der primitive Datentyp '''int''' wird automatisch in die Klasse '''Integer''' umgewandelt. Dieser mechanismus nennt sich Autoboxing.
* Zeile 5) Das Element an der Stelle 0 wird aus der ArrayList entfernt
* Zeile 6) Ausgabe des Elements an der Stelle 2 (Index 1)

=== Einsatzgebiete ===
Die Einsatzgebiete überschneiden sich mit herkömmlichen Arrays. Benötigt man mehr flexibilität und soll '''nicht''' mit primitiven Datentypen gearbeitet werden, so kann anstatt eines Arrays die ArrayListe verwendet werden. Ist die Anzahl der Elemente start fluktuierend (oftmaliges löschen/einfügen/hinzufügen), so sollte man aus oben genannten Gründen auf eine andere Datenstruktur ausweichen.

=== LinkedList oder verkettete Liste ===
Die verkettete Liste ist eine sehr dynamische Datenstruktur. Ihre Größe ist flexibel. Die Daten werden in Knoten gehalten, welche im Falle der einfach verketteten Liste auf den Nachfolger und bei der doppelt verketteten Liste zusätzlich auf den Vorgänger Knoten zeigen. Elemente können einfach an bestimmten Stellen eingefügt oder gelöscht werden, es müssen lediglich die Nachfolger bzw. Vorgänger aktualisiert werden.
[[Datei:Singly linked list and doubly linked list in Java.jpg|mini|none|Einfach und doppelt verkettete Liste. Quelle: https://www.java67.com/2016/01/how-to-implement-singly-linked-list-in-java-using-generics-example.html]]

==== Vorteile ====
* '''Einfügen und Löschen effizient''' - Es müssen lediglich die Zeiger auf den Vorgänger/Nachfolger geändert werden.
* '''Speicherbedarf flexibel''' - Der Speicherbedarf wächst und schrumpft mit der Anzahl der Elemente.

==== Nachteile ====
* '''Zufälliger Zugriff langsam''' - Werden in der LinkedList Elemente mit ihrem Index angesprochen, so muss zuerst die komplette Liste bis zum entsprechenden Index durchlaufen werden.
* '''Speicheroverhead''' - Da die Daten in Knoten gespeichert werden müssen entsteht automatisch ein Speicheroverhead.

==== Einsatzgebiete ====
* Wenn die größe der Liste stark variiert, d.h. oftmals Elemente eingefügt, gelöscht und hinzugefügt werden und '''kein''' zufälliger Zugriff benötigt wird.

==== Code beispiel ====
''Hinzufügen eines Elements''
<syntaxhighlight lang='Java' line="'line'">
public boolean add(Integer element) {
Node newNode = new Node(element);
if(root == null) {
root = newNode;
} else {
Node current = root;
while(current.next() != null) {
current = current.next();
}
current.setNext(newNode);
}
return true;
}
</syntaxhighlight>

''Holen eines Elements''
<syntaxhighlight lang='Java' line="'line'">
public Integer get(int index) {
Node current = root;
for(int i=0; i<index && current != null; i++) {
current = current.next();
}
if(current == null) {
throw new IndexOutOfBoundsException();
}
}
</syntaxhighlight>

== Assoziatives Array ==
Das '''assoziative Array''' oder auch Map, ist eine Sammlung von '''Key''', '''Value''' Paaren. Sie eignet sich sehr gut dafür, für einen bestimmten Schlüssel einen Wert zu hinterlegen. Die Operationen, einfügen, löschen, abrufen, sind Konstant und weisen im Normalfall ein Laufzeitverhalten von O(1) auf. Die Reihenfolge der Element ist nicht definiert.

== Bäume ==
Bäume sind Datenstrukturen, welche im Kontext von Suchstrukturen, automatisch einer gewissen Ordnung folgen. Bereits nach dem Einfügen sind diese Element sortiert.

==== Code ====
Sortierte Ausgabe eines binären Suchbaums (In-Order)
<syntaxhighlight lang='Java' line="'line'">
public void print(NOde node) {
if(node == null) {
return;
}
//Rekursiver aufruf für den Linken Teilbaum
print(node.getLeft());
System.out.print(" "+node.getValue()+" ");
print(node.getRight());
}

= Sortieralgorithmen =
Sortieralgorithmen werden benötigt um Datenstrukturen nach gewissen Kriterien zu sortieren. Dazu müssen die Elemente natürlich vergleichbar sein, d.h. es muss möglich sein herauszufinden ob ein Element "größer" oder "kleiner" als ein anderes ist.

== Eigenschaften ==
Sortieralgorithmen können über mehrere Eigenschaften verfügen.
=== In-Place ===
Das bedeutet der Sortieralgorithmus benötigt "keinen" weiteren Speicherplatz beim sortieren, bzw. wenn der Speicherbedarf konstant ist, und nicht mit der Anzahl der Elemente wächst. Z.b. der Sortieralgorithmus Mergesort, teilt die Daten der bestehenden Liste in Sublisten auf, er ist somit nicht In-Place.
=== Stabil ===
Ein Sortieralgorithmus arbeitet stabil, wenn dieser eine bestehende korrekte Ordnung nicht verändert.

== Bubblesort ==
Bubblesort ist ein vergleichsweise akademischer Algorithmus. Er ist wenig effizient, arbeitet jedoch '''Stabil''' und '''In-Place'''.
[[Datei:Bubble-sort-example-300px.gif|mini|none|Funktionsweise Bubblesort. Quelle: https://de.wikipedia.org/wiki/Bubblesort]]

=== Code ===
Bubblesort in Java
<syntaxhighlight lang='Java' line="'line'">
public class Bubblesort {
public static void sort(int[] arr) {
int operations = 0;
int n = arr.length;
boolean swapped = false;
do {
swapped = false;
for (int i = 0; i < n - 1; i++) {
operations++;
if (arr[i] > arr[i + 1]) {
int tmp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = tmp;
swapped = true;
}
}
// Letztes Element ist an der richtigen stelle, n um 1 reduzieren
n = n - 1;
} while (swapped);
System.out.println("Operations: " + operations);
}

public static void main(String[] args) {
int[] arr = new int[] { 1, 2, 3, 4, 5, 6 };
sort(arr);
arr = new int[] { 6, 5, 4, 3, 2, 1 };
sort(arr);
arr = new int[] { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 };
sort(arr);
}
}

</syntaxhighlight>

=== Laufzeitanalyse ===
Für die Laufzeitanalyse verwenden wir die maximal mögliche Laufzeit.
Betrachten wir hierfür folgendes Array:
10,8,5,3,2,1
* 1) Durchlauf: Die Zahl 10 wird mit 8,5,3,2 und 1 verglichen und vertauscht.
* 2) Durchlauf: Die Zahl 8 wird mit 5,3,2 und 1 verglichen und vertauscht, '''mit 10 muss nichtmehr verglichen werden'''.
* 3) Durchlauf: Die Zahl 5 wird mit 3,2 und 1 verglichen und vertauscht, '''mit 10, 8 muss nichtmehr verglichen werden'''.
* 4) Durchlauf: Die Zahl 3 wird mit 2 und 1 verglichen und vertauscht, '''mit 10, 8, 5 muss nichtmehr verglichen werden'''.
* 5) Durchlauf: Die Zahl 2 wird mit 1 verglichen und vertauscht, '''mit 10, 8, 5, 3 muss nichtmehr verglichen werden'''.
* Ende, die Zahl 1 muss nichtmehr verglichen werden.

Vergleichen und vertauschen betrachten wir nun als eine Operation.

* 1) Durchlauf -> 5 Operationen
* 2) Durchlauf -> 4 Operationen
* 3) Durchlauf -> 3 Operationen
* 4) Durchlauf -> 2 Operationen
* 5) Durchlauf -> 1 Operation

Das sind für ein Array der Länge 6, 15 Operationen.

==== Die allgemeine Formel lautet ====
* 1) (n-1) + (n-2) + ... 1
* 2) ''Das ist ja der kleine Gauß minus n:'' (n * (n + 1))/2 - n
* 3) (n2 + n - 2*n)/2
* 4) (n2 - n)/2
* 5) 1/2*(n2 - n)
* 6) n2 - n -> Konstante Werte werden bei der O - Notation entfernt
* 7) n2 -> n ist zu n2 vernachlässigbar und wird entfernt

==== Laufzeit ====
'''Somit ist die Laufzeit von Bubblesort O(n2)'''
==== Laufzeit Bestcase ====
Liegt bereits eine sortierte Liste vor, so benötigt Bubblesort nur einen Durchlauf. Dabei erfolgen '''n - 1''' vergleiche. Die Konstante wird entfernt.
 
'''Die Laufzeit im Bestcase ist O(n)'''

Algorithmen und Datenstrukturen

2021-01-06T08:58:20Z

192.168.96.1: /* Beispiel */

Im folgenden Themenbereich geht es um Algorithmen und Datenstrukturen und um die Landau Symbole oder O - Notation und wie diese im Kontext von Algorithmen und Datenstrukturen verwendet wird.
 
Bei den Alghorithmen werden wir uns auf Sortieralgorithmen beschränken, uns mit deren Laufzeitanalyse (O - Notation) befassen
 
Bei den Datenstrukturen beschränken wir uns auf Arrays, Listen und Bäume und ebenfalls um deren Laufzeitanalyse für verschiedene Operationen

__TOC__

= Landau Symbole oder O - Notation =

'''Landau-Symbole''' (auch '''O-Notation''') werden in der Mathematik und in der Informatik verwendet, um das asymptotische Verhalten von Funktionen und Folgen zu beschreiben. In der Informatik werden sie bei der Analyse von Algorithmen verwendet und geben ein Maß für die Anzahl der Elementarschritte oder der Speichereinheiten in Abhängigkeit von der Größe des gegebenen Problems an. (siehe [[https://de.wikipedia.org/wiki/Landau-Symbole]]).
 
Unter asymptotischem Verhalten verstehen wir hier das Grenzverhalten eines Algorithmus, vereinfacht gesagt, wie kann sich die Laufzeit im schlechtesten Fall entwickeln. Um das Grenzverhalten eines Algorithmus zu betrachten, analysieren wir wieviele Operationen im schlechtesten Fall im bezug auf die größe des Problems (z.B.: Anzahl der Elemente) benötigt werden. Konstante Werte können dabei vernachlässigt werden.

== Beispiel ==
Suchen des kleinsten und größten Elements in einem Array.
{| class="wikitable"
|-
| 1 || 2 || 3 || 4 || 5 || 6
|}
Um das größte Element zu finden, werden 5 Schritte benötigt, dies entspricht der Länge des Arrays - 1. Für die Suche des größten Elements benötigen wir ebenfalls 5 Schritte. Somit ist die Laufzeit für unseren Algorithmus '''2 * (n - 1)''', die Konstanten werden entfernt: '''O(n)'''
<syntaxhighlight lang='java' line="'line'">
public void findMinAndMax(int[] arr) {
int min = arr[0];
int max = arr[0];
for(int i=1; i<arr.length; i++) {
min = Math.min(min, arr[i]);
}
for(int i=1; i<arr.length; i++) {
max = Math.max(max, arr[i]);
}
System.out.println("Min: "+min);
System.out.println("Max: "+max);
}
</syntaxhighlight>
In der O - Notation werden einige gebräuchliche Schranken verwendet, wenn wir einen Algorithmus oder eine Datenstruktur analysieren, verwenden wir diese Schranken und nicht die exakte Mathematische repräsentation des Problems (siehe [[Algorithmen_und_Datenstrukturen#Bubblesort|Bubblesort]])

{| class="wikitable"
|+ Gebräuchliche Beschränkungen (es gibt viele weitere!)
|-
! O - Notation !! Bedeutung !! Beispiel
|-
| O(1) || Das Laufzeitverhalten hängt nicht von der Anzahl der Elemente ab und ist konstant || Element an der Stelle N aus einem Array oder einer ArrayListe holen
|-
| O(n) || Das Laufzeitverhalten verlängert sich linear mit der Anzahl der Element || Suchen eines bestimmten Elements in einem unsortierten Array
|-
| O(n log n) || Super lineares Wachstum :-DDD || Mergesort, Heapsort, durchschnittsfall Quicksort
|-
| O(n2) || Quadratisches Wachstum, die Laufzeit wächst quadratisch zur Anzahl der Elemente || Bubblesort
|-
| O(log2n) || 2er Logarithmisches Wachstum || Suche im Binärbaum
|}

= Datenstrukturen =

In der Informatik und Softwaretechnik ist eine Datenstruktur ein Objekt, welches zur Speicherung und Organisation von Daten dient. Es handelt sich um eine Struktur, weil die Daten in einer bestimmten Art und Weise angeordnet und verknüpft werden, um den Zugriff auf sie und ihre Verwaltung effizient zu ermöglichen. (siehe [[https://de.wikipedia.org/wiki/Datenstruktur]])
 
Im folgenden sollen einige Datenstrukturen erläutert werden, für jede Datenstruktur gibt es andere Einsatzgebiete die für deren Eigenschaften optimal sind.

== Array ==
Ein Array oder Feld ist eine sehr effiziente doch wenig dynamische Datenstruktur. In nahezu allen Programmiersprachen findet sich diese Datenstruktur wieder. Weiter ist auch ein dynamisches vergrößern oder verkleinern in einigen Programmiersprachen automatisch implementiert ('''Javascript''').
 
Gehen wir jedoch von Programmiersprachen wie '''Java''' oder '''C''' aus, so hat ein Array immer eine fixe größe. Das heißt, zur Laufzeit (nach dem das Programm compiliert und gestartet wurde) kann diese nicht verändert werden.
=== Vorteile ===
* '''Der Speicheroverhead ist sehr gering''' - Es wird nur der Speicher reserviert, der für die Anzahl der Elemente benötigt wird.
* '''Geringe Zugriffszeit''' - Wird ein Element an einer stelle angesprochen, so kann für den Zugriff die Exakte Speicheradresse berechnet werden.

=== Nachteile ===
* '''Wenig flexibel''' - Wie bereits erwähnt, muss die größe meist fix definiert werden. Eine vergrößerung/verkleinerung ist nicht möglich, ermöglicht die Programmiersprache dies, so hat dies meist zurfolge, dass das Array neu erstellt wird, und die Elemente kopiert werden müssen.

=== Einsatzgebiete ===
Überall dort, wo eine fixe Speichergröße benötigt und effizient wichtig ist, dort sollte die Verwendung von Arrays in betracht gezogen werden.
* '''Bildmanipulation''' - Wird ein Bild zur Bearbeitung geladen, so kann die ''Bitmap'' in einem Array gespeichert werden. jedes Element im Array entspricht dann einem Pixel.
* '''Puffern von Daten''' - Beim Lesen und Schreiben werden Daten meist in einem Array zwischengespeichert (gepuffert). Danach kann die Bearbeitung erfolgen. Weiters kann bei jedem Lese oder Schreibvorgang erneut das selbe Array verwendet werden, was die Effizienz weiter erhöht.
* '''Jegliches Schachbrettartige Problem mit fixer Größe''' - Schiffe versenken, Schach,...

== Liste ==
Die Liste ist eine sehr gebräuchliche Datenstruktur. Sie ist gekennzeichnet durch, je nach implementierung, gute Zugriffszeiten oder erhöhte Flexibilität.
 
Beziehen wir uns auf die Programmiersprache Java, so ist die Liste ein '''Interface''', das heißt eine Schnittstelle. Diese Schnittstelle definiert einige '''Methoden''' die eine Implementierung erfüllen muss. Einige davon wären:
* <syntaxhighlight lang="java" inline>E get(int index)</syntaxhighlight> - Gibt das Element an der Stelle '''index''' aus
* <syntaxhighlight lang="java" inline>E remove(int index)</syntaxhighlight> - Gibt das Element an der Stelle '''index''' aus
* <syntaxhighlight lang="java" inline>boolean add(E element)</syntaxhighlight> - Fügt ein Element an das Ende der Liste an
* <syntaxhighlight lang="java" inline>boolean add(int index, E element)</syntaxhighlight> - Fügt ein Element an einer bestimmten Position ein, und schiebt nachfolgende Elemente nach rechts (Index wird erhöht)
* ...
Hier ist nun ersichtlich, dass die Flexibilität der Liste ein essenzieller Bestandteil der Definition ist.
 
Anbei einige Implementierungen des Interfaces List.
=== ArrayList ===
Die ArrayList vereint die Eigenschaften einer Liste und eines Arrays. Die interne Implementierung verwendet ein Array von fixer größe um Elemente zu speichern. Wird diese fixe größe überschritten, so wird intern ein neues Array angelegt, je nach implementierung mit einem gewissen Vergrößerungsfaktor. Nach dem neuanlegen des internen Arrays, werden alle Elemente kopiert und in das neue Array eingefügt. Werden Elemente gelöscht, so müssen die Elemente nach dem gelöschten Element um eins nach links verschoben werden.
[[Datei:Removing Element from ArrayList diagram.png|mini|none|400px|Element wird aus ArrayListe entfernt. Quelle: https://beginnersbook.com/2013/12/java-arraylist/]]
In Java wird die größe des internen Arrays nicht automatisch reduziert, wenn Elemente gelöscht werden. Dafür gibt es die Methode <syntaxhighlight lang="java" inline>myArrayList.trim()</syntaxhighlight>

==== Vorteile ====
* '''Relativ geringer Speicheroverhead''' - Dies verhält sich ähnlich wie beim Array. Jedoch können in der ArrayList keine primitiven Datentypen gespeichert werden. Dies bedeutet, es wird nur ein Array von Referenzen erstellt. In jedem Platz findet sich eine Referenz auf das wirkliche Objekt. Dies bedeutet in Bezug auf primitive Datentypen einen weit höheren Speicherbedarf als bei einem Array.
* '''Geringe Zugriffszeit''' - Wird ein Element an einer stelle angesprochen, so kann für den Zugriff die Exakte Speicheradresse berechnet werden.

==== Nachteile ====
* '''Ineffizientes Löschen''' - Laufzeit beim Löschen nicht optimal, Elemente müssen verschoben werden.
* '''Ineffizientes Einfügen''' - Laufzeit beim Einfügen von Elementen an einer gewissen Stelle langsam, wie beim löschen müssen alle Nachfolgenden Elemente verschoben werden.
* '''Ineffizientes Hinzufügen, wenn internes Array voll''' - Laufzeit beim Hinzufügen von Elementen bei vollem Array langsam, ein neues Array muss erstellt werden und alle Elemente

==== Code beispiel ====
<syntaxhighlight lang='Java' line="'line'>
List<Integer> myArrayList = new ArrayList<>();
myArrayList.add(1);
myArrayList.add(1);
myArrayList.add(1);
myArrayList.remove(0);
System.out.println("Element an der Stelle 2: "+myArrayList.get(1));
</syntaxhighlight>
* Zeile 1) Die die ArrayListe wird erzeugt und einer Variable des Typs List zugewiesen. Warum ist das möglich? Weil ArrayList das Interface List implementiert. D.h.: Eine ArrayList ist eine List.
* Zeile 2) - 4) fügen dem Array einen int hinzu. Hier ist zu beachten, der primitive Datentyp '''int''' wird automatisch in die Klasse '''Integer''' umgewandelt. Dieser mechanismus nennt sich Autoboxing.
* Zeile 5) Das Element an der Stelle 0 wird aus der ArrayList entfernt
* Zeile 6) Ausgabe des Elements an der Stelle 2 (Index 1)

=== Einsatzgebiete ===
Die Einsatzgebiete überschneiden sich mit herkömmlichen Arrays. Benötigt man mehr flexibilität und soll '''nicht''' mit primitiven Datentypen gearbeitet werden, so kann anstatt eines Arrays die ArrayListe verwendet werden. Ist die Anzahl der Elemente start fluktuierend (oftmaliges löschen/einfügen/hinzufügen), so sollte man aus oben genannten Gründen auf eine andere Datenstruktur ausweichen.

=== LinkedList oder verkettete Liste ===
Die verkettete Liste ist eine sehr dynamische Datenstruktur. Ihre Größe ist flexibel. Die Daten werden in Knoten gehalten, welche im Falle der einfach verketteten Liste auf den Nachfolger und bei der doppelt verketteten Liste zusätzlich auf den Vorgänger Knoten zeigen. Elemente können einfach an bestimmten Stellen eingefügt oder gelöscht werden, es müssen lediglich die Nachfolger bzw. Vorgänger aktualisiert werden.
[[Datei:Singly linked list and doubly linked list in Java.jpg|mini|none|Einfach und doppelt verkettete Liste. Quelle: https://www.java67.com/2016/01/how-to-implement-singly-linked-list-in-java-using-generics-example.html]]

==== Vorteile ====
* '''Einfügen und Löschen effizient''' - Es müssen lediglich die Zeiger auf den Vorgänger/Nachfolger geändert werden.
* '''Speicherbedarf flexibel''' - Der Speicherbedarf wächst und schrumpft mit der Anzahl der Elemente.

==== Nachteile ====
* '''Zufälliger Zugriff langsam''' - Werden in der LinkedList Elemente mit ihrem Index angesprochen, so muss zuerst die komplette Liste bis zum entsprechenden Index durchlaufen werden.
* '''Speicheroverhead''' - Da die Daten in Knoten gespeichert werden müssen entsteht automatisch ein Speicheroverhead.

==== Einsatzgebiete ====
* Wenn die größe der Liste stark variiert, d.h. oftmals Elemente eingefügt, gelöscht und hinzugefügt werden und '''kein''' zufälliger Zugriff benötigt wird.

==== Code beispiel ====
''Hinzufügen eines Elements''
<syntaxhighlight lang='Java' line="'line'">
public boolean add(Integer element) {
Node newNode = new Node(element);
if(root == null) {
root = newNode;
} else {
Node current = root;
while(current.next() != null) {
current = current.next();
}
current.setNext(newNode);
}
return true;
}
</syntaxhighlight>

''Holen eines Elements''
<syntaxhighlight lang='Java' line="'line'">
public Integer get(int index) {
Node current = root;
for(int i=0; i<index && current != null; i++) {
current = current.next();
}
if(current == null) {
throw new IndexOutOfBoundsException();
}
}
</syntaxhighlight>

== Assoziatives Array ==
Das '''assoziative Array''' oder auch Map, ist eine Sammlung von '''Key''', '''Value''' Paaren. Sie eignet sich sehr gut dafür, für einen bestimmten Schlüssel einen Wert zu hinterlegen. Die Operationen, einfügen, löschen, abrufen, sind Konstant und weisen im Normalfall ein Laufzeitverhalten von O(1) auf. Die Reihenfolge der Element ist nicht definiert.

= Sortieralgorithmen =
Sortieralgorithmen werden benötigt um Datenstrukturen nach gewissen Kriterien zu sortieren. Dazu müssen die Elemente natürlich vergleichbar sein, d.h. es muss möglich sein herauszufinden ob ein Element "größer" oder "kleiner" als ein anderes ist.

== Eigenschaften ==
Sortieralgorithmen können über mehrere Eigenschaften verfügen.
=== In-Place ===
Das bedeutet der Sortieralgorithmus benötigt "keinen" weiteren Speicherplatz beim sortieren, bzw. wenn der Speicherbedarf konstant ist, und nicht mit der Anzahl der Elemente wächst. Z.b. der Sortieralgorithmus Mergesort, teilt die Daten der bestehenden Liste in Sublisten auf, er ist somit nicht In-Place.
=== Stabil ===
Ein Sortieralgorithmus arbeitet stabil, wenn dieser eine bestehende korrekte Ordnung nicht verändert.

== Bubblesort ==
Bubblesort ist ein vergleichsweise akademischer Algorithmus. Er ist wenig effizient, arbeitet jedoch '''Stabil''' und '''In-Place'''.
[[Datei:Bubble-sort-example-300px.gif|mini|none|Funktionsweise Bubblesort. Quelle: https://de.wikipedia.org/wiki/Bubblesort]]

=== Code ===
Bubblesort in Java
<syntaxhighlight lang='Java' line="'line'">
public class Bubblesort {
public static void sort(int[] arr) {
int operations = 0;
int n = arr.length;
boolean swapped = false;
do {
swapped = false;
for (int i = 0; i < n - 1; i++) {
operations++;
if (arr[i] > arr[i + 1]) {
int tmp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = tmp;
swapped = true;
}
}
// Letztes Element ist an der richtigen stelle, n um 1 reduzieren
n = n - 1;
} while (swapped);
System.out.println("Operations: " + operations);
}

public static void main(String[] args) {
int[] arr = new int[] { 1, 2, 3, 4, 5, 6 };
sort(arr);
arr = new int[] { 6, 5, 4, 3, 2, 1 };
sort(arr);
arr = new int[] { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 };
sort(arr);
}
}

</syntaxhighlight>

=== Laufzeitanalyse ===
Für die Laufzeitanalyse verwenden wir die maximal mögliche Laufzeit.
Betrachten wir hierfür folgendes Array:
10,8,5,3,2,1
* 1) Durchlauf: Die Zahl 10 wird mit 8,5,3,2 und 1 verglichen und vertauscht.
* 2) Durchlauf: Die Zahl 8 wird mit 5,3,2 und 1 verglichen und vertauscht, '''mit 10 muss nichtmehr verglichen werden'''.
* 3) Durchlauf: Die Zahl 5 wird mit 3,2 und 1 verglichen und vertauscht, '''mit 10, 8 muss nichtmehr verglichen werden'''.
* 4) Durchlauf: Die Zahl 3 wird mit 2 und 1 verglichen und vertauscht, '''mit 10, 8, 5 muss nichtmehr verglichen werden'''.
* 5) Durchlauf: Die Zahl 2 wird mit 1 verglichen und vertauscht, '''mit 10, 8, 5, 3 muss nichtmehr verglichen werden'''.
* Ende, die Zahl 1 muss nichtmehr verglichen werden.

Vergleichen und vertauschen betrachten wir nun als eine Operation.

* 1) Durchlauf -> 5 Operationen
* 2) Durchlauf -> 4 Operationen
* 3) Durchlauf -> 3 Operationen
* 4) Durchlauf -> 2 Operationen
* 5) Durchlauf -> 1 Operation

Das sind für ein Array der Länge 6, 15 Operationen.

==== Die allgemeine Formel lautet ====
* 1) (n-1) + (n-2) + ... 1
* 2) ''Das ist ja der kleine Gauß minus n:'' (n * (n + 1))/2 - n
* 3) (n2 + n - 2*n)/2
* 4) (n2 - n)/2
* 5) 1/2*(n2 - n)
* 6) n2 - n -> Konstante Werte werden bei der O - Notation entfernt
* 7) n2 -> n ist zu n2 vernachlässigbar und wird entfernt

==== Laufzeit ====
'''Somit ist die Laufzeit von Bubblesort O(n2)'''
==== Laufzeit Bestcase ====
Liegt bereits eine sortierte Liste vor, so benötigt Bubblesort nur einen Durchlauf. Dabei erfolgen '''n - 1''' vergleiche. Die Konstante wird entfernt.
 
'''Die Laufzeit im Bestcase ist O(n)'''

Algorithmen und Datenstrukturen

2021-01-06T08:57:45Z

192.168.96.1: /* Beispiel */

Im folgenden Themenbereich geht es um Algorithmen und Datenstrukturen und um die Landau Symbole oder O - Notation und wie diese im Kontext von Algorithmen und Datenstrukturen verwendet wird.
 
Bei den Alghorithmen werden wir uns auf Sortieralgorithmen beschränken, uns mit deren Laufzeitanalyse (O - Notation) befassen
 
Bei den Datenstrukturen beschränken wir uns auf Arrays, Listen und Bäume und ebenfalls um deren Laufzeitanalyse für verschiedene Operationen

__TOC__

= Landau Symbole oder O - Notation =

'''Landau-Symbole''' (auch '''O-Notation''') werden in der Mathematik und in der Informatik verwendet, um das asymptotische Verhalten von Funktionen und Folgen zu beschreiben. In der Informatik werden sie bei der Analyse von Algorithmen verwendet und geben ein Maß für die Anzahl der Elementarschritte oder der Speichereinheiten in Abhängigkeit von der Größe des gegebenen Problems an. (siehe [[https://de.wikipedia.org/wiki/Landau-Symbole]]).
 
Unter asymptotischem Verhalten verstehen wir hier das Grenzverhalten eines Algorithmus, vereinfacht gesagt, wie kann sich die Laufzeit im schlechtesten Fall entwickeln. Um das Grenzverhalten eines Algorithmus zu betrachten, analysieren wir wieviele Operationen im schlechtesten Fall im bezug auf die größe des Problems (z.B.: Anzahl der Elemente) benötigt werden. Konstante Werte können dabei vernachlässigt werden.

== Beispiel ==
Suchen des kleinsten und größten Elements in einem Array.
{| class="wikitable"
|-
| 1 || 2 || 3 || 4 || 5 || 6
|}
Um das größte Element zu finden, werden 5 Schritte benötigt, dies entspricht der Länge des Arrays - 1. Für die Suche des größten Elements benötigen wir ebenfalls 5 Schritte. Somit ist die Laufzeit für unseren Algorithmus '''2 * (n - 1)''', die Konstanten werden entfernt: '''O(n)'''
<syntaxhighlight lang='java' line="'line'">
public void findMinAndMax(int[] arr) {
int min = arr[0];
int max = arr[0];
for(int i=1; i<arr.length; i++) {
min = Math.min(min, arr[i]);
}
for(int i=1; i<arr.length; i++) {
max = Math.max(max, arr[i]);
}
System.out.println("Min: "+min);
System.out.println("Max: "+max);
}
</syntaxhighlight>
 
In der O - Notation werden einige gebräuchliche Schranken verwendet, wenn wir einen Algorithmus oder eine Datenstruktur analysieren, verwenden wir diese Schranken und nicht die exakte Mathematische repräsentation des Problems (siehe [[Algorithmen_und_Datenstrukturen#Bubblesort|Bubblesort]])

{| class="wikitable"
|+ Gebräuchliche Beschränkungen (es gibt viele weitere!)
|-
! O - Notation !! Bedeutung !! Beispiel
|-
| O(1) || Das Laufzeitverhalten hängt nicht von der Anzahl der Elemente ab und ist konstant || Element an der Stelle N aus einem Array oder einer ArrayListe holen
|-
| O(n) || Das Laufzeitverhalten verlängert sich linear mit der Anzahl der Element || Suchen eines bestimmten Elements in einem unsortierten Array
|-
| O(n log n) || Super lineares Wachstum :-DDD || Mergesort, Heapsort, durchschnittsfall Quicksort
|-
| O(n2) || Quadratisches Wachstum, die Laufzeit wächst quadratisch zur Anzahl der Elemente || Bubblesort
|-
| O(log2n) || 2er Logarithmisches Wachstum || Suche im Binärbaum
|}

= Datenstrukturen =

In der Informatik und Softwaretechnik ist eine Datenstruktur ein Objekt, welches zur Speicherung und Organisation von Daten dient. Es handelt sich um eine Struktur, weil die Daten in einer bestimmten Art und Weise angeordnet und verknüpft werden, um den Zugriff auf sie und ihre Verwaltung effizient zu ermöglichen. (siehe [[https://de.wikipedia.org/wiki/Datenstruktur]])
 
Im folgenden sollen einige Datenstrukturen erläutert werden, für jede Datenstruktur gibt es andere Einsatzgebiete die für deren Eigenschaften optimal sind.

== Array ==
Ein Array oder Feld ist eine sehr effiziente doch wenig dynamische Datenstruktur. In nahezu allen Programmiersprachen findet sich diese Datenstruktur wieder. Weiter ist auch ein dynamisches vergrößern oder verkleinern in einigen Programmiersprachen automatisch implementiert ('''Javascript''').
 
Gehen wir jedoch von Programmiersprachen wie '''Java''' oder '''C''' aus, so hat ein Array immer eine fixe größe. Das heißt, zur Laufzeit (nach dem das Programm compiliert und gestartet wurde) kann diese nicht verändert werden.
=== Vorteile ===
* '''Der Speicheroverhead ist sehr gering''' - Es wird nur der Speicher reserviert, der für die Anzahl der Elemente benötigt wird.
* '''Geringe Zugriffszeit''' - Wird ein Element an einer stelle angesprochen, so kann für den Zugriff die Exakte Speicheradresse berechnet werden.

=== Nachteile ===
* '''Wenig flexibel''' - Wie bereits erwähnt, muss die größe meist fix definiert werden. Eine vergrößerung/verkleinerung ist nicht möglich, ermöglicht die Programmiersprache dies, so hat dies meist zurfolge, dass das Array neu erstellt wird, und die Elemente kopiert werden müssen.

=== Einsatzgebiete ===
Überall dort, wo eine fixe Speichergröße benötigt und effizient wichtig ist, dort sollte die Verwendung von Arrays in betracht gezogen werden.
* '''Bildmanipulation''' - Wird ein Bild zur Bearbeitung geladen, so kann die ''Bitmap'' in einem Array gespeichert werden. jedes Element im Array entspricht dann einem Pixel.
* '''Puffern von Daten''' - Beim Lesen und Schreiben werden Daten meist in einem Array zwischengespeichert (gepuffert). Danach kann die Bearbeitung erfolgen. Weiters kann bei jedem Lese oder Schreibvorgang erneut das selbe Array verwendet werden, was die Effizienz weiter erhöht.
* '''Jegliches Schachbrettartige Problem mit fixer Größe''' - Schiffe versenken, Schach,...

== Liste ==
Die Liste ist eine sehr gebräuchliche Datenstruktur. Sie ist gekennzeichnet durch, je nach implementierung, gute Zugriffszeiten oder erhöhte Flexibilität.
 
Beziehen wir uns auf die Programmiersprache Java, so ist die Liste ein '''Interface''', das heißt eine Schnittstelle. Diese Schnittstelle definiert einige '''Methoden''' die eine Implementierung erfüllen muss. Einige davon wären:
* <syntaxhighlight lang="java" inline>E get(int index)</syntaxhighlight> - Gibt das Element an der Stelle '''index''' aus
* <syntaxhighlight lang="java" inline>E remove(int index)</syntaxhighlight> - Gibt das Element an der Stelle '''index''' aus
* <syntaxhighlight lang="java" inline>boolean add(E element)</syntaxhighlight> - Fügt ein Element an das Ende der Liste an
* <syntaxhighlight lang="java" inline>boolean add(int index, E element)</syntaxhighlight> - Fügt ein Element an einer bestimmten Position ein, und schiebt nachfolgende Elemente nach rechts (Index wird erhöht)
* ...
Hier ist nun ersichtlich, dass die Flexibilität der Liste ein essenzieller Bestandteil der Definition ist.
 
Anbei einige Implementierungen des Interfaces List.
=== ArrayList ===
Die ArrayList vereint die Eigenschaften einer Liste und eines Arrays. Die interne Implementierung verwendet ein Array von fixer größe um Elemente zu speichern. Wird diese fixe größe überschritten, so wird intern ein neues Array angelegt, je nach implementierung mit einem gewissen Vergrößerungsfaktor. Nach dem neuanlegen des internen Arrays, werden alle Elemente kopiert und in das neue Array eingefügt. Werden Elemente gelöscht, so müssen die Elemente nach dem gelöschten Element um eins nach links verschoben werden.
[[Datei:Removing Element from ArrayList diagram.png|mini|none|400px|Element wird aus ArrayListe entfernt. Quelle: https://beginnersbook.com/2013/12/java-arraylist/]]
In Java wird die größe des internen Arrays nicht automatisch reduziert, wenn Elemente gelöscht werden. Dafür gibt es die Methode <syntaxhighlight lang="java" inline>myArrayList.trim()</syntaxhighlight>

==== Vorteile ====
* '''Relativ geringer Speicheroverhead''' - Dies verhält sich ähnlich wie beim Array. Jedoch können in der ArrayList keine primitiven Datentypen gespeichert werden. Dies bedeutet, es wird nur ein Array von Referenzen erstellt. In jedem Platz findet sich eine Referenz auf das wirkliche Objekt. Dies bedeutet in Bezug auf primitive Datentypen einen weit höheren Speicherbedarf als bei einem Array.
* '''Geringe Zugriffszeit''' - Wird ein Element an einer stelle angesprochen, so kann für den Zugriff die Exakte Speicheradresse berechnet werden.

==== Nachteile ====
* '''Ineffizientes Löschen''' - Laufzeit beim Löschen nicht optimal, Elemente müssen verschoben werden.
* '''Ineffizientes Einfügen''' - Laufzeit beim Einfügen von Elementen an einer gewissen Stelle langsam, wie beim löschen müssen alle Nachfolgenden Elemente verschoben werden.
* '''Ineffizientes Hinzufügen, wenn internes Array voll''' - Laufzeit beim Hinzufügen von Elementen bei vollem Array langsam, ein neues Array muss erstellt werden und alle Elemente

==== Code beispiel ====
<syntaxhighlight lang='Java' line="'line'>
List<Integer> myArrayList = new ArrayList<>();
myArrayList.add(1);
myArrayList.add(1);
myArrayList.add(1);
myArrayList.remove(0);
System.out.println("Element an der Stelle 2: "+myArrayList.get(1));
</syntaxhighlight>
* Zeile 1) Die die ArrayListe wird erzeugt und einer Variable des Typs List zugewiesen. Warum ist das möglich? Weil ArrayList das Interface List implementiert. D.h.: Eine ArrayList ist eine List.
* Zeile 2) - 4) fügen dem Array einen int hinzu. Hier ist zu beachten, der primitive Datentyp '''int''' wird automatisch in die Klasse '''Integer''' umgewandelt. Dieser mechanismus nennt sich Autoboxing.
* Zeile 5) Das Element an der Stelle 0 wird aus der ArrayList entfernt
* Zeile 6) Ausgabe des Elements an der Stelle 2 (Index 1)

=== Einsatzgebiete ===
Die Einsatzgebiete überschneiden sich mit herkömmlichen Arrays. Benötigt man mehr flexibilität und soll '''nicht''' mit primitiven Datentypen gearbeitet werden, so kann anstatt eines Arrays die ArrayListe verwendet werden. Ist die Anzahl der Elemente start fluktuierend (oftmaliges löschen/einfügen/hinzufügen), so sollte man aus oben genannten Gründen auf eine andere Datenstruktur ausweichen.

=== LinkedList oder verkettete Liste ===
Die verkettete Liste ist eine sehr dynamische Datenstruktur. Ihre Größe ist flexibel. Die Daten werden in Knoten gehalten, welche im Falle der einfach verketteten Liste auf den Nachfolger und bei der doppelt verketteten Liste zusätzlich auf den Vorgänger Knoten zeigen. Elemente können einfach an bestimmten Stellen eingefügt oder gelöscht werden, es müssen lediglich die Nachfolger bzw. Vorgänger aktualisiert werden.
[[Datei:Singly linked list and doubly linked list in Java.jpg|mini|none|Einfach und doppelt verkettete Liste. Quelle: https://www.java67.com/2016/01/how-to-implement-singly-linked-list-in-java-using-generics-example.html]]

==== Vorteile ====
* '''Einfügen und Löschen effizient''' - Es müssen lediglich die Zeiger auf den Vorgänger/Nachfolger geändert werden.
* '''Speicherbedarf flexibel''' - Der Speicherbedarf wächst und schrumpft mit der Anzahl der Elemente.

==== Nachteile ====
* '''Zufälliger Zugriff langsam''' - Werden in der LinkedList Elemente mit ihrem Index angesprochen, so muss zuerst die komplette Liste bis zum entsprechenden Index durchlaufen werden.
* '''Speicheroverhead''' - Da die Daten in Knoten gespeichert werden müssen entsteht automatisch ein Speicheroverhead.

==== Einsatzgebiete ====
* Wenn die größe der Liste stark variiert, d.h. oftmals Elemente eingefügt, gelöscht und hinzugefügt werden und '''kein''' zufälliger Zugriff benötigt wird.

==== Code beispiel ====
''Hinzufügen eines Elements''
<syntaxhighlight lang='Java' line="'line'">
public boolean add(Integer element) {
Node newNode = new Node(element);
if(root == null) {
root = newNode;
} else {
Node current = root;
while(current.next() != null) {
current = current.next();
}
current.setNext(newNode);
}
return true;
}
</syntaxhighlight>

''Holen eines Elements''
<syntaxhighlight lang='Java' line="'line'">
public Integer get(int index) {
Node current = root;
for(int i=0; i<index && current != null; i++) {
current = current.next();
}
if(current == null) {
throw new IndexOutOfBoundsException();
}
}
</syntaxhighlight>

== Assoziatives Array ==
Das '''assoziative Array''' oder auch Map, ist eine Sammlung von '''Key''', '''Value''' Paaren. Sie eignet sich sehr gut dafür, für einen bestimmten Schlüssel einen Wert zu hinterlegen. Die Operationen, einfügen, löschen, abrufen, sind Konstant und weisen im Normalfall ein Laufzeitverhalten von O(1) auf. Die Reihenfolge der Element ist nicht definiert.

= Sortieralgorithmen =
Sortieralgorithmen werden benötigt um Datenstrukturen nach gewissen Kriterien zu sortieren. Dazu müssen die Elemente natürlich vergleichbar sein, d.h. es muss möglich sein herauszufinden ob ein Element "größer" oder "kleiner" als ein anderes ist.

== Eigenschaften ==
Sortieralgorithmen können über mehrere Eigenschaften verfügen.
=== In-Place ===
Das bedeutet der Sortieralgorithmus benötigt "keinen" weiteren Speicherplatz beim sortieren, bzw. wenn der Speicherbedarf konstant ist, und nicht mit der Anzahl der Elemente wächst. Z.b. der Sortieralgorithmus Mergesort, teilt die Daten der bestehenden Liste in Sublisten auf, er ist somit nicht In-Place.
=== Stabil ===
Ein Sortieralgorithmus arbeitet stabil, wenn dieser eine bestehende korrekte Ordnung nicht verändert.

== Bubblesort ==
Bubblesort ist ein vergleichsweise akademischer Algorithmus. Er ist wenig effizient, arbeitet jedoch '''Stabil''' und '''In-Place'''.
[[Datei:Bubble-sort-example-300px.gif|mini|none|Funktionsweise Bubblesort. Quelle: https://de.wikipedia.org/wiki/Bubblesort]]

=== Code ===
Bubblesort in Java
<syntaxhighlight lang='Java' line="'line'">
public class Bubblesort {
public static void sort(int[] arr) {
int operations = 0;
int n = arr.length;
boolean swapped = false;
do {
swapped = false;
for (int i = 0; i < n - 1; i++) {
operations++;
if (arr[i] > arr[i + 1]) {
int tmp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = tmp;
swapped = true;
}
}
// Letztes Element ist an der richtigen stelle, n um 1 reduzieren
n = n - 1;
} while (swapped);
System.out.println("Operations: " + operations);
}

public static void main(String[] args) {
int[] arr = new int[] { 1, 2, 3, 4, 5, 6 };
sort(arr);
arr = new int[] { 6, 5, 4, 3, 2, 1 };
sort(arr);
arr = new int[] { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 };
sort(arr);
}
}

</syntaxhighlight>

=== Laufzeitanalyse ===
Für die Laufzeitanalyse verwenden wir die maximal mögliche Laufzeit.
Betrachten wir hierfür folgendes Array:
10,8,5,3,2,1
* 1) Durchlauf: Die Zahl 10 wird mit 8,5,3,2 und 1 verglichen und vertauscht.
* 2) Durchlauf: Die Zahl 8 wird mit 5,3,2 und 1 verglichen und vertauscht, '''mit 10 muss nichtmehr verglichen werden'''.
* 3) Durchlauf: Die Zahl 5 wird mit 3,2 und 1 verglichen und vertauscht, '''mit 10, 8 muss nichtmehr verglichen werden'''.
* 4) Durchlauf: Die Zahl 3 wird mit 2 und 1 verglichen und vertauscht, '''mit 10, 8, 5 muss nichtmehr verglichen werden'''.
* 5) Durchlauf: Die Zahl 2 wird mit 1 verglichen und vertauscht, '''mit 10, 8, 5, 3 muss nichtmehr verglichen werden'''.
* Ende, die Zahl 1 muss nichtmehr verglichen werden.

Vergleichen und vertauschen betrachten wir nun als eine Operation.

* 1) Durchlauf -> 5 Operationen
* 2) Durchlauf -> 4 Operationen
* 3) Durchlauf -> 3 Operationen
* 4) Durchlauf -> 2 Operationen
* 5) Durchlauf -> 1 Operation

Das sind für ein Array der Länge 6, 15 Operationen.

==== Die allgemeine Formel lautet ====
* 1) (n-1) + (n-2) + ... 1
* 2) ''Das ist ja der kleine Gauß minus n:'' (n * (n + 1))/2 - n
* 3) (n2 + n - 2*n)/2
* 4) (n2 - n)/2
* 5) 1/2*(n2 - n)
* 6) n2 - n -> Konstante Werte werden bei der O - Notation entfernt
* 7) n2 -> n ist zu n2 vernachlässigbar und wird entfernt

==== Laufzeit ====
'''Somit ist die Laufzeit von Bubblesort O(n2)'''
==== Laufzeit Bestcase ====
Liegt bereits eine sortierte Liste vor, so benötigt Bubblesort nur einen Durchlauf. Dabei erfolgen '''n - 1''' vergleiche. Die Konstante wird entfernt.
 
'''Die Laufzeit im Bestcase ist O(n)'''

Algorithmen und Datenstrukturen

2021-01-06T08:52:25Z

192.168.96.1: /* Landau Symbole oder O - Notation */

Im folgenden Themenbereich geht es um Algorithmen und Datenstrukturen und um die Landau Symbole oder O - Notation und wie diese im Kontext von Algorithmen und Datenstrukturen verwendet wird.
 
Bei den Alghorithmen werden wir uns auf Sortieralgorithmen beschränken, uns mit deren Laufzeitanalyse (O - Notation) befassen
 
Bei den Datenstrukturen beschränken wir uns auf Arrays, Listen und Bäume und ebenfalls um deren Laufzeitanalyse für verschiedene Operationen

__TOC__

= Landau Symbole oder O - Notation =

'''Landau-Symbole''' (auch '''O-Notation''') werden in der Mathematik und in der Informatik verwendet, um das asymptotische Verhalten von Funktionen und Folgen zu beschreiben. In der Informatik werden sie bei der Analyse von Algorithmen verwendet und geben ein Maß für die Anzahl der Elementarschritte oder der Speichereinheiten in Abhängigkeit von der Größe des gegebenen Problems an. (siehe [[https://de.wikipedia.org/wiki/Landau-Symbole]]).
 
Unter asymptotischem Verhalten verstehen wir hier das Grenzverhalten eines Algorithmus, vereinfacht gesagt, wie kann sich die Laufzeit im schlechtesten Fall entwickeln. Um das Grenzverhalten eines Algorithmus zu betrachten, analysieren wir wieviele Operationen im schlechtesten Fall im bezug auf die größe des Problems (z.B.: Anzahl der Elemente) benötigt werden. Konstante Werte können dabei vernachlässigt werden.

== Beispiel ==
Suchen des kleinsten und größten Elements in einem Array.
{| class="wikitable"
|+ Text der Überschrift
|-
| 1
|-
| 2
|-
| 3
|-
| 4
|-
| 5
|-
| 6
|}
Um das größte Element zu finden, werden 5 Schritte benötigt, dies entspricht der Länge des Arrays - 1. Für die Suche des größten Elements benötigen wir ebenfalls 5 Schritte. Somit ist die Laufzeit für unseren Algorithmus '''2 * (n - 1)''', die Konstanten werden entfernt: '''O(n)'''
 
In der O - Notation werden einige gebräuchliche Schranken verwendet, wenn wir einen Algorithmus oder eine Datenstruktur analysieren, verwenden wir diese Schranken und nicht die exakte Mathematische repräsentation des Problems (siehe [[Algorithmen_und_Datenstrukturen#Bubblesort|Bubblesort]])

{| class="wikitable"
|+ Gebräuchliche Beschränkungen (es gibt viele weitere!)
|-
! O - Notation !! Bedeutung !! Beispiel
|-
| O(1) || Das Laufzeitverhalten hängt nicht von der Anzahl der Elemente ab und ist konstant || Element an der Stelle N aus einem Array oder einer ArrayListe holen
|-
| O(n) || Das Laufzeitverhalten verlängert sich linear mit der Anzahl der Element || Suchen eines bestimmten Elements in einem unsortierten Array
|-
| O(n log n) || Super lineares Wachstum :-DDD || Mergesort, Heapsort, durchschnittsfall Quicksort
|-
| O(n2) || Quadratisches Wachstum, die Laufzeit wächst quadratisch zur Anzahl der Elemente || Bubblesort
|-
| O(log2n) || 2er Logarithmisches Wachstum || Suche im Binärbaum
|}

= Datenstrukturen =

In der Informatik und Softwaretechnik ist eine Datenstruktur ein Objekt, welches zur Speicherung und Organisation von Daten dient. Es handelt sich um eine Struktur, weil die Daten in einer bestimmten Art und Weise angeordnet und verknüpft werden, um den Zugriff auf sie und ihre Verwaltung effizient zu ermöglichen. (siehe [[https://de.wikipedia.org/wiki/Datenstruktur]])
 
Im folgenden sollen einige Datenstrukturen erläutert werden, für jede Datenstruktur gibt es andere Einsatzgebiete die für deren Eigenschaften optimal sind.

== Array ==
Ein Array oder Feld ist eine sehr effiziente doch wenig dynamische Datenstruktur. In nahezu allen Programmiersprachen findet sich diese Datenstruktur wieder. Weiter ist auch ein dynamisches vergrößern oder verkleinern in einigen Programmiersprachen automatisch implementiert ('''Javascript''').
 
Gehen wir jedoch von Programmiersprachen wie '''Java''' oder '''C''' aus, so hat ein Array immer eine fixe größe. Das heißt, zur Laufzeit (nach dem das Programm compiliert und gestartet wurde) kann diese nicht verändert werden.
=== Vorteile ===
* '''Der Speicheroverhead ist sehr gering''' - Es wird nur der Speicher reserviert, der für die Anzahl der Elemente benötigt wird.
* '''Geringe Zugriffszeit''' - Wird ein Element an einer stelle angesprochen, so kann für den Zugriff die Exakte Speicheradresse berechnet werden.

=== Nachteile ===
* '''Wenig flexibel''' - Wie bereits erwähnt, muss die größe meist fix definiert werden. Eine vergrößerung/verkleinerung ist nicht möglich, ermöglicht die Programmiersprache dies, so hat dies meist zurfolge, dass das Array neu erstellt wird, und die Elemente kopiert werden müssen.

=== Einsatzgebiete ===
Überall dort, wo eine fixe Speichergröße benötigt und effizient wichtig ist, dort sollte die Verwendung von Arrays in betracht gezogen werden.
* '''Bildmanipulation''' - Wird ein Bild zur Bearbeitung geladen, so kann die ''Bitmap'' in einem Array gespeichert werden. jedes Element im Array entspricht dann einem Pixel.
* '''Puffern von Daten''' - Beim Lesen und Schreiben werden Daten meist in einem Array zwischengespeichert (gepuffert). Danach kann die Bearbeitung erfolgen. Weiters kann bei jedem Lese oder Schreibvorgang erneut das selbe Array verwendet werden, was die Effizienz weiter erhöht.
* '''Jegliches Schachbrettartige Problem mit fixer Größe''' - Schiffe versenken, Schach,...

== Liste ==
Die Liste ist eine sehr gebräuchliche Datenstruktur. Sie ist gekennzeichnet durch, je nach implementierung, gute Zugriffszeiten oder erhöhte Flexibilität.
 
Beziehen wir uns auf die Programmiersprache Java, so ist die Liste ein '''Interface''', das heißt eine Schnittstelle. Diese Schnittstelle definiert einige '''Methoden''' die eine Implementierung erfüllen muss. Einige davon wären:
* <syntaxhighlight lang="java" inline>E get(int index)</syntaxhighlight> - Gibt das Element an der Stelle '''index''' aus
* <syntaxhighlight lang="java" inline>E remove(int index)</syntaxhighlight> - Gibt das Element an der Stelle '''index''' aus
* <syntaxhighlight lang="java" inline>boolean add(E element)</syntaxhighlight> - Fügt ein Element an das Ende der Liste an
* <syntaxhighlight lang="java" inline>boolean add(int index, E element)</syntaxhighlight> - Fügt ein Element an einer bestimmten Position ein, und schiebt nachfolgende Elemente nach rechts (Index wird erhöht)
* ...
Hier ist nun ersichtlich, dass die Flexibilität der Liste ein essenzieller Bestandteil der Definition ist.
 
Anbei einige Implementierungen des Interfaces List.
=== ArrayList ===
Die ArrayList vereint die Eigenschaften einer Liste und eines Arrays. Die interne Implementierung verwendet ein Array von fixer größe um Elemente zu speichern. Wird diese fixe größe überschritten, so wird intern ein neues Array angelegt, je nach implementierung mit einem gewissen Vergrößerungsfaktor. Nach dem neuanlegen des internen Arrays, werden alle Elemente kopiert und in das neue Array eingefügt. Werden Elemente gelöscht, so müssen die Elemente nach dem gelöschten Element um eins nach links verschoben werden.
[[Datei:Removing Element from ArrayList diagram.png|mini|none|400px|Element wird aus ArrayListe entfernt. Quelle: https://beginnersbook.com/2013/12/java-arraylist/]]
In Java wird die größe des internen Arrays nicht automatisch reduziert, wenn Elemente gelöscht werden. Dafür gibt es die Methode <syntaxhighlight lang="java" inline>myArrayList.trim()</syntaxhighlight>

==== Vorteile ====
* '''Relativ geringer Speicheroverhead''' - Dies verhält sich ähnlich wie beim Array. Jedoch können in der ArrayList keine primitiven Datentypen gespeichert werden. Dies bedeutet, es wird nur ein Array von Referenzen erstellt. In jedem Platz findet sich eine Referenz auf das wirkliche Objekt. Dies bedeutet in Bezug auf primitive Datentypen einen weit höheren Speicherbedarf als bei einem Array.
* '''Geringe Zugriffszeit''' - Wird ein Element an einer stelle angesprochen, so kann für den Zugriff die Exakte Speicheradresse berechnet werden.

==== Nachteile ====
* '''Ineffizientes Löschen''' - Laufzeit beim Löschen nicht optimal, Elemente müssen verschoben werden.
* '''Ineffizientes Einfügen''' - Laufzeit beim Einfügen von Elementen an einer gewissen Stelle langsam, wie beim löschen müssen alle Nachfolgenden Elemente verschoben werden.
* '''Ineffizientes Hinzufügen, wenn internes Array voll''' - Laufzeit beim Hinzufügen von Elementen bei vollem Array langsam, ein neues Array muss erstellt werden und alle Elemente

==== Code beispiel ====
<syntaxhighlight lang='Java' line="'line'>
List<Integer> myArrayList = new ArrayList<>();
myArrayList.add(1);
myArrayList.add(1);
myArrayList.add(1);
myArrayList.remove(0);
System.out.println("Element an der Stelle 2: "+myArrayList.get(1));
</syntaxhighlight>
* Zeile 1) Die die ArrayListe wird erzeugt und einer Variable des Typs List zugewiesen. Warum ist das möglich? Weil ArrayList das Interface List implementiert. D.h.: Eine ArrayList ist eine List.
* Zeile 2) - 4) fügen dem Array einen int hinzu. Hier ist zu beachten, der primitive Datentyp '''int''' wird automatisch in die Klasse '''Integer''' umgewandelt. Dieser mechanismus nennt sich Autoboxing.
* Zeile 5) Das Element an der Stelle 0 wird aus der ArrayList entfernt
* Zeile 6) Ausgabe des Elements an der Stelle 2 (Index 1)

=== Einsatzgebiete ===
Die Einsatzgebiete überschneiden sich mit herkömmlichen Arrays. Benötigt man mehr flexibilität und soll '''nicht''' mit primitiven Datentypen gearbeitet werden, so kann anstatt eines Arrays die ArrayListe verwendet werden. Ist die Anzahl der Elemente start fluktuierend (oftmaliges löschen/einfügen/hinzufügen), so sollte man aus oben genannten Gründen auf eine andere Datenstruktur ausweichen.

=== LinkedList oder verkettete Liste ===
Die verkettete Liste ist eine sehr dynamische Datenstruktur. Ihre Größe ist flexibel. Die Daten werden in Knoten gehalten, welche im Falle der einfach verketteten Liste auf den Nachfolger und bei der doppelt verketteten Liste zusätzlich auf den Vorgänger Knoten zeigen. Elemente können einfach an bestimmten Stellen eingefügt oder gelöscht werden, es müssen lediglich die Nachfolger bzw. Vorgänger aktualisiert werden.
[[Datei:Singly linked list and doubly linked list in Java.jpg|mini|none|Einfach und doppelt verkettete Liste. Quelle: https://www.java67.com/2016/01/how-to-implement-singly-linked-list-in-java-using-generics-example.html]]

==== Vorteile ====
* '''Einfügen und Löschen effizient''' - Es müssen lediglich die Zeiger auf den Vorgänger/Nachfolger geändert werden.
* '''Speicherbedarf flexibel''' - Der Speicherbedarf wächst und schrumpft mit der Anzahl der Elemente.

==== Nachteile ====
* '''Zufälliger Zugriff langsam''' - Werden in der LinkedList Elemente mit ihrem Index angesprochen, so muss zuerst die komplette Liste bis zum entsprechenden Index durchlaufen werden.
* '''Speicheroverhead''' - Da die Daten in Knoten gespeichert werden müssen entsteht automatisch ein Speicheroverhead.

==== Einsatzgebiete ====
* Wenn die größe der Liste stark variiert, d.h. oftmals Elemente eingefügt, gelöscht und hinzugefügt werden und '''kein''' zufälliger Zugriff benötigt wird.

==== Code beispiel ====
''Hinzufügen eines Elements''
<syntaxhighlight lang='Java' line="'line'">
public boolean add(Integer element) {
Node newNode = new Node(element);
if(root == null) {
root = newNode;
} else {
Node current = root;
while(current.next() != null) {
current = current.next();
}
current.setNext(newNode);
}
return true;
}
</syntaxhighlight>

''Holen eines Elements''
<syntaxhighlight lang='Java' line="'line'">
public Integer get(int index) {
Node current = root;
for(int i=0; i<index && current != null; i++) {
current = current.next();
}
if(current == null) {
throw new IndexOutOfBoundsException();
}
}
</syntaxhighlight>

== Assoziatives Array ==
Das '''assoziative Array''' oder auch Map, ist eine Sammlung von '''Key''', '''Value''' Paaren. Sie eignet sich sehr gut dafür, für einen bestimmten Schlüssel einen Wert zu hinterlegen. Die Operationen, einfügen, löschen, abrufen, sind Konstant und weisen im Normalfall ein Laufzeitverhalten von O(1) auf. Die Reihenfolge der Element ist nicht definiert.

= Sortieralgorithmen =
Sortieralgorithmen werden benötigt um Datenstrukturen nach gewissen Kriterien zu sortieren. Dazu müssen die Elemente natürlich vergleichbar sein, d.h. es muss möglich sein herauszufinden ob ein Element "größer" oder "kleiner" als ein anderes ist.

== Eigenschaften ==
Sortieralgorithmen können über mehrere Eigenschaften verfügen.
=== In-Place ===
Das bedeutet der Sortieralgorithmus benötigt "keinen" weiteren Speicherplatz beim sortieren, bzw. wenn der Speicherbedarf konstant ist, und nicht mit der Anzahl der Elemente wächst. Z.b. der Sortieralgorithmus Mergesort, teilt die Daten der bestehenden Liste in Sublisten auf, er ist somit nicht In-Place.
=== Stabil ===
Ein Sortieralgorithmus arbeitet stabil, wenn dieser eine bestehende korrekte Ordnung nicht verändert.

== Bubblesort ==
Bubblesort ist ein vergleichsweise akademischer Algorithmus. Er ist wenig effizient, arbeitet jedoch '''Stabil''' und '''In-Place'''.
[[Datei:Bubble-sort-example-300px.gif|mini|none|Funktionsweise Bubblesort. Quelle: https://de.wikipedia.org/wiki/Bubblesort]]

=== Code ===
Bubblesort in Java
<syntaxhighlight lang='Java' line="'line'">
public class Bubblesort {
public static void sort(int[] arr) {
int operations = 0;
int n = arr.length;
boolean swapped = false;
do {
swapped = false;
for (int i = 0; i < n - 1; i++) {
operations++;
if (arr[i] > arr[i + 1]) {
int tmp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = tmp;
swapped = true;
}
}
// Letztes Element ist an der richtigen stelle, n um 1 reduzieren
n = n - 1;
} while (swapped);
System.out.println("Operations: " + operations);
}

public static void main(String[] args) {
int[] arr = new int[] { 1, 2, 3, 4, 5, 6 };
sort(arr);
arr = new int[] { 6, 5, 4, 3, 2, 1 };
sort(arr);
arr = new int[] { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 };
sort(arr);
}
}

</syntaxhighlight>

=== Laufzeitanalyse ===
Für die Laufzeitanalyse verwenden wir die maximal mögliche Laufzeit.
Betrachten wir hierfür folgendes Array:
10,8,5,3,2,1
* 1) Durchlauf: Die Zahl 10 wird mit 8,5,3,2 und 1 verglichen und vertauscht.
* 2) Durchlauf: Die Zahl 8 wird mit 5,3,2 und 1 verglichen und vertauscht, '''mit 10 muss nichtmehr verglichen werden'''.
* 3) Durchlauf: Die Zahl 5 wird mit 3,2 und 1 verglichen und vertauscht, '''mit 10, 8 muss nichtmehr verglichen werden'''.
* 4) Durchlauf: Die Zahl 3 wird mit 2 und 1 verglichen und vertauscht, '''mit 10, 8, 5 muss nichtmehr verglichen werden'''.
* 5) Durchlauf: Die Zahl 2 wird mit 1 verglichen und vertauscht, '''mit 10, 8, 5, 3 muss nichtmehr verglichen werden'''.
* Ende, die Zahl 1 muss nichtmehr verglichen werden.

Vergleichen und vertauschen betrachten wir nun als eine Operation.

* 1) Durchlauf -> 5 Operationen
* 2) Durchlauf -> 4 Operationen
* 3) Durchlauf -> 3 Operationen
* 4) Durchlauf -> 2 Operationen
* 5) Durchlauf -> 1 Operation

Das sind für ein Array der Länge 6, 15 Operationen.

==== Die allgemeine Formel lautet ====
* 1) (n-1) + (n-2) + ... 1
* 2) ''Das ist ja der kleine Gauß minus n:'' (n * (n + 1))/2 - n
* 3) (n2 + n - 2*n)/2
* 4) (n2 - n)/2
* 5) 1/2*(n2 - n)
* 6) n2 - n -> Konstante Werte werden bei der O - Notation entfernt
* 7) n2 -> n ist zu n2 vernachlässigbar und wird entfernt

==== Laufzeit ====
'''Somit ist die Laufzeit von Bubblesort O(n2)'''
==== Laufzeit Bestcase ====
Liegt bereits eine sortierte Liste vor, so benötigt Bubblesort nur einen Durchlauf. Dabei erfolgen '''n - 1''' vergleiche. Die Konstante wird entfernt.
 
'''Die Laufzeit im Bestcase ist O(n)'''

Algorithmen und Datenstrukturen

2021-01-06T08:42:12Z

192.168.96.1: /* Vorteile */

Im folgenden Themenbereich geht es um Algorithmen und Datenstrukturen und um die Landau Symbole oder O - Notation und wie diese im Kontext von Algorithmen und Datenstrukturen verwendet wird.
 
Bei den Alghorithmen werden wir uns auf Sortieralgorithmen beschränken, uns mit deren Laufzeitanalyse (O - Notation) befassen
 
Bei den Datenstrukturen beschränken wir uns auf Arrays, Listen und Bäume und ebenfalls um deren Laufzeitanalyse für verschiedene Operationen

__TOC__

= Landau Symbole oder O - Notation =

'''Landau-Symbole''' (auch '''O-Notation''') werden in der Mathematik und in der Informatik verwendet, um das asymptotische Verhalten von Funktionen und Folgen zu beschreiben. In der Informatik werden sie bei der Analyse von Algorithmen verwendet und geben ein Maß für die Anzahl der Elementarschritte oder der Speichereinheiten in Abhängigkeit von der Größe des gegebenen Problems an. (siehe [[https://de.wikipedia.org/wiki/Landau-Symbole]]).
 
Unter asymptotischem Verhalten verstehen wir hier das Grenzverhalten eines Algorithmus, vereinfacht gesagt, wie kann sich die Laufzeit im schlechtesten Fall entwickeln.
 
In der O - Notation werden einige gebräuchliche Schranken verwendet, wenn wir einen Algorithmus oder eine Datenstruktur analysieren, verwenden wir diese Schranken und nicht die exakte Mathematische repräsentation des Problems (siehe [[Algorithmen_und_Datenstrukturen#Bubblesort|Bubblesort]])

{| class="wikitable"
|+ Gebräuchliche Beschränkungen (es gibt viele weitere!)
|-
! O - Notation !! Bedeutung !! Beispiel
|-
| O(1) || Das Laufzeitverhalten hängt nicht von der Anzahl der Elemente ab und ist konstant || Element an der Stelle N aus einem Array oder einer ArrayListe holen
|-
| O(n) || Das Laufzeitverhalten verlängert sich linear mit der Anzahl der Element || Suchen eines bestimmten Elements in einem unsortierten Array
|-
| O(n log n) || Super lineares Wachstum :-DDD || Mergesort, Heapsort, durchschnittsfall Quicksort
|-
| O(n2) || Quadratisches Wachstum, die Laufzeit wächst quadratisch zur Anzahl der Elemente || Bubblesort
|-
| O(log2n) || 2er Logarithmisches Wachstum || Suche im Binärbaum
|}

= Datenstrukturen =

In der Informatik und Softwaretechnik ist eine Datenstruktur ein Objekt, welches zur Speicherung und Organisation von Daten dient. Es handelt sich um eine Struktur, weil die Daten in einer bestimmten Art und Weise angeordnet und verknüpft werden, um den Zugriff auf sie und ihre Verwaltung effizient zu ermöglichen. (siehe [[https://de.wikipedia.org/wiki/Datenstruktur]])
 
Im folgenden sollen einige Datenstrukturen erläutert werden, für jede Datenstruktur gibt es andere Einsatzgebiete die für deren Eigenschaften optimal sind.

== Array ==
Ein Array oder Feld ist eine sehr effiziente doch wenig dynamische Datenstruktur. In nahezu allen Programmiersprachen findet sich diese Datenstruktur wieder. Weiter ist auch ein dynamisches vergrößern oder verkleinern in einigen Programmiersprachen automatisch implementiert ('''Javascript''').
 
Gehen wir jedoch von Programmiersprachen wie '''Java''' oder '''C''' aus, so hat ein Array immer eine fixe größe. Das heißt, zur Laufzeit (nach dem das Programm compiliert und gestartet wurde) kann diese nicht verändert werden.
=== Vorteile ===
* '''Der Speicheroverhead ist sehr gering''' - Es wird nur der Speicher reserviert, der für die Anzahl der Elemente benötigt wird.
* '''Geringe Zugriffszeit''' - Wird ein Element an einer stelle angesprochen, so kann für den Zugriff die Exakte Speicheradresse berechnet werden.

=== Nachteile ===
* '''Wenig flexibel''' - Wie bereits erwähnt, muss die größe meist fix definiert werden. Eine vergrößerung/verkleinerung ist nicht möglich, ermöglicht die Programmiersprache dies, so hat dies meist zurfolge, dass das Array neu erstellt wird, und die Elemente kopiert werden müssen.

=== Einsatzgebiete ===
Überall dort, wo eine fixe Speichergröße benötigt und effizient wichtig ist, dort sollte die Verwendung von Arrays in betracht gezogen werden.
* '''Bildmanipulation''' - Wird ein Bild zur Bearbeitung geladen, so kann die ''Bitmap'' in einem Array gespeichert werden. jedes Element im Array entspricht dann einem Pixel.
* '''Puffern von Daten''' - Beim Lesen und Schreiben werden Daten meist in einem Array zwischengespeichert (gepuffert). Danach kann die Bearbeitung erfolgen. Weiters kann bei jedem Lese oder Schreibvorgang erneut das selbe Array verwendet werden, was die Effizienz weiter erhöht.
* '''Jegliches Schachbrettartige Problem mit fixer Größe''' - Schiffe versenken, Schach,...

== Liste ==
Die Liste ist eine sehr gebräuchliche Datenstruktur. Sie ist gekennzeichnet durch, je nach implementierung, gute Zugriffszeiten oder erhöhte Flexibilität.
 
Beziehen wir uns auf die Programmiersprache Java, so ist die Liste ein '''Interface''', das heißt eine Schnittstelle. Diese Schnittstelle definiert einige '''Methoden''' die eine Implementierung erfüllen muss. Einige davon wären:
* <syntaxhighlight lang="java" inline>E get(int index)</syntaxhighlight> - Gibt das Element an der Stelle '''index''' aus
* <syntaxhighlight lang="java" inline>E remove(int index)</syntaxhighlight> - Gibt das Element an der Stelle '''index''' aus
* <syntaxhighlight lang="java" inline>boolean add(E element)</syntaxhighlight> - Fügt ein Element an das Ende der Liste an
* <syntaxhighlight lang="java" inline>boolean add(int index, E element)</syntaxhighlight> - Fügt ein Element an einer bestimmten Position ein, und schiebt nachfolgende Elemente nach rechts (Index wird erhöht)
* ...
Hier ist nun ersichtlich, dass die Flexibilität der Liste ein essenzieller Bestandteil der Definition ist.
 
Anbei einige Implementierungen des Interfaces List.
=== ArrayList ===
Die ArrayList vereint die Eigenschaften einer Liste und eines Arrays. Die interne Implementierung verwendet ein Array von fixer größe um Elemente zu speichern. Wird diese fixe größe überschritten, so wird intern ein neues Array angelegt, je nach implementierung mit einem gewissen Vergrößerungsfaktor. Nach dem neuanlegen des internen Arrays, werden alle Elemente kopiert und in das neue Array eingefügt. Werden Elemente gelöscht, so müssen die Elemente nach dem gelöschten Element um eins nach links verschoben werden.
[[Datei:Removing Element from ArrayList diagram.png|mini|none|400px|Element wird aus ArrayListe entfernt. Quelle: https://beginnersbook.com/2013/12/java-arraylist/]]
In Java wird die größe des internen Arrays nicht automatisch reduziert, wenn Elemente gelöscht werden. Dafür gibt es die Methode <syntaxhighlight lang="java" inline>myArrayList.trim()</syntaxhighlight>

==== Vorteile ====
* '''Relativ geringer Speicheroverhead''' - Dies verhält sich ähnlich wie beim Array. Jedoch können in der ArrayList keine primitiven Datentypen gespeichert werden. Dies bedeutet, es wird nur ein Array von Referenzen erstellt. In jedem Platz findet sich eine Referenz auf das wirkliche Objekt. Dies bedeutet in Bezug auf primitive Datentypen einen weit höheren Speicherbedarf als bei einem Array.
* '''Geringe Zugriffszeit''' - Wird ein Element an einer stelle angesprochen, so kann für den Zugriff die Exakte Speicheradresse berechnet werden.

==== Nachteile ====
* '''Ineffizientes Löschen''' - Laufzeit beim Löschen nicht optimal, Elemente müssen verschoben werden.
* '''Ineffizientes Einfügen''' - Laufzeit beim Einfügen von Elementen an einer gewissen Stelle langsam, wie beim löschen müssen alle Nachfolgenden Elemente verschoben werden.
* '''Ineffizientes Hinzufügen, wenn internes Array voll''' - Laufzeit beim Hinzufügen von Elementen bei vollem Array langsam, ein neues Array muss erstellt werden und alle Elemente

==== Code beispiel ====
<syntaxhighlight lang='Java' line="'line'>
List<Integer> myArrayList = new ArrayList<>();
myArrayList.add(1);
myArrayList.add(1);
myArrayList.add(1);
myArrayList.remove(0);
System.out.println("Element an der Stelle 2: "+myArrayList.get(1));
</syntaxhighlight>
* Zeile 1) Die die ArrayListe wird erzeugt und einer Variable des Typs List zugewiesen. Warum ist das möglich? Weil ArrayList das Interface List implementiert. D.h.: Eine ArrayList ist eine List.
* Zeile 2) - 4) fügen dem Array einen int hinzu. Hier ist zu beachten, der primitive Datentyp '''int''' wird automatisch in die Klasse '''Integer''' umgewandelt. Dieser mechanismus nennt sich Autoboxing.
* Zeile 5) Das Element an der Stelle 0 wird aus der ArrayList entfernt
* Zeile 6) Ausgabe des Elements an der Stelle 2 (Index 1)

=== Einsatzgebiete ===
Die Einsatzgebiete überschneiden sich mit herkömmlichen Arrays. Benötigt man mehr flexibilität und soll '''nicht''' mit primitiven Datentypen gearbeitet werden, so kann anstatt eines Arrays die ArrayListe verwendet werden. Ist die Anzahl der Elemente start fluktuierend (oftmaliges löschen/einfügen/hinzufügen), so sollte man aus oben genannten Gründen auf eine andere Datenstruktur ausweichen.

=== LinkedList oder verkettete Liste ===
Die verkettete Liste ist eine sehr dynamische Datenstruktur. Ihre Größe ist flexibel. Die Daten werden in Knoten gehalten, welche im Falle der einfach verketteten Liste auf den Nachfolger und bei der doppelt verketteten Liste zusätzlich auf den Vorgänger Knoten zeigen. Elemente können einfach an bestimmten Stellen eingefügt oder gelöscht werden, es müssen lediglich die Nachfolger bzw. Vorgänger aktualisiert werden.
[[Datei:Singly linked list and doubly linked list in Java.jpg|mini|none|Einfach und doppelt verkettete Liste. Quelle: https://www.java67.com/2016/01/how-to-implement-singly-linked-list-in-java-using-generics-example.html]]

==== Vorteile ====
* '''Einfügen und Löschen effizient''' - Es müssen lediglich die Zeiger auf den Vorgänger/Nachfolger geändert werden.
* '''Speicherbedarf flexibel''' - Der Speicherbedarf wächst und schrumpft mit der Anzahl der Elemente.

==== Nachteile ====
* '''Zufälliger Zugriff langsam''' - Werden in der LinkedList Elemente mit ihrem Index angesprochen, so muss zuerst die komplette Liste bis zum entsprechenden Index durchlaufen werden.
* '''Speicheroverhead''' - Da die Daten in Knoten gespeichert werden müssen entsteht automatisch ein Speicheroverhead.

==== Einsatzgebiete ====
* Wenn die größe der Liste stark variiert, d.h. oftmals Elemente eingefügt, gelöscht und hinzugefügt werden und '''kein''' zufälliger Zugriff benötigt wird.

==== Code beispiel ====
''Hinzufügen eines Elements''
<syntaxhighlight lang='Java' line="'line'">
public boolean add(Integer element) {
Node newNode = new Node(element);
if(root == null) {
root = newNode;
} else {
Node current = root;
while(current.next() != null) {
current = current.next();
}
current.setNext(newNode);
}
return true;
}
</syntaxhighlight>

''Holen eines Elements''
<syntaxhighlight lang='Java' line="'line'">
public Integer get(int index) {
Node current = root;
for(int i=0; i<index && current != null; i++) {
current = current.next();
}
if(current == null) {
throw new IndexOutOfBoundsException();
}
}
</syntaxhighlight>

== Assoziatives Array ==
Das '''assoziative Array''' oder auch Map, ist eine Sammlung von '''Key''', '''Value''' Paaren. Sie eignet sich sehr gut dafür, für einen bestimmten Schlüssel einen Wert zu hinterlegen. Die Operationen, einfügen, löschen, abrufen, sind Konstant und weisen im Normalfall ein Laufzeitverhalten von O(1) auf. Die Reihenfolge der Element ist nicht definiert.

= Sortieralgorithmen =
Sortieralgorithmen werden benötigt um Datenstrukturen nach gewissen Kriterien zu sortieren. Dazu müssen die Elemente natürlich vergleichbar sein, d.h. es muss möglich sein herauszufinden ob ein Element "größer" oder "kleiner" als ein anderes ist.

== Eigenschaften ==
Sortieralgorithmen können über mehrere Eigenschaften verfügen.
=== In-Place ===
Das bedeutet der Sortieralgorithmus benötigt "keinen" weiteren Speicherplatz beim sortieren, bzw. wenn der Speicherbedarf konstant ist, und nicht mit der Anzahl der Elemente wächst. Z.b. der Sortieralgorithmus Mergesort, teilt die Daten der bestehenden Liste in Sublisten auf, er ist somit nicht In-Place.
=== Stabil ===
Ein Sortieralgorithmus arbeitet stabil, wenn dieser eine bestehende korrekte Ordnung nicht verändert.

== Bubblesort ==
Bubblesort ist ein vergleichsweise akademischer Algorithmus. Er ist wenig effizient, arbeitet jedoch '''Stabil''' und '''In-Place'''.
[[Datei:Bubble-sort-example-300px.gif|mini|none|Funktionsweise Bubblesort. Quelle: https://de.wikipedia.org/wiki/Bubblesort]]

=== Code ===
Bubblesort in Java
<syntaxhighlight lang='Java' line="'line'">
public class Bubblesort {
public static void sort(int[] arr) {
int operations = 0;
int n = arr.length;
boolean swapped = false;
do {
swapped = false;
for (int i = 0; i < n - 1; i++) {
operations++;
if (arr[i] > arr[i + 1]) {
int tmp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = tmp;
swapped = true;
}
}
// Letztes Element ist an der richtigen stelle, n um 1 reduzieren
n = n - 1;
} while (swapped);
System.out.println("Operations: " + operations);
}

public static void main(String[] args) {
int[] arr = new int[] { 1, 2, 3, 4, 5, 6 };
sort(arr);
arr = new int[] { 6, 5, 4, 3, 2, 1 };
sort(arr);
arr = new int[] { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 };
sort(arr);
}
}

</syntaxhighlight>

=== Laufzeitanalyse ===
Für die Laufzeitanalyse verwenden wir die maximal mögliche Laufzeit.
Betrachten wir hierfür folgendes Array:
10,8,5,3,2,1
* 1) Durchlauf: Die Zahl 10 wird mit 8,5,3,2 und 1 verglichen und vertauscht.
* 2) Durchlauf: Die Zahl 8 wird mit 5,3,2 und 1 verglichen und vertauscht, '''mit 10 muss nichtmehr verglichen werden'''.
* 3) Durchlauf: Die Zahl 5 wird mit 3,2 und 1 verglichen und vertauscht, '''mit 10, 8 muss nichtmehr verglichen werden'''.
* 4) Durchlauf: Die Zahl 3 wird mit 2 und 1 verglichen und vertauscht, '''mit 10, 8, 5 muss nichtmehr verglichen werden'''.
* 5) Durchlauf: Die Zahl 2 wird mit 1 verglichen und vertauscht, '''mit 10, 8, 5, 3 muss nichtmehr verglichen werden'''.
* Ende, die Zahl 1 muss nichtmehr verglichen werden.

Vergleichen und vertauschen betrachten wir nun als eine Operation.

* 1) Durchlauf -> 5 Operationen
* 2) Durchlauf -> 4 Operationen
* 3) Durchlauf -> 3 Operationen
* 4) Durchlauf -> 2 Operationen
* 5) Durchlauf -> 1 Operation

Das sind für ein Array der Länge 6, 15 Operationen.

==== Die allgemeine Formel lautet ====
* 1) (n-1) + (n-2) + ... 1
* 2) ''Das ist ja der kleine Gauß minus n:'' (n * (n + 1))/2 - n
* 3) (n2 + n - 2*n)/2
* 4) (n2 - n)/2
* 5) 1/2*(n2 - n)
* 6) n2 - n -> Konstante Werte werden bei der O - Notation entfernt
* 7) n2 -> n ist zu n2 vernachlässigbar und wird entfernt

==== Laufzeit ====
'''Somit ist die Laufzeit von Bubblesort O(n2)'''
==== Laufzeit Bestcase ====
Liegt bereits eine sortierte Liste vor, so benötigt Bubblesort nur einen Durchlauf. Dabei erfolgen '''n - 1''' vergleiche. Die Konstante wird entfernt.
 
'''Die Laufzeit im Bestcase ist O(n)'''

Algorithmen und Datenstrukturen

2021-01-06T08:41:29Z

192.168.96.1: /* Nachteile */

Im folgenden Themenbereich geht es um Algorithmen und Datenstrukturen und um die Landau Symbole oder O - Notation und wie diese im Kontext von Algorithmen und Datenstrukturen verwendet wird.
 
Bei den Alghorithmen werden wir uns auf Sortieralgorithmen beschränken, uns mit deren Laufzeitanalyse (O - Notation) befassen
 
Bei den Datenstrukturen beschränken wir uns auf Arrays, Listen und Bäume und ebenfalls um deren Laufzeitanalyse für verschiedene Operationen

__TOC__

= Landau Symbole oder O - Notation =

'''Landau-Symbole''' (auch '''O-Notation''') werden in der Mathematik und in der Informatik verwendet, um das asymptotische Verhalten von Funktionen und Folgen zu beschreiben. In der Informatik werden sie bei der Analyse von Algorithmen verwendet und geben ein Maß für die Anzahl der Elementarschritte oder der Speichereinheiten in Abhängigkeit von der Größe des gegebenen Problems an. (siehe [[https://de.wikipedia.org/wiki/Landau-Symbole]]).
 
Unter asymptotischem Verhalten verstehen wir hier das Grenzverhalten eines Algorithmus, vereinfacht gesagt, wie kann sich die Laufzeit im schlechtesten Fall entwickeln.
 
In der O - Notation werden einige gebräuchliche Schranken verwendet, wenn wir einen Algorithmus oder eine Datenstruktur analysieren, verwenden wir diese Schranken und nicht die exakte Mathematische repräsentation des Problems (siehe [[Algorithmen_und_Datenstrukturen#Bubblesort|Bubblesort]])

{| class="wikitable"
|+ Gebräuchliche Beschränkungen (es gibt viele weitere!)
|-
! O - Notation !! Bedeutung !! Beispiel
|-
| O(1) || Das Laufzeitverhalten hängt nicht von der Anzahl der Elemente ab und ist konstant || Element an der Stelle N aus einem Array oder einer ArrayListe holen
|-
| O(n) || Das Laufzeitverhalten verlängert sich linear mit der Anzahl der Element || Suchen eines bestimmten Elements in einem unsortierten Array
|-
| O(n log n) || Super lineares Wachstum :-DDD || Mergesort, Heapsort, durchschnittsfall Quicksort
|-
| O(n2) || Quadratisches Wachstum, die Laufzeit wächst quadratisch zur Anzahl der Elemente || Bubblesort
|-
| O(log2n) || 2er Logarithmisches Wachstum || Suche im Binärbaum
|}

= Datenstrukturen =

In der Informatik und Softwaretechnik ist eine Datenstruktur ein Objekt, welches zur Speicherung und Organisation von Daten dient. Es handelt sich um eine Struktur, weil die Daten in einer bestimmten Art und Weise angeordnet und verknüpft werden, um den Zugriff auf sie und ihre Verwaltung effizient zu ermöglichen. (siehe [[https://de.wikipedia.org/wiki/Datenstruktur]])
 
Im folgenden sollen einige Datenstrukturen erläutert werden, für jede Datenstruktur gibt es andere Einsatzgebiete die für deren Eigenschaften optimal sind.

== Array ==
Ein Array oder Feld ist eine sehr effiziente doch wenig dynamische Datenstruktur. In nahezu allen Programmiersprachen findet sich diese Datenstruktur wieder. Weiter ist auch ein dynamisches vergrößern oder verkleinern in einigen Programmiersprachen automatisch implementiert ('''Javascript''').
 
Gehen wir jedoch von Programmiersprachen wie '''Java''' oder '''C''' aus, so hat ein Array immer eine fixe größe. Das heißt, zur Laufzeit (nach dem das Programm compiliert und gestartet wurde) kann diese nicht verändert werden.
=== Vorteile ===
* '''Der Speicheroverhead ist sehr gering''' - Es wird nur der Speicher reserviert, der für die Anzahl der Elemente benötigt wird.
* '''Geringe Zugriffszeit''' - Wird ein Element an einer stelle angesprochen, so kann für den Zugriff die Exakte Speicheradresse berechnet werden.

=== Nachteile ===
* '''Wenig flexibel''' - Wie bereits erwähnt, muss die größe meist fix definiert werden. Eine vergrößerung/verkleinerung ist nicht möglich, ermöglicht die Programmiersprache dies, so hat dies meist zurfolge, dass das Array neu erstellt wird, und die Elemente kopiert werden müssen.

=== Einsatzgebiete ===
Überall dort, wo eine fixe Speichergröße benötigt und effizient wichtig ist, dort sollte die Verwendung von Arrays in betracht gezogen werden.
* '''Bildmanipulation''' - Wird ein Bild zur Bearbeitung geladen, so kann die ''Bitmap'' in einem Array gespeichert werden. jedes Element im Array entspricht dann einem Pixel.
* '''Puffern von Daten''' - Beim Lesen und Schreiben werden Daten meist in einem Array zwischengespeichert (gepuffert). Danach kann die Bearbeitung erfolgen. Weiters kann bei jedem Lese oder Schreibvorgang erneut das selbe Array verwendet werden, was die Effizienz weiter erhöht.
* '''Jegliches Schachbrettartige Problem mit fixer Größe''' - Schiffe versenken, Schach,...

== Liste ==
Die Liste ist eine sehr gebräuchliche Datenstruktur. Sie ist gekennzeichnet durch, je nach implementierung, gute Zugriffszeiten oder erhöhte Flexibilität.
 
Beziehen wir uns auf die Programmiersprache Java, so ist die Liste ein '''Interface''', das heißt eine Schnittstelle. Diese Schnittstelle definiert einige '''Methoden''' die eine Implementierung erfüllen muss. Einige davon wären:
* <syntaxhighlight lang="java" inline>E get(int index)</syntaxhighlight> - Gibt das Element an der Stelle '''index''' aus
* <syntaxhighlight lang="java" inline>E remove(int index)</syntaxhighlight> - Gibt das Element an der Stelle '''index''' aus
* <syntaxhighlight lang="java" inline>boolean add(E element)</syntaxhighlight> - Fügt ein Element an das Ende der Liste an
* <syntaxhighlight lang="java" inline>boolean add(int index, E element)</syntaxhighlight> - Fügt ein Element an einer bestimmten Position ein, und schiebt nachfolgende Elemente nach rechts (Index wird erhöht)
* ...
Hier ist nun ersichtlich, dass die Flexibilität der Liste ein essenzieller Bestandteil der Definition ist.
 
Anbei einige Implementierungen des Interfaces List.
=== ArrayList ===
Die ArrayList vereint die Eigenschaften einer Liste und eines Arrays. Die interne Implementierung verwendet ein Array von fixer größe um Elemente zu speichern. Wird diese fixe größe überschritten, so wird intern ein neues Array angelegt, je nach implementierung mit einem gewissen Vergrößerungsfaktor. Nach dem neuanlegen des internen Arrays, werden alle Elemente kopiert und in das neue Array eingefügt. Werden Elemente gelöscht, so müssen die Elemente nach dem gelöschten Element um eins nach links verschoben werden.
[[Datei:Removing Element from ArrayList diagram.png|mini|none|400px|Element wird aus ArrayListe entfernt. Quelle: https://beginnersbook.com/2013/12/java-arraylist/]]
In Java wird die größe des internen Arrays nicht automatisch reduziert, wenn Elemente gelöscht werden. Dafür gibt es die Methode <syntaxhighlight lang="java" inline>myArrayList.trim()</syntaxhighlight>

==== Vorteile ====
* '''Relativ geringer Speicheroverhead''' - Dies verhält sich ähnlich wie beim Array. Jedoch können in der ArrayList keine primitiven Datentypen gespeichert werden. Dies bedeutet, es wird nur ein Array von Referenzen erstellt. In jedem Platz findet sich eine Referenz auf das wirkliche Objekt. Dies bedeutet in Bezug auf primitive Datentypen einen weit höheren Speicherbedarf als bei einem Array.
* '''Geringe Zugriffszeit''' - Wird ein Element an einer stelle angesprochen, so kann für den Zugriff die Exakte Speicheradresse berechnet werden.

==== Nachteile ====
* '''Ineffizientes Löschen''' - Laufzeit beim Löschen nicht optimal, Elemente müssen verschoben werden.
* '''Ineffizientes Einfügen''' - Laufzeit beim Einfügen von Elementen an einer gewissen Stelle langsam, wie beim löschen müssen alle Nachfolgenden Elemente verschoben werden.
* '''Ineffizientes Hinzufügen, wenn internes Array voll''' - Laufzeit beim Hinzufügen von Elementen bei vollem Array langsam, ein neues Array muss erstellt werden und alle Elemente

==== Code beispiel ====
<syntaxhighlight lang='Java' line="'line'>
List<Integer> myArrayList = new ArrayList<>();
myArrayList.add(1);
myArrayList.add(1);
myArrayList.add(1);
myArrayList.remove(0);
System.out.println("Element an der Stelle 2: "+myArrayList.get(1));
</syntaxhighlight>
* Zeile 1) Die die ArrayListe wird erzeugt und einer Variable des Typs List zugewiesen. Warum ist das möglich? Weil ArrayList das Interface List implementiert. D.h.: Eine ArrayList ist eine List.
* Zeile 2) - 4) fügen dem Array einen int hinzu. Hier ist zu beachten, der primitive Datentyp '''int''' wird automatisch in die Klasse '''Integer''' umgewandelt. Dieser mechanismus nennt sich Autoboxing.
* Zeile 5) Das Element an der Stelle 0 wird aus der ArrayList entfernt
* Zeile 6) Ausgabe des Elements an der Stelle 2 (Index 1)

=== Einsatzgebiete ===
Die Einsatzgebiete überschneiden sich mit herkömmlichen Arrays. Benötigt man mehr flexibilität und soll '''nicht''' mit primitiven Datentypen gearbeitet werden, so kann anstatt eines Arrays die ArrayListe verwendet werden. Ist die Anzahl der Elemente start fluktuierend (oftmaliges löschen/einfügen/hinzufügen), so sollte man aus oben genannten Gründen auf eine andere Datenstruktur ausweichen.

=== LinkedList oder verkettete Liste ===
Die verkettete Liste ist eine sehr dynamische Datenstruktur. Ihre Größe ist flexibel. Die Daten werden in Knoten gehalten, welche im Falle der einfach verketteten Liste auf den Nachfolger und bei der doppelt verketteten Liste zusätzlich auf den Vorgänger Knoten zeigen. Elemente können einfach an bestimmten Stellen eingefügt oder gelöscht werden, es müssen lediglich die Nachfolger bzw. Vorgänger aktualisiert werden.
[[Datei:Singly linked list and doubly linked list in Java.jpg|mini|none|Einfach und doppelt verkettete Liste. Quelle: https://www.java67.com/2016/01/how-to-implement-singly-linked-list-in-java-using-generics-example.html]]

==== Vorteile ====
* '''Einfügen und Löschen effizient''' - Es müssen lediglich die Zeiger auf den Vorgänger/Nachfolger geändert werden.

==== Nachteile ====
* '''Zufälliger Zugriff langsam''' - Werden in der LinkedList Elemente mit ihrem Index angesprochen, so muss zuerst die komplette Liste bis zum entsprechenden Index durchlaufen werden.
* '''Speicheroverhead''' - Da die Daten in Knoten gespeichert werden müssen entsteht automatisch ein Speicheroverhead.

==== Einsatzgebiete ====
* Wenn die größe der Liste stark variiert, d.h. oftmals Elemente eingefügt, gelöscht und hinzugefügt werden und '''kein''' zufälliger Zugriff benötigt wird.

==== Code beispiel ====
''Hinzufügen eines Elements''
<syntaxhighlight lang='Java' line="'line'">
public boolean add(Integer element) {
Node newNode = new Node(element);
if(root == null) {
root = newNode;
} else {
Node current = root;
while(current.next() != null) {
current = current.next();
}
current.setNext(newNode);
}
return true;
}
</syntaxhighlight>

''Holen eines Elements''
<syntaxhighlight lang='Java' line="'line'">
public Integer get(int index) {
Node current = root;
for(int i=0; i<index && current != null; i++) {
current = current.next();
}
if(current == null) {
throw new IndexOutOfBoundsException();
}
}
</syntaxhighlight>

== Assoziatives Array ==
Das '''assoziative Array''' oder auch Map, ist eine Sammlung von '''Key''', '''Value''' Paaren. Sie eignet sich sehr gut dafür, für einen bestimmten Schlüssel einen Wert zu hinterlegen. Die Operationen, einfügen, löschen, abrufen, sind Konstant und weisen im Normalfall ein Laufzeitverhalten von O(1) auf. Die Reihenfolge der Element ist nicht definiert.

= Sortieralgorithmen =
Sortieralgorithmen werden benötigt um Datenstrukturen nach gewissen Kriterien zu sortieren. Dazu müssen die Elemente natürlich vergleichbar sein, d.h. es muss möglich sein herauszufinden ob ein Element "größer" oder "kleiner" als ein anderes ist.

== Eigenschaften ==
Sortieralgorithmen können über mehrere Eigenschaften verfügen.
=== In-Place ===
Das bedeutet der Sortieralgorithmus benötigt "keinen" weiteren Speicherplatz beim sortieren, bzw. wenn der Speicherbedarf konstant ist, und nicht mit der Anzahl der Elemente wächst. Z.b. der Sortieralgorithmus Mergesort, teilt die Daten der bestehenden Liste in Sublisten auf, er ist somit nicht In-Place.
=== Stabil ===
Ein Sortieralgorithmus arbeitet stabil, wenn dieser eine bestehende korrekte Ordnung nicht verändert.

== Bubblesort ==
Bubblesort ist ein vergleichsweise akademischer Algorithmus. Er ist wenig effizient, arbeitet jedoch '''Stabil''' und '''In-Place'''.
[[Datei:Bubble-sort-example-300px.gif|mini|none|Funktionsweise Bubblesort. Quelle: https://de.wikipedia.org/wiki/Bubblesort]]

=== Code ===
Bubblesort in Java
<syntaxhighlight lang='Java' line="'line'">
public class Bubblesort {
public static void sort(int[] arr) {
int operations = 0;
int n = arr.length;
boolean swapped = false;
do {
swapped = false;
for (int i = 0; i < n - 1; i++) {
operations++;
if (arr[i] > arr[i + 1]) {
int tmp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = tmp;
swapped = true;
}
}
// Letztes Element ist an der richtigen stelle, n um 1 reduzieren
n = n - 1;
} while (swapped);
System.out.println("Operations: " + operations);
}

public static void main(String[] args) {
int[] arr = new int[] { 1, 2, 3, 4, 5, 6 };
sort(arr);
arr = new int[] { 6, 5, 4, 3, 2, 1 };
sort(arr);
arr = new int[] { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 };
sort(arr);
}
}

</syntaxhighlight>

=== Laufzeitanalyse ===
Für die Laufzeitanalyse verwenden wir die maximal mögliche Laufzeit.
Betrachten wir hierfür folgendes Array:
10,8,5,3,2,1
* 1) Durchlauf: Die Zahl 10 wird mit 8,5,3,2 und 1 verglichen und vertauscht.
* 2) Durchlauf: Die Zahl 8 wird mit 5,3,2 und 1 verglichen und vertauscht, '''mit 10 muss nichtmehr verglichen werden'''.
* 3) Durchlauf: Die Zahl 5 wird mit 3,2 und 1 verglichen und vertauscht, '''mit 10, 8 muss nichtmehr verglichen werden'''.
* 4) Durchlauf: Die Zahl 3 wird mit 2 und 1 verglichen und vertauscht, '''mit 10, 8, 5 muss nichtmehr verglichen werden'''.
* 5) Durchlauf: Die Zahl 2 wird mit 1 verglichen und vertauscht, '''mit 10, 8, 5, 3 muss nichtmehr verglichen werden'''.
* Ende, die Zahl 1 muss nichtmehr verglichen werden.

Vergleichen und vertauschen betrachten wir nun als eine Operation.

* 1) Durchlauf -> 5 Operationen
* 2) Durchlauf -> 4 Operationen
* 3) Durchlauf -> 3 Operationen
* 4) Durchlauf -> 2 Operationen
* 5) Durchlauf -> 1 Operation

Das sind für ein Array der Länge 6, 15 Operationen.

==== Die allgemeine Formel lautet ====
* 1) (n-1) + (n-2) + ... 1
* 2) ''Das ist ja der kleine Gauß minus n:'' (n * (n + 1))/2 - n
* 3) (n2 + n - 2*n)/2
* 4) (n2 - n)/2
* 5) 1/2*(n2 - n)
* 6) n2 - n -> Konstante Werte werden bei der O - Notation entfernt
* 7) n2 -> n ist zu n2 vernachlässigbar und wird entfernt

==== Laufzeit ====
'''Somit ist die Laufzeit von Bubblesort O(n2)'''
==== Laufzeit Bestcase ====
Liegt bereits eine sortierte Liste vor, so benötigt Bubblesort nur einen Durchlauf. Dabei erfolgen '''n - 1''' vergleiche. Die Konstante wird entfernt.
 
'''Die Laufzeit im Bestcase ist O(n)'''