Arrays-in-python.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Arrays in Python"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Arrays in Python sind durch den Datentyp ```List``` implementiert. Dies ist für unsere Vorlesung etwas verwirrend, da wir meistens verkettete Listen meinen, wenn wir von Listen sprechen. Der Python Datentyp ```List``` ist aber ein Array im klassischen Sinn, welches Indexierung in konstanter Zeit erlaubt.  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Erzeugen von Arrays"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Folgende Aufrufe illustrieren verschiedene Möglichkeiten ein Array in Python zu erzeugen."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ein Array kann kreiert werden, indem die Elemente zwischen eckigen Klammern [] geschrieben werden. Hier wird ein leeres Array erstellt:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "[]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Und hier ein Array mit 4 Elementen:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "[\"a\", \"list\", \"of\", \"strings\"]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Wenn wir ein Array der Grösse 10, welches alle Werte auf den Wert 0 initialisiert erzeugen wollen, schreiben wir das wie folgt."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "[0] * 10"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Übung: Erzeugen Sie ein Array der Grösse 5, dessen Elemente leere Strings (\"\") sind*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Elemente lesen und setzen"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Gegeben sei folgendes Testarray:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "xs = [\"a\", \"b\", \"c\", \"d\"]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Lesen und setzen von Elementen machen wir mit dem [] Operator. Hier lesen wir das erste Element:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(xs[0])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Python erlaubt auch negative Indices. Wenn der Index negativ ist, wird vom Ende gezählt:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(xs[-1])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Für das Setzen eines Wertes weisen wir dem entsprechenden Arrayelement einfach einen Wert zu:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "xs[2]=\"c'\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Wir sehen, dass hier wirklich der Wert verändert wurde. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(xs)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Länge eines Arrays"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Die Länge eines Arrays kann mittels der Python Funktion ```len``` bestimmt werden. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "len(xs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "len([0]*100)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Finden eines Elements"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Python erlaubt uns auch, nach Elementen in einem Array zu suchen. Die Syntax dafür ist jedoch etwas gewöhnungsbedürftig. Es wird der ```in``` Operator verwendet. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Der Folgende Ausdruck ergibt ```true```, da das Element ```a``` in ```xs``` enthalten ist:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "\"a\" in xs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Der folgende Ausdruck ergibt jedoch ```false```."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "\"I cannot be found \" in xs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Mit der Methode ```index``` können wir uns auch die Position eines Elements im Array angeben lassen:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "xs.index(\"b\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Übung: Was passiert, wenn das Element nicht vorhanden ist?*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Laufzeit "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Im Folgenden messen wir die Laufzeit der verschiedenen Operationen für Arrays von wachsender Grösse. Wir nutzen dazu die Funktion ```timeit``` aus dem gleichnamigen Modul ```timeit```, welche uns erlaubt eine Funktion ```n``` mal aufzurufen. Damit unser Experiment repräsentativ ist, wählen wir das Element zufällig aus. Dafür benötigen wir das Modul ```random```."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import timeit\n",
    "import random"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```timeit``` nimmt als erstes Argument eine Funktion ohne Argumente, welche von ```timeit``` ausgeführt wird, und ein Keyword-Argument ```number``` in dem die Anzahl Wiederholungen angegeben werden. \n",
    "\n",
    "Der folgende Aufruf führt also 10 Mal die Funktion aus, die \"hallo\" ausgibt und berechnet die Zeit, die dafür insgesamt benötigt wird. Dieses mehrmalige Durchführen eines Experiments ist wichtig, da die Laufzeit jedes einzelnen Aufrufs zufälligen Variationen, bedingt durch zum Beispiel die CPU Auslastung oder Betriebssysteminterne Funktionen, ausgesetzt ist. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "    \n",
    "timeit.timeit(lambda: print(\"hallo\"), number=10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Der Aufruf ```lambda: print(\"hello\")``` macht, dass ```print(hello)``` nicht direkt ausgeführt wird, sondern als Funktion an ```timeit``` übergeben wird, welche dann von ```timeit``` ausgeführt wird. Sie müssen die Details dieses Aufrufs nicht verstehen. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Wir können ```timeit``` auch noch eine setup-Funktion übergeben, welche jeweils einmal am Anfang ausgeführt wird. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "timeit.timeit(lambda: print(\"hallo\"), number=10, setup= lambda: print(\"called at the beginning\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Bei unserem ersten Test experimentieren wir mit der Laufzeit für den Arrayzugriff. Wir schreiben dafür die Funktion ```accessArray```, welches jeweils auf einen zufälligen Index im übergebenen Array ```a``` zugreift."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def accessArray(a):\n",
    "    r = random.randint(0, len(a)-1)\n",
    "    a[r] = 10\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Nun können wir die Zugriffszeit für die Arrays der Grösse 10 bis $10^7$ testen:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for i in range(1, 8):\n",
    "    array = [0]*(10**i)\n",
    "    t = timeit.timeit(lambda: accessArray(array), number=100000)\n",
    "    print(\"Zeit für Array der Länge \" + str(len(array)) + \" = \" + str(t))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Wir sehen, dass die Zugriffszeit immer etwa gleich bleibt, obwohl die Länge des Arrays jeweils um Faktor 10 zunimmt. Die Laufzeit, um ein Element an beliebiger Stelle zu lesen oder zu schreiben, ist also konstant."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Nun testen wir die Operation ```find```:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def findInArray(a):\n",
    "   c = \"you wont find me\" in a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for i in range(1, 7):\n",
    "    array = [0]*(10**i)\n",
    "    t = timeit.timeit(lambda: findInArray(array), number=1000)\n",
    "    print(\"Zeit für Array der Länge \" + str(len(array)) + \" = \" + str(t))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Wir sehen, dass hier die Laufzeit ungefähr linear zunimmt. Auch dies entspricht unseren Erwartungen. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Übung: In diesem Experiment wurde das Element nie gefunden. Würde sich etwas ändern, wenn das Element gefunden wird? Experimentieren Sie!*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Zum Schluss wollen wir noch die Laufzeit der Operation ```len``` testen. Unsere Hypothesis ist, dass diese in konstanter Laufzeit berechnet werden kann, da wir einfach für jedes Array die Länge speichern können. Dass dies wirklich der Fall ist, zeigt folgendes Experiment. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for i in range(1, 8):\n",
    "    array = [0]*(10**i)\n",
    "    t = timeit.timeit(lambda: len(array), number=100000)\n",
    "    print(\"Zeit für Array der Länge \" + str(len(array)) + \" = \" + str(t))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.4"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": false,
   "sideBar": false,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": false,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}