{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Module 2, Practical 6\n", "\n", "In this practical we will work with data structures.\n", "\n", "## Data structures\n", "\n", "How do we arrange data within our programs depends on the operations we want to perform on them. To be as effective as possible, we should pick the data structure that gives: \n", "\n", "1. the *most efficient access* to the data according to the operations we intend to perform on the data, and\n", "2. use the *least amount of memory* in the process. \n", "\n", "Programming languages provide many different data structures (e.g. lists, dictionaries, etc) which have different features and performance (both in terms of speed and memory consumption). \n", "\n", "To decide which data type suits our needs better, we need to know the different features of the various datatypes that are available (or that we can implement).\n", "\n", "**Example**: Inserting data into a Python list." ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "List insert with 10 elements took 0.000s\n", "List insert with 20000 elements took 0.109s\n", "------------------\n", "List append with 10 elements took 0.000s\n", "List append with 20000 elements took 0.006s\n" ] } ], "source": [ "import time\n", "\n", "def listInsert(size):\n", " myList = []\n", " for i in range(size):\n", " myList.insert(0, i)\n", " \n", " for i in range(len(myList)):\n", " myList.pop(0) \n", "\n", "def listAppend(size):\n", " myList = []\n", " for i in range(size):\n", " myList.append(i)\n", "\n", " for i in range(len(myList)):\n", " myList.pop(-1)\n", "\n", "\n", "n = 10\n", "start = time.time()\n", "listInsert(n)\n", "end = time.time()\n", "print(\"List insert with {} elements took {:.03f}s\". format(n, end - start))\n", "n = 20000\n", "start = time.time()\n", "listInsert(n)\n", "end = time.time()\n", "print(\"List insert with {} elements took {:.03f}s\". format(n, end - start))\n", "\n", "print(\"------------------\")\n", "n=10\n", "start = time.time()\n", "listAppend(n)\n", "end = time.time()\n", "print(\"List append with {} elements took {:.03f}s\". format(n, end - start))\n", "n = 20000\n", "start = time.time()\n", "listAppend(20000)\n", "end = time.time()\n", "print(\"List append with {} elements took {:.03f}s\". format(n, end - start))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The behaviour above is due to the fact that adding an element at the beginning of the list with ```list.insert(0,element)``` and ```list.pop(0)``` end up with python having to move all the elements present in the list to make room for the new element or to adjust the list when we remove it. \n", "\n", "By adding and removing from the back of the list we are actually a lot faster. Later on we will also see the ```collections.deque``` data structure, that allows for quick operations on lists.\n", " \n", "*How can we analyze and compare different data types?*\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Abstract Data Types (ADTs)\n", "\n", "ADTs are a mathematical description of a strategy to store the data and operations that can be performed on the data (in abstract terms, without focusing on implementation). \n", "*Abstract data types* provide the specifications of what the data types should look like/behave.\n", "\n", "Some examples taken from the lectures:\n", "\n", "#### ADT: Sequence\n", "\n", "A sequence is a dynamic data structure (no limit on the number of elements) that contains (possibly repeated) sorted elements (sorted not by the value of the elements, but based on their position within the structure). Allowed operations are:\n", "\n", "- *remove* elements by their index (index)\n", "- *directly access* some elements like the first or the last (*head* and *tail*) or given their index (position)\n", "- *sequentially access* all the elements moving forward (*next*) or backwards (*previous*) in the structure.\n", "\n", "Full specification of the sequence ADT (from the lecture): \n", "\n", "![](images/sequenceADT.png)\n", "\n", "\n", "#### ADT: Set\n", "Sets are dynamic data structures that contain **non-repeated** elements in **no specific order**. Allowed operations are: \n", "\n", "- *insert*, *delete* and *contains* to add, remove or test the presence of an element in the set\n", "- *minimum* and *maximum* to retrieve the minimum and maximum element (based on values)\n", "- it should be possible to *iterate* through the elements in the set (in no specific order) with something like ```for el in set:```. \n", " \n", "Finally, some operations are defined on two sets like: *union*, *intersection*, *difference*. \n", "\n", "Full specification of the set ADT (from the lecture):\n", "\n", "![](images/setADT.png)\n", "\n", "Python already provides the ```set``` data structure. \n", "Let's see how to define and interact with a set through some examples:" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Start with an empty set with add some elements" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "set()\n", "{'Minni', 'Paperino', 'Pippo'}\n" ] } ], "source": [ "a = set()\n", "print(a)\n", "a.add(\"Pippo\")\n", "a.add(\"Paperino\")\n", "a.add(\"Minni\")\n", "print(a) " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Adding an already existing element has no effect on the set" ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "{'Minni', 'Paperino', 'Pippo'}\n" ] } ], "source": [ "a.add(\"Pippo\")\n", "print(a)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Sets can also be generated starting from existing elements" ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "\n", "List: [121, 5, 4, 1, 1, 4, 2, 121]\n", "Set: {1, 2, 4, 5, 121}\n", "\n", "S1: {'b', 'c', 'd', 'a', 'r'}\n", "S2: {'b', 'E', 'A', 'd', 'a'}\n" ] } ], "source": [ "#a set from a list of values\n", "myList = [121, 5, 4, 1, 1, 4, 2, 121]\n", "print(\"\\nList: {}\".format(myList))\n", "S = set(myList)\n", "print(\"Set: {}\".format(S))\n", "\n", "#from strings\n", "S1 = set(\"abracadabra\")\n", "S2 = set(\"AbbadabE\")\n", "print(\"\\nS1: {}\".format(S1))\n", "print(\"S2: {}\".format(S2))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Accessing elements in a set is done by iteration (`for`) or by verifying their presence (`in`) " ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Accessing set S\n", "\telement: 1\n", "\telement: 2\n", "\telement: 4\n", "\telement: 5\n", "\telement: 121\n", "\n", "Is 44 in S? False\n", "Is 121 in S? True\n" ] } ], "source": [ "print(\"Accessing set S\")\n", "for el in S:\n", " print(\"\\telement: {}\".format(el))\n", "\n", "print()\n", "print(\"Is 44 in S? {}\".format(44 in S))\n", "print(\"Is 121 in S? {}\".format(121 in S))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Sets allow to perform mathematical set operations (Intersection, union, etc..)" ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Intersection(S1,S2): {'d', 'b', 'a'} \n", "\n", "Union(S1,S2): {'b', 'E', 'A', 'c', 'd', 'a', 'r'} \n", "\n", "In S1 but not in S2: {'c', 'r'} \n", "\n", "In S2 but not in S1: {'A', 'E'} \n", "\n", "In S1 or S2 but not in both: {'E', 'r', 'A', 'c'}\n" ] } ], "source": [ "print(\"Intersection(S1,S2): {} \\n\".format(S1 & S2))\n", "print(\"Union(S1,S2): {} \\n\".format(S1 | S2))\n", "print(\"In S1 but not in S2: {} \\n\".format(S1 - S2))\n", "print(\"In S2 but not in S1: {} \\n\".format(S2 - S1))\n", "print(\"In S1 or S2 but not in both: {}\".format(S1 ^ S2))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Iterators in Python\n", "\n", "When we define a new data structure that is intended to be iterated, we need to specify how to traverse this structure, and this is done through the construct called **iterator**. \n", "\n", "In python, to create an object/class that is also an iterator you have to implement the methods __iter__() and __next__() to your object.\n", "\n", "As you have learned, all classes have a function called __init__(), which allows you to do some initializing when the object is being created.\n", "\n", "- The __iter__() method acts similar, you can do operations as choosing on which attribute to iterate. Still, keep in mind that this method MUST always return the iterator object itself.\n", "\n", "- The __next__() method also allows you to do operations, and must return the next item in the sequence.\n", "\n", "To prevent the iteration from going on forever, we can use the ```StopIteration``` statement.\n", "\n", "In the __next__() method, we can add a terminating condition to raise an error if the iteration is done a specified number of times.\n", "\n", "Example:" ] }, { "cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [ { "ename": "TypeError", "evalue": "'MyNumbers' object is not iterable", "output_type": "error", "traceback": [ "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m", "\u001b[0;31mTypeError\u001b[0m Traceback (most recent call last)", "Cell \u001b[0;32mIn[9], line 7\u001b[0m\n\u001b[1;32m 3\u001b[0m \u001b[39mself\u001b[39m\u001b[39m.\u001b[39mdata \u001b[39m=\u001b[39m data\n\u001b[1;32m 5\u001b[0m myclass \u001b[39m=\u001b[39m MyNumbers([\u001b[39m1\u001b[39m,\u001b[39m2\u001b[39m,\u001b[39m3\u001b[39m,\u001b[39m4\u001b[39m,\u001b[39m5\u001b[39m])\n\u001b[0;32m----> 7\u001b[0m \u001b[39mfor\u001b[39;00m x \u001b[39min\u001b[39;00m myclass:\n\u001b[1;32m 8\u001b[0m \u001b[39mprint\u001b[39m(x)\n", "\u001b[0;31mTypeError\u001b[0m: 'MyNumbers' object is not iterable" ] } ], "source": [ "class MyNumbers:\n", " def __init__(self, data):\n", " self.data = data\n", "\n", "myclass = MyNumbers([1,2,3,4,5])\n", "\n", "for x in myclass:\n", " print(x)" ] }, { "cell_type": "code", "execution_count": 11, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "1\n", "2\n", "3\n", "4\n", "5\n" ] } ], "source": [ "class MyNumbers:\n", " def __init__(self, data):\n", " self.data = data\n", "\n", " # define __iter__ and __next__ methods for iteration!!\n", " def __iter__(self): \n", " self.i = 0\n", " return self\n", "\n", " def __next__(self):\n", " if self.i < len(self.data):\n", " current = self.i\n", " self.i += 1\n", " return self.data[current]\n", " else:\n", " self.i = 0\n", " raise StopIteration()\n", "\n", "myclass = MyNumbers([1,2,3,4,5])\n", "\n", "for x in myclass:\n", " print(x)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Exercise (set implementation)\n", "\n", "1. Write a simple MySet class that implements the abstract data type **set**. Use a dictionary as internal data structure (hint: you can put the element as key of the dictionary and the value as \"1\"). For simplicity, the object should be constructed by passing to it a list of elements (e.g. S = mySet(\\[1,2,3\\]).\n", "\n", "The ADT of the set structure is (i.e. the methods to implement): \n", "\n", "![](images/setADT.png)\n", "\n", "Implement the **iterator** interface that **yields** the next elements. Implement a special method ```__contains__``` to test if an element is present with **el in S**. \n", "\n", "Test the code with:\n", "\n", "```python\n", " S = MySet([33, 1,4,5,7,5,5,5,4,7,3])\n", " print(\"Initial S: {}\".format(S))\n", " S.add(125)\n", " S.discard(77)\n", " S.discard(5)\n", " print(\"S now: {}\".format(S))\n", " print(\"Does S contain 13? {}\".format(13 in S))\n", " print(\"Does S contain 125? {}\".format(125 in S))\n", " print(\"All elements in S:\")\n", " for s in S:\n", " print(\"\\telement: {}\".format(s))\n", "\n", " print(\"\\nS:{}\".format(S))\n", " S1 = MySet([33, 0, 3,4, 4, 33,44])\n", " print(\"S1: {}\".format(S1))\n", " print(\"\\nUnion: {}\".format(S.union(S1)))\n", " print(\"Intersection: {}\".format(S.intersection(S1)))\n", " print(\"S - S1: {}\".format(S.difference(S1)))\n", " print(\"S1 - S: {}\".format(S1.difference(S)))\n", " print(\"(S - S1) U (S1 -S): {}\".format(S.difference(S1).union(S1.difference(S))))\n", "```\n", "\n", "and compare the results with what would give python's built-in ```set``` data structure.\n", "\n", "
Show/Hide Implementation\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Initial S: {33, 1, 4, 5, 7, 3}\n", "S now: {33, 1, 4, 7, 3, 125}\n", "Does S contain 13? False\n", "Does S contain 125? True\n", "All elements in S:\n", "\telement: 33\n", "\telement: 1\n", "\telement: 4\n", "\telement: 7\n", "\telement: 3\n", "\telement: 125\n", "\n", "S: {33, 1, 4, 7, 3, 125}\n", "S1: {33, 0, 3, 4, 44}\n", "\n", "Union: {33, 0, 3, 4, 44, 1, 7, 125}\n", "Intersection: {33, 4, 3}\n", "S - S1: {1, 7, 125}\n", "S1 - S: {0, 44}\n", "(S - S1) U (S1 -S): {0, 44, 1, 7, 125}\n", "\n", "Testing python's builtin:\n", "pS: {33, 1, 3, 4, 7, 125}\n", "pS1: {0, 33, 3, 4, 44}\n", "Union: {0, 33, 1, 3, 4, 7, 44, 125}\n", "Intersection: {33, 3, 4}\n", "pS - pS1: {1, 125, 7}\n", "pS1 - pS: {0, 44}\n", "(pS - pS1) U (pS1 -pS): {0, 1, 7, 44, 125}\n" ] } ], "source": [ "class MySet:\n", " def __init__(self, elements):\n", " self.__data = dict()\n", " for el in elements:\n", " self.__data[el] = 1\n", " \n", " #let's specify the special operator for len\n", " def __len__(self):\n", " return len(self.__data)\n", " \n", " #this is the special operator for in\n", " def __contains__(self, element):\n", " el = self.__data.get(element, None)\n", " return el != None\n", " \n", " #we do not redefine __add__ because that is for S1 + S2\n", " #where S1 and S2 are sets\n", " def add(self, element):\n", " #don't care if already there\n", " self.__data[element] = 1 \n", " \n", " def discard(self, element):\n", " #equivalent to: \n", " #if element in self.__data: del self.__data[element]\n", " el = self.__data.pop(element, None)\n", " \n", " def __iter__(self):\n", " self.iteratorPosition = 0\n", " return self # the object itself will be the iterator...\n", "\n", " def __next__(self):\n", " if self.iteratorPosition > (len(self.__data) - 1):\n", " self.iteratorPosition = 0\n", " raise StopIteration()\n", " pos = self.iteratorPosition\n", " self.iteratorPosition += 1\n", " keys = list(self.__data.keys())\n", " return keys[pos]\n", " \n", " def __str__(self):\n", " keys = self.__data.keys() \n", " return \"{\"+\"{}\".format(\", \".join([str(x) for x in keys])) + \"}\"\n", "\n", " def union(self, other):\n", " \"\"\"elements in either of the two sets\"\"\"\n", " elements = []\n", " for el in other:\n", " elements.append(el)\n", " S2 = MySet(elements)\n", " for el in self:\n", " S2.add(el)\n", " return S2\n", "\n", " def intersection(self, other):\n", " \"\"\"elements in both sets\"\"\"\n", " \"\"\"elements in both sets\"\"\"\n", " my_keys = self.__data.keys()\n", " your_keys = other.__data.keys()\n", " inter = [x for x in my_keys if x in your_keys]\n", " return MySet(inter)\n", "\n", " def difference(self, other):\n", " \"\"\"elements in self but not in other\"\"\"\n", " diff = [x for x in self if x not in other]\n", " return MySet(diff)\n", "\n", "### TESTING MySet Class ###\n", "S = MySet([33, 1,4,5,7,5,5,5,4,7,3])\n", "print(\"Initial S: {}\".format(S))\n", "S.add(125)\n", "S.discard(77)\n", "S.discard(5)\n", "print(\"S now: {}\".format(S))\n", "print(\"Does S contain 13? {}\".format(13 in S))\n", "print(\"Does S contain 125? {}\".format(125 in S))\n", "print(\"All elements in S:\")\n", "for s in S:\n", " print(\"\\telement: {}\".format(s))\n", "\n", "print(\"\\nS: {}\".format(S))\n", "S1 = MySet([33, 0, 3,4, 4, 33,44])\n", "print(\"S1: {}\".format(S1))\n", "print(\"\\nUnion: {}\".format(S.union(S1)))\n", "print(\"Intersection: {}\".format(S.intersection(S1)))\n", "print(\"S - S1: {}\".format(S.difference(S1)))\n", "print(\"S1 - S: {}\".format(S1.difference(S)))\n", "print(\"(S - S1) U (S1 -S): {}\".format(S.difference(S1).union(S1.difference(S))))\n", "\n", "#### Test vs python's set\n", "print(\"\\nTesting python's builtin:\")\n", "pS = set([33, 1,4,5,7,5,5,5,4,7,3])\n", "pS.add(125)\n", "#pS.remove(77) # this gives an error!\n", "pS.remove(5)\n", "print(\"pS: {}\".format(pS))\n", "pS1 = set([33, 0, 3,4, 4, 33,44])\n", "print(\"pS1: {}\".format(pS1))\n", "print(\"Union: {}\".format(pS | pS1))\n", "print(\"Intersection: {}\".format(pS & pS1))\n", "print(\"pS - pS1: {}\".format(pS - pS1))\n", "print(\"pS1 - pS: {}\".format(pS1 - pS))\n", "print(\"(pS - pS1) U (pS1 -pS): {}\".format(pS - pS1 | pS1 - pS))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Download the complete source file: [MySet.py](exercises/data_structures/MySet.py)\n", "
\n", "\n", "### ADT: dictionary\n", "\n", "Dictionaries map keys to values and allow insertion, removal and lookup:\n", "\n", "![](images/dictionaryADT.png)\n", "\n", "\n", "## Linked lists\n", "\n", "Linked lists are collections of objects and pointers (either 1 or 2) that point to the *next* element in the list or to *both the next and previous* element in the list. \n", "\n", "Linked lists can be **linear** or **circular** when the last element is connected to the first and only a fixed amount of elements is allowed and then newly-added elements replace previous ones. \n", "\n", "They can be **bidirectional** if from one element one can move to the **previous** and to the **next** or **monodirectional** when it is possible only to go to the **next** element.\n", "\n", "Here are some of the possible types of list (from the lecture): \n", "\n", "![](images/linked_lists.png)\n", "\n", "The operations that can be performed on lists are:\n", "\n", "![](images/list_operations.png)\n", "\n", "### Example: bidirectional linked list\n", "\n", "Let's implement a bidirectional linked list of objects of type \"Node\" (that contain attributes: ```data```, ```prevEl``` and ```nextEl```. " ] }, { "cell_type": "code", "execution_count": 14, "metadata": {}, "outputs": [], "source": [ "class Node:\n", " def __init__(self, data):\n", " self.__data = data\n", " self.__prevEl = None\n", " self.__nextEl = None\n", "\n", " def getData(self):\n", " return self.__data\n", " def setData(self, newdata):\n", " self.__data = newdata\n", "\n", " # next element\n", " def setNext(self, node):\n", " self.__nextEl = node\n", " def getNext(self):\n", " return self.__nextEl\n", "\n", " # previous element\n", " def setPrev(self,node):\n", " self.__prevEl = node\n", " def getPrev(self):\n", " return self.__prevEl\n", "\n", " def __str__(self):\n", " return str(self.__data)\n", "\n", " # for sorting\n", " def __lt__(self, other):\n", " return self.__data < other.__data\n", "\n", "\n", "class BiLinkList:\n", " def __init__(self):\n", " self.__head = None\n", " self.__tail = None\n", " self.__len = 0\n", " # to reduce complexity of min and max calculation, we keep track \n", " # of this information during insertions\n", " self.__minEl = None # this assumes that nodes can be sorted\n", " self.__maxEl = None # this assumes that nodes can be sorted\n", "\n", " def __len__(self):\n", " return self.__len\n", " def min(self):\n", " return self.__minEl\n", " def max(self):\n", " return self.__maxEl\n", "\n", " def append(self,node):\n", " if type(node) != Node:\n", " raise TypeError(\"node is not of type Node\")\n", " else:\n", " if self.__head == None:\n", " self.__head = node\n", " self.__tail = node\n", " else:\n", " node.setPrev(self.__tail)\n", " self.__tail.setNext(node)\n", " self.__tail = node\n", " self.__len += 1\n", " # this assumes that nodes can be sorted\n", " if self.__minEl == None or self.__minEl > node:\n", " self.__minEl = node\n", " if self.__maxEl == None or self.__maxEl < node:\n", " self.__maxEl = node\n", "\n", " def insert(self, node, i):\n", " # to avoid index problems, if i is out of bounds\n", " # we insert at beginning or end\n", " if i > self.__len:\n", " i = self.__len #I know that it is after tail!\n", " if i < 0:\n", " i = 0\n", " cnt = 0\n", " cur_el = self.__head\n", " while cnt < i:\n", " cur_el = cur_el.getNext()\n", " cnt += 1\n", " #add node before cur_el\n", " if cur_el == self.__head:\n", " #add before current head\n", " node.setNext(self.__head)\n", " self.__head.setPrev(node)\n", " self.__head = node\n", " else:\n", " if cur_el == None:\n", " #add after tail\n", " self.__tail.setNext(node)\n", " node.setPrev(self.__tail)\n", " self.__tail = node\n", " else:\n", " #add in the middle of the list\n", " p = cur_el.getPrev()\n", " p.setNext(node)\n", " node.setPrev(p)\n", " node.setNext(cur_el)\n", " cur_el.setPrev(node)\n", "\n", " self.__len += 1\n", " #This assumes that nodes can be sorted\n", " if self.__minEl == None or self.__minEl > node:\n", " self.__minEl = node\n", " if self.__maxEl == None or self.__maxEl < node:\n", " self.__maxEl = node\n", "\n", " def getAtIndex(self, i):\n", " if i > self.__len:\n", " return None\n", " else:\n", " cnt = 0\n", " cur_el = self.__head\n", " while cnt < self.__len:\n", " if cnt == i:\n", " return cur_el\n", " else:\n", " cnt += 1\n", " cur_el = cur_el.getNext()\n", "\n", " def iterator(self):\n", " cur_el = self.__head\n", " while cur_el != None:\n", " yield cur_el\n", " cur_el = cur_el.getNext()\n", "\n", " def __str__(self):\n", " if self.__head != None:\n", " dta = str(self.__head)\n", " cur_el = self.__head.getNext()\n", " while cur_el != None:\n", " dta += \" <-> \" + str(cur_el)\n", " cur_el = cur_el.getNext()\n", "\n", " return str(dta)\n", " else:\n", " return \"\"\n", " \n", " def remove(self, element):\n", " pass\n", "\n", " def slice(self, x, y):\n", " pass" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Download the complete source file: [BidirectionalList.py](exercises/data_structures/BidirectionalList.py)\n", "\n", "Let's test the BiLinkList implementation!" ] }, { "cell_type": "code", "execution_count": 15, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "1 <-> 11 <-> 21 <-> 31 <-> 41\n", "\t1 prev:None next:11\n", "\t11 prev:1 next:21\n", "\t21 prev:11 next:31\n", "\t31 prev:21 next:41\n", "\t41 prev:31 next:None\n", "1000 <-> 1 <-> 11 <-> 2 <-> 21 <-> 31 <-> 41 <-> -10 <-> 27\n", "\t1000 prev:None next:1\n", "\t1 prev:1000 next:11\n", "\t11 prev:1 next:2\n", "\t2 prev:11 next:21\n", "\t21 prev:2 next:31\n", "\t31 prev:21 next:41\n", "\t41 prev:31 next:-10\n", "\t-10 prev:41 next:27\n", "\t27 prev:-10 next:None\n", "Number of elements: 9 min: -10 max: 1000\n", "MLL[4] = 21\n", "Moving backwards 1 steps from 21\n", "\tI find node: 2\n", "Moving backwards 2 steps from 2\n", "\tI find node: 11\n", "Moving backwards 3 steps from 11\n", "\tI find node: 1\n" ] } ], "source": [ "MLL = BiLinkList()\n", "for i in range(1,50,10):\n", " n = Node(i)\n", " MLL.append(n)\n", "print(MLL)\n", "for el in MLL.iterator():\n", " print(\"\\t{} prev:{} next:{}\".format(el,\n", " el.getPrev(),\n", " el.getNext()))\n", "n = Node(2)\n", "MLL.insert(n,2)\n", "n = Node(-10)\n", "MLL.append(n)\n", "n = Node(1000)\n", "MLL.insert(n, -1)\n", "n = Node(27)\n", "MLL.insert(n, 2000)\n", "\n", "print(MLL)\n", "for el in MLL.iterator():\n", " print(\"\\t{} prev:{} next:{}\".format(el,\n", " el.getPrev(),\n", " el.getNext()))\n", "print(\"Number of elements: {} min: {} max: {}\".format(len(MLL),\n", " MLL.min(),\n", " MLL.max()))\n", "N = MLL.getAtIndex(4)\n", "print(\"MLL[4] = {}\".format(N))\n", "for i in range(3):\n", " print(\"Moving backwards {} steps from {}\".format(i+1, N))\n", " print(\"\\tI find node: {}\".format(N.getPrev()))\n", " N = N.getPrev()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Exercise (complete bidirectional list)\n", "\n", "2. Complete the bidirectional linked list example seen above by implementing the following methods:\n", "\n", "- ```remove(x)``` method that removes the element x from the list if present\n", "- ```slice(x,y)``` where ```x``` and ```y``` are integers. The slice method should return another bidirectionaly linked list with elements from ```x``` (included) to ```y``` (excluded). \n", "\n", "
Show/Hide Solution\n" ] }, { "cell_type": "code", "execution_count": 16, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "1 <-> 11 <-> 21 <-> 31 <-> 41\n", "\t1 prev:None next:11\n", "\t11 prev:1 next:21\n", "\t21 prev:11 next:31\n", "\t31 prev:21 next:41\n", "\t41 prev:31 next:None\n", "1000 <-> 1 <-> 11 <-> 2 <-> 21 <-> 31 <-> 41 <-> -10 <-> 27\n", "\t1000 prev:None next:1\n", "\t1 prev:1000 next:11\n", "\t11 prev:1 next:2\n", "\t2 prev:11 next:21\n", "\t21 prev:2 next:31\n", "\t31 prev:21 next:41\n", "\t41 prev:31 next:-10\n", "\t-10 prev:41 next:27\n", "\t27 prev:-10 next:None\n", "Number of elements: 9 min: -10 max: 1000\n", "MLL[3] = 2\n", "2 removed!\n", "1000 <-> 1 <-> 11 <-> 21 <-> 31 <-> 41 <-> -10 <-> 27\n", "\t1000 prev:None next:1\n", "\t1 prev:1000 next:11\n", "\t11 prev:1 next:21\n", "\t21 prev:11 next:31\n", "\t31 prev:21 next:41\n", "\t41 prev:31 next:-10\n", "\t-10 prev:41 next:27\n", "\t27 prev:-10 next:None\n", "MLL[0] = 1000\n", "1000 removed!\n", "1 <-> 11 <-> 21 <-> 31 <-> 41 <-> -10 <-> 27\n", "\t1 prev:None next:11\n", "\t11 prev:1 next:21\n", "\t21 prev:11 next:31\n", "\t31 prev:21 next:41\n", "\t41 prev:31 next:-10\n", "\t-10 prev:41 next:27\n", "\t27 prev:-10 next:None\n", "Slice[2,4]:\n", "21 <-> 31\n", "Slice[3,15]:\n", "31 <-> 41 <-> -10 <-> 27\n", "Remove all\n", "1 removed!\n", "11 <-> 21 <-> 31 <-> 41 <-> -10 <-> 27\n", "11 removed!\n", "21 <-> 31 <-> 41 <-> -10 <-> 27\n", "21 removed!\n", "31 <-> 41 <-> -10 <-> 27\n", "31 removed!\n", "41 <-> -10 <-> 27\n", "41 removed!\n", "-10 <-> 27\n", "-10 removed!\n", "27\n", "27 removed!\n", "\n", "Current list content: \n" ] } ], "source": [ "class Node:\n", " def __init__(self, data):\n", " self.__data = data\n", " self.__prevEl = None\n", " self.__nextEl = None\n", "\n", " def getData(self):\n", " return self.__data\n", " def setData(self, newdata):\n", " self.__data = newdata\n", "\n", " # next element\n", " def setNext(self, node):\n", " self.__nextEl = node\n", " def getNext(self):\n", " return self.__nextEl\n", "\n", " # previous element\n", " def setPrev(self,node):\n", " self.__prevEl = node\n", " def getPrev(self):\n", " return self.__prevEl\n", "\n", " def __str__(self):\n", " return str(self.__data)\n", "\n", " # for sorting\n", " def __lt__(self, other):\n", " return self.__data < other.__data\n", "\n", "\n", "class BiLinkList:\n", " def __init__(self):\n", " self.__head = None\n", " self.__tail = None\n", " self.__len = 0\n", " # to reduce complexity of min and max calculation, we keep track \n", " # of this information during insertions\n", " self.__minEl = None # this assumes that nodes can be sorted\n", " self.__maxEl = None # this assumes that nodes can be sorted\n", "\n", " def __len__(self):\n", " return self.__len\n", " def min(self):\n", " return self.__minEl\n", " def max(self):\n", " return self.__maxEl\n", "\n", " def append(self,node):\n", " if type(node) != Node:\n", " raise TypeError(\"node is not of type Node\")\n", " else:\n", " if self.__head == None:\n", " self.__head = node\n", " self.__tail = node\n", " else:\n", " node.setPrev(self.__tail)\n", " self.__tail.setNext(node)\n", " self.__tail = node\n", " self.__len += 1\n", " # this assumes that nodes can be sorted\n", " if self.__minEl == None or self.__minEl > node:\n", " self.__minEl = node\n", " if self.__maxEl == None or self.__maxEl < node:\n", " self.__maxEl = node\n", "\n", " def insert(self, node, i):\n", " # to avoid index problems, if i is out of bounds\n", " # we insert at beginning or end\n", " if i > self.__len:\n", " i = self.__len #I know that it is after tail!\n", " if i < 0:\n", " i = 0\n", " cnt = 0\n", " cur_el = self.__head\n", " while cnt < i:\n", " cur_el = cur_el.getNext()\n", " cnt += 1\n", " #add node before cur_el\n", " if cur_el == self.__head:\n", " #add before current head\n", " node.setNext(self.__head)\n", " self.__head.setPrev(node)\n", " self.__head = node\n", " else:\n", " if cur_el == None:\n", " #add after tail\n", " self.__tail.setNext(node)\n", " node.setPrev(self.__tail)\n", " self.__tail = node\n", " else:\n", " #add in the middle of the list\n", " p = cur_el.getPrev()\n", " p.setNext(node)\n", " node.setPrev(p)\n", " node.setNext(cur_el)\n", " cur_el.setPrev(node)\n", "\n", " self.__len += 1\n", " #This assumes that nodes can be sorted\n", " if self.__minEl == None or self.__minEl > node:\n", " self.__minEl = node\n", " if self.__maxEl == None or self.__maxEl < node:\n", " self.__maxEl = node\n", "\n", " def getAtIndex(self, i):\n", " if i > self.__len:\n", " return None\n", " else:\n", " cnt = 0\n", " cur_el = self.__head\n", " while cnt < self.__len:\n", " if cnt == i:\n", " return cur_el\n", " else:\n", " cnt += 1\n", " cur_el = cur_el.getNext()\n", "\n", " def iterator(self):\n", " cur_el = self.__head\n", " while cur_el != None:\n", " yield cur_el\n", " cur_el = cur_el.getNext()\n", "\n", " def __str__(self):\n", " if self.__head != None:\n", " dta = str(self.__head)\n", " cur_el = self.__head.getNext()\n", " while cur_el != None:\n", " dta += \" <-> \" + str(cur_el)\n", " cur_el = cur_el.getNext()\n", "\n", " return str(dta)\n", " else:\n", " return \"\"\n", " \n", " ###################################################\n", " ################### NEW METHODS ###################\n", " # WARINING: these implementations do not update \n", " # self.__minEl and self.__maxEl\n", " ###################################################\n", " def remove(self, element):\n", " if self.__head != None:\n", " cur_el = self.__head\n", " while cur_el != element and cur_el != None:\n", " cur_el = cur_el.getNext()\n", "\n", " if cur_el != None:\n", " p = cur_el.getPrev()\n", " n = cur_el.getNext()\n", "\n", " if cur_el == self.__head:\n", " self.__head = n\n", "\n", " if cur_el == self.__tail:\n", " self.__tail = p\n", "\n", " if n != None:\n", " n.setPrev(p)\n", " if p != None:\n", " p.setNext(n)\n", " \n", " self.__len -= 1\n", "\n", " \n", " def slice(self, x, y):\n", " m = min(x,y)\n", " M = max(x,y)\n", " \n", " if m > self.__len:\n", " return None\n", " else:\n", " cur_el = self.__head\n", " cnt = 0\n", " while cnt < m:\n", " cur_el = cur_el.getNext()\n", " cnt += 1\n", " nList = BiLinkList()\n", " \n", " while cnt < M and cur_el != None:\n", " n = Node(cur_el.getData())\n", " cur_el = cur_el.getNext()\n", " nList.append(n)\n", " cnt += 1\n", " return nList\n", " \n", " ###################################################\n", " ############### END NEW METHODS ###################\n", " ###################################################\n", "\n", "\n", "\n", "# TESTING \n", "MLL = BiLinkList()\n", "for i in range(1,50,10):\n", " n = Node(i)\n", " MLL.append(n)\n", "print(MLL)\n", "for el in MLL.iterator():\n", " print(\"\\t{} prev:{} next:{}\".format(el,el.getPrev(), \n", " el.getNext()))\n", "n = Node(2)\n", "MLL.insert(n,2)\n", "n = Node(-10)\n", "MLL.append(n)\n", "n = Node(1000)\n", "MLL.insert(n, -1)\n", "n = Node(27)\n", "MLL.insert(n, 2000)\n", "\n", "print(MLL)\n", "for el in MLL.iterator():\n", " print(\"\\t{} prev:{} next:{}\".format(el,el.getPrev(), \n", " el.getNext()))\n", "print(\"Number of elements: {} min: {} max: {}\".format(len(MLL),\n", " MLL.min(), \n", " MLL.max()))\n", "n = MLL.getAtIndex(3)\n", "print(\"MLL[3] = {}\".format(n))\n", "MLL.remove(n)\n", "print(\"{} removed!\".format(n))\n", "print(MLL)\n", "for el in MLL.iterator():\n", " print(\"\\t{} prev:{} next:{}\".format(el,el.getPrev(), \n", " el.getNext()))\n", "\n", "n = MLL.getAtIndex(0)\n", "print(\"MLL[0] = {}\".format(n))\n", "MLL.remove(n)\n", "print(\"{} removed!\".format(n))\n", "print(MLL)\n", "\n", "for el in MLL.iterator():\n", " print(\"\\t{} prev:{} next:{}\".format(el,el.getPrev(), \n", " el.getNext()))\n", " \n", "#slice:\n", "print(\"Slice[2,4]:\")\n", "print(MLL.slice(2,4))\n", "\n", "#slice:\n", "print(\"Slice[3,15]:\")\n", "print(MLL.slice(3,15))\n", "\n", "#Removing all elements now.\n", "print(\"Remove all\")\n", "for i in range(len(MLL)):\n", " n = MLL.getAtIndex(0)\n", " MLL.remove(n)\n", " print(\"{} removed!\".format(n))\n", " print(MLL)\n", "print(\"Current list content:\", MLL)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Download the complete source file: [BidirectionalList2.py](exercises/data_structures/BidirectionalList2.py)\n", "\n", "**Warning:** the implementation provided above is not completely correct... what happens to min/max when a node si removed or the list is sliced?\n", "
\n", "\n", "### Exercise (circular list)\n", "\n", "3. Implement a circular single-directional linked list of objects SingleNode (that have a data and a link to the next element) with the following methods: \n", "\n", "- ```append(element)``` : adds at the end of the list;\n", "\n", "- ```extend(list_of_elements)``` : adds all the elements in the list\n", "\n", "- ```get(index)``` : reads the node at position index;\n", "\n", "- ```removeAt(index)``` : removes the element at position index if it exists;\n", "\n", "- ```removeEl(el)``` : removes the element el, if present.\n", "\n", "- ```head()``` : gets the first element of the list;\n", "\n", "- ```tail()``` : gets the last element of the list;\n", "\n", "- ```__len__()``` : returns the length of the list;\n", "\n", "- ```__str__()``` : returns a string representation of the list: \n", "\n", "```\n", "1 --> 2 --> 3 --> ... N --|\n", "^-------------------------| \n", "```\n", "\n", "Remember that a circular list should always have the last element (tail) pointing to the first element (head):\n", "\n", "![](images/circular_list.png)\n", "\n", "Test your class with the following code:\n", "\n", "```python\n", " CL = CircularList()\n", " n = SingleNode([1])\n", " n1 = SingleNode(2)\n", " n2 = SingleNode([3])\n", " n3 = SingleNode([4])\n", " n4 = SingleNode(5)\n", " n5 = SingleNode([6])\n", " CL.append(n)\n", " CL.append(n1)\n", " CL.append(n2)\n", " CL.extend([n3,n4,n5])\n", " n = SingleNode(\"luca\")\n", " CL.append(n)\n", " print(CL)\n", " print(\"CL has length: {}\".format(len(CL)))\n", " print(\"Head:{}\\nTail:{}\".format(CL.head(),CL.tail()))\n", " print(\"{} is at position: {}\".format(CL.get(3),3))\n", " print(\"{} is at position: {}\".format(CL.get(-10),-10))\n", " print(\"{} is at position: {}\".format(CL.get(20),20))\n", " print(\"{} is at position: {}\".format(CL.get(0),0))\n", " CL.removeAt(2)\n", " CL.removeAt(5)\n", " print(CL)\n", " CL.removeEl(n5)\n", " print(CL)\n", " #n is not present!\n", " CL.removeEl(n)\n", " print(CL)\n", "```\n", "\n", "
Show/Hide Solution\n" ] }, { "cell_type": "code", "execution_count": 17, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[1]-->2-->[3]-->[4]-->5-->[6]-->luca--|\n", "^-------------------------------------|\n", "CL has length: 7\n", "Head:[1]\n", "Tail:luca\n", "[4] is at position: 3\n", "5 is at position: -10\n", "luca is at position: 20\n", "[1] is at position: 0\n", "[1]-->2-->[4]-->5-->[6]--|\n", "^------------------------|\n", "[1]-->2-->[4]-->5--|\n", "^------------------|\n", "[1]-->2-->[4]-->5--|\n", "^------------------|\n" ] } ], "source": [ "class SingleNode:\n", " def __init__(self, data):\n", " self.__data = data\n", " self.__nextEl = None\n", "\n", " def getData(self):\n", " return self.__data\n", " def setData(self, newdata):\n", " self.__data = newdata\n", "\n", " def setNext(self, node):\n", " self.__nextEl = node\n", " def getNext(self):\n", " return self.__nextEl\n", "\n", "\n", " def __str__(self):\n", " return str(self.__data)\n", "\n", " #for sorting\n", " def __lt__(self, other):\n", " return self.__data < other.__data\n", "\n", "class CircularList:\n", " def __init__(self):\n", " self.__head = None\n", " self.__tail = None\n", " self.__len = 0\n", "\n", " def __len__(self):\n", " return self.__len\n", "\n", " def append(self, node):\n", " if type(node) != SingleNode:\n", " raise TypeError(\"node is not of type SingleNode\")\n", " else:\n", " if self.__head == None:\n", " self.__head = node\n", " self.__tail = node\n", " else:\n", " node.setNext(self.__head)\n", " self.__tail.setNext(node)\n", " self.__tail = node\n", "\n", " self.__len += 1\n", "\n", " def extend(self, nodesList):\n", " for el in nodesList:\n", " self.append(el)\n", "\n", " def head(self):\n", " return self.__head\n", "\n", " def tail(self):\n", " return self.__tail\n", "\n", " def get(self, index):\n", " i = 0\n", " cur_el = self.__head\n", " if index < 0:\n", " #should someone input a very small number!\n", " while index < 0:\n", " index = self.__len + index\n", "\n", " while i < index:\n", " cur_el = cur_el.getNext()\n", " i += 1\n", " return cur_el\n", "\n", "\n", " def removeAt(self, index):\n", " i = 0\n", " cur_el = self.__head\n", " if index < 0:\n", " #should someone input a very small number!\n", " while index < 0:\n", " index = self.__len + index\n", "\n", "\n", " while i < index-1:\n", " cur_el = cur_el.getNext()\n", " i += 1\n", " prev = cur_el\n", " cur_el = prev.getNext()\n", " next_el = cur_el.getNext()\n", " prev.setNext(next_el)\n", " if cur_el == self.__tail:\n", " self.__tail = prev\n", " if cur_el == self.__head:\n", " self.__head = prev\n", "\n", " self.__len -= 1\n", "\n", " def removeEl(self, element):\n", " i = 0\n", " cur_el = self.__head\n", "\n", " while cur_el.getNext() != element and cur_el != self.__tail:\n", " cur_el = cur_el.getNext()\n", "\n", " if cur_el != self.__tail:\n", " prev = cur_el\n", " cur_el = prev.getNext()\n", " #cur_el is element now\n", " next_el = cur_el.getNext()\n", " prev.setNext(next_el)\n", " if cur_el == self.__tail:\n", " self.__tail = prev\n", " if cur_el == self.__head:\n", " self.__head = prev\n", "\n", " self.__len -= 1\n", "\n", " def __str__(self):\n", " outStr = \"\"\n", " cur_el = self.__head\n", " outStr = str(cur_el)\n", " while cur_el != self.__tail:\n", " cur_el = cur_el.getNext()\n", " outStr += \"-->\" + str(cur_el)\n", " L = len(outStr)\n", " outStr += \"--|\\n^\"\n", "\n", " i = 0\n", " while i < L+1:\n", " outStr = outStr + \"-\"\n", " i += 1\n", " outStr += \"|\"\n", "\n", " return outStr\n", "\n", "# Testing\n", "CL = CircularList()\n", "n = SingleNode([1])\n", "n1 = SingleNode(2)\n", "n2 = SingleNode([3])\n", "n3 = SingleNode([4])\n", "n4 = SingleNode(5)\n", "n5 = SingleNode([6])\n", "CL.append(n)\n", "CL.append(n1)\n", "CL.append(n2)\n", "CL.extend([n3,n4,n5])\n", "n = SingleNode(\"luca\")\n", "CL.append(n)\n", "print(CL)\n", "print(\"CL has length: {}\".format(len(CL)))\n", "print(\"Head:{}\\nTail:{}\".format(CL.head(),CL.tail()))\n", "print(\"{} is at position: {}\".format(CL.get(3),3))\n", "print(\"{} is at position: {}\".format(CL.get(-10),-10))\n", "print(\"{} is at position: {}\".format(CL.get(20),20))\n", "print(\"{} is at position: {}\".format(CL.get(0),0))\n", "CL.removeAt(2)\n", "CL.removeAt(5)\n", "print(CL)\n", "CL.removeEl(n5)\n", "print(CL)\n", "#n is not present!\n", "CL.removeEl(n)\n", "print(CL)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Download the complete source file: [CircularList.py](exercises/data_structures/CircularList.py)\n", "
\n", "\n", "## Stacks\n", "\n", "**Stacks** are data structures that provide access to a specific element, that is the last element inserted into the stack.\n", "\n", "The specific operations available for stacks are described in the abstract data type (from the lecture):\n", "\n", "![](images/stackADT.png)\n", "\n", "**Example:** Let's implement a stack class MyStack by using Python's list." ] }, { "cell_type": "code", "execution_count": 18, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Is it empty? True\n", "Initial length: 0\n", "Added [1,2,3]\n", "Added [4,5,6]\n", "Is it empty? False\n", "Added [1,4,5]\n", "On top of the stack: [1, 4, 5]\n", "Let's start removing elements...\n", "On top of the stack: [1, 4, 5]\n", "On top of the stack: [4,5,6]\n", "On top of the stack: [1,2,3]\n", "On top of the stack: None\n", "Added 123456\n", "On top of the stack: 123456\n", "On top of the stack: None\n" ] } ], "source": [ "class MyStack:\n", "\n", " def __init__(self):\n", " self.__data = list()\n", "\n", " def isEmpty(self):\n", " return len(self.__data) == 0\n", "\n", " def __len__(self):\n", " return len(self.__data)\n", "\n", " def push(self, element):\n", " \"\"\"adds an element on top of the stack\"\"\"\n", " self.__data.append(element)\n", "\n", " def pop(self):\n", " \"\"\"removes one element from the stack and returns it\"\"\"\n", " if len(self.__data) > 0:\n", " return self.__data.pop()\n", " else:\n", " return None\n", "\n", " def peek(self):\n", " if len(self.__data) > 0:\n", " return self.__data[-1]\n", " else:\n", " return None\n", "\n", "#Testing\n", "S = MyStack()\n", "print(\"Is it empty? {}\".format(S.isEmpty()))\n", "print(\"Initial length: {}\".format(len(S)))\n", "S.push(\"[1,2,3]\")\n", "print(\"Added [1,2,3]\")\n", "S.push(\"[4,5,6]\")\n", "print(\"Added [4,5,6]\")\n", "print(\"Is it empty? {}\".format(S.isEmpty()))\n", "S.push([1,4,5])\n", "print(\"Added [1,4,5]\")\n", "print(\"On top of the stack: {}\".format(S.peek()))\n", "print(\"Let's start removing elements...\")\n", "print(\"On top of the stack: {}\".format(S.pop()))\n", "print(\"On top of the stack: {}\".format(S.pop()))\n", "print(\"On top of the stack: {}\".format(S.pop()))\n", "print(\"On top of the stack: {}\".format(S.pop()))\n", "S.push(123456)\n", "print(\"Added 123456\")\n", "print(\"On top of the stack: {}\".format(S.pop()))\n", "print(\"On top of the stack: {}\".format(S.pop()))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Download the complete source file: [MyStack.py](exercises/data_structures/MyStack.py)\n", "\n", "### Exercise\n", "\n", "4. Stacks are great to evaluate postfix expressions. Some examples of postfix expressions are:\n", "\n", "```\n", "10 5 +\n", "```\n", "that encodes for ```10 + 5 = 15``` \n", "\n", "```\n", "10 5 + 7 *\n", "```\n", "that encodes for ```(10 + 5) * 7 = 105```\n", "\n", "Given a postfix expression it can be evaluated in the following way: \n", "\n", "1. start from the beginning of the string (better, convert it to a list by splitting the string by \" \"), remove elements from the list and insert elements in the stack unless they are operators. If they are operators, pop two elements and apply the operation, storing it in a variable;\n", "\n", "2. If the list is empty, the result is stored in the variable, otherwise go back to point 1.\n", "\n", "Assuming only integer numbers and the 4 standard binary operators +,-,/,\\*: write some python code that uses the stack class seen above ```MyStack``` and evaluates the following postfix expressions:\n", "\n", "```\n", "operations = [\"10 5 + 7 *\", \n", " \"1 2 3 4 5 6 7 8 + + + + + + +\", \n", " \"1 2 3 4 5 + - * /\",\n", " \"5 4 + 8 /\",\n", " \"3 10 2 - 5 * +\"]\n", "```\n", "\n", "
Show/Hide Solution\n" ] }, { "cell_type": "code", "execution_count": 19, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Operation: 10 5 + 7 *\n", "(10 + 5)\n", "(15 * 7)\n", "Result: 105\n", "Operation: 1 2 3 4 5 6 7 8 + + + + + + +\n", "(7 + 8)\n", "(6 + 15)\n", "(5 + 21)\n", "(4 + 26)\n", "(3 + 30)\n", "(2 + 33)\n", "(1 + 35)\n", "Result: 36\n", "Operation: 1 2 3 4 5 + - * /\n", "(4 + 5)\n", "(3 - 9)\n", "(2 * -6)\n", "(1 / -12)\n", "Result: -0.08333333333333333\n", "Operation: 5 4 + 8 /\n", "(5 + 4)\n", "(9 / 8)\n", "Result: 1.125\n", "Operation: 3 10 2 - 5 * +\n", "(10 - 2)\n", "(8 * 5)\n", "(3 + 40)\n", "Result: 43\n" ] } ], "source": [ "class MyStack:\n", " \n", " def __init__(self):\n", " self.__data = []\n", " \n", " def isEmpty(self):\n", " return len(self.__data) == 0\n", " \n", " def __len__(self):\n", " return len(self.__data)\n", " \n", " def push(self, element):\n", " \"\"\"adds an element on top of the stack\"\"\"\n", " self.__data.append(element)\n", " \n", " def pop(self):\n", " \"\"\"removes one element from the stack and returns it\"\"\"\n", " if len(self.__data) > 0:\n", " ret = self.__data[-1]\n", " del self.__data[-1]\n", " return ret\n", " else:\n", " return None\n", " \n", " def peek(self):\n", " if len(self.__data) > 0:\n", " return self.__data[-1]\n", " else:\n", " return None\n", " \n", "\n", "def evaluatePostfix(expr): \n", " S = MyStack()\n", " els = expr.split(\" \")\n", " res = 0\n", " infix = \"\"\n", " for i in range(len(els)):\n", " e = els[i]\n", " if e not in \"+-*/\":\n", " S.push(int(e))\n", " else:\n", " o2 = S.pop()\n", " o1 = S.pop()\n", " tmp = 0\n", " infix = \"(\" + str(o1) + \" \" + e +\" \" + str(o2) + \")\" \n", " print(infix)\n", " if e == \"+\":\n", " tmp = o1 + o2\n", " \n", " elif e == \"-\":\n", " tmp = o1 - o2\n", " \n", " elif e == \"/\":\n", " tmp = o1 / o2\n", " \n", " else:\n", " tmp = o1 * o2\n", " res = tmp\n", " \n", " if i != len(els):\n", " S.push(res)\n", " return res\n", "\n", "\n", "operations = [\"10 5 + 7 *\", \n", " \"1 2 3 4 5 6 7 8 + + + + + + +\", \n", " \"1 2 3 4 5 + - * /\",\n", " \"5 4 + 8 /\",\n", " \"3 10 2 - 5 * +\"]\n", "\n", "for op in operations:\n", " print(\"Operation: {}\".format(op))\n", " res = evaluatePostfix(op)\n", " print(\"Result: {}\".format(res))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Download the complete source file: [PostfixExpressions.py](exercises/data_structures/PostfixExpressions.py)\n", "
\n", "\n", "## Queues\n", "\n", "Queues, also called **FIFO queues: first in first out queues**, are linear dynamic data structures that add at the back of the queue and remove elements from the beginning.\n", "\n", "The specific operations available for queues are reported below (from the lecture):\n", "\n", "![](images/queueADT.png)\n", "\n", "**Example:** Let's implement a (slow!) queue class MyQueue by using Python's list." ] }, { "cell_type": "code", "execution_count": 20, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Size of Q: 3\n", "TOP is now: 1\n", "\n", "Removing el 1 from queue\n", "Removing el 2 from queue\n", "Removing el 3 from queue\n", "Removing el 4 from queue\n", "Removing el 5 from queue\n", "\n", "Queue has size: 400000\n", "\n", "Queue has size: 0\n", "\n", "Elapsed time: 21.83s\n" ] } ], "source": [ "class MyQueue:\n", "\n", " def __init__(self):\n", " self.__data = list()\n", "\n", " def isEmpty(self):\n", " return len(self.__data) == 0\n", "\n", " def __len__(self):\n", " return len(self.__data)\n", "\n", " def enqueue(self, element):\n", " self.__data.insert(0,element)\n", "\n", " def dequeue(self):\n", " el = None\n", " if len(self.__data) > 0:\n", " el = self.__data.pop()\n", " return el\n", "\n", " def top(self):\n", " if len(self.__data) > 0:\n", " return self.__data[-1]\n", "\n", "\n", "#Testing\n", "import time\n", "\n", "Q = MyQueue()\n", "Q.enqueue(1)\n", "Q.enqueue(2)\n", "Q.enqueue(3)\n", "print(\"Size of Q: {}\".format(len(Q)))\n", "Q.enqueue(4)\n", "Q.enqueue(5)\n", "print(\"TOP is now: {}\\n\".format(Q.top()))\n", "while not Q.isEmpty():\n", " el = Q.dequeue()\n", " print(\"Removing el {} from queue\".format(el))\n", "\n", "start_t = time.time()\n", "for i in range(400000):\n", " Q.enqueue(i)\n", "print(\"\\nQueue has size: {}\".format(len(Q)))\n", "#comment the next 3 lines and see what happens\n", "while not Q.isEmpty():\n", " el = Q.dequeue()\n", "print(\"\\nQueue has size: {}\".format(len(Q)))\n", "end_t = time.time()\n", "print(\"\\nElapsed time: {:.2f}s\".format(end_t - start_t))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Download the complete source file: [MyQueue.py](exercises/data_structures/MyQueue.py)\n", "\n", "Note that in the example above, enqueue adds at the beginning and dequeue removes from the end, this requires n shifts at each insertion, which is quite time costly!!!\n", "\n", "**Example:** Let's implement a queue class ```MyFasterQueue``` by using python's list but with a quicker __len__ operator (i.e. a counter that avoids looping all the time) and with a quicker **enqueue** operator." ] }, { "cell_type": "code", "execution_count": 21, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Size of Q: 3\n", "TOP is now: 5\n", "\n", "Removing el 1 from queue\n", "Removing el 2 from queue\n", "Removing el 3 from queue\n", "Removing el 4 from queue\n", "Removing el 5 from queue\n", "\n", "Queue has size: 400000\n", "\n", "Queue has size: 0\n", "\n", "Elapsed time: 15.47s\n" ] } ], "source": [ "class MyFasterQueue:\n", "\n", " def __init__(self):\n", " self.__data = list()\n", " self.__length = 0\n", "\n", " def isEmpty(self):\n", " return len(self.__data) == 0\n", "\n", " def __len__(self):\n", " return self.__length\n", "\n", " ## Add at the end not at the beginning\n", " def enqueue(self, element):\n", " self.__data.append(element)\n", " self.__length += 1\n", "\n", " def dequeue(self):\n", " el = None\n", " if len(self.__data) > 0:\n", " el = self.__data.pop(0)\n", " self.__length -= 1\n", " return el\n", "\n", " def top(self):\n", " if len(self.__data) > 0:\n", " return self.__data[-1]\n", "\n", "#Testing\n", "import time\n", "\n", "Q = MyFasterQueue()\n", "Q.enqueue(1)\n", "Q.enqueue(2)\n", "Q.enqueue(3)\n", "print(\"Size of Q: {}\".format(len(Q)))\n", "Q.enqueue(4)\n", "Q.enqueue(5)\n", "print(\"TOP is now: {}\\n\".format(Q.top()))\n", "while not Q.isEmpty():\n", " el = Q.dequeue()\n", " print(\"Removing el {} from queue\".format(el))\n", "\n", "start_t = time.time()\n", "for i in range(400000):\n", " Q.enqueue(i)\n", "print(\"\\nQueue has size: {}\".format(len(Q)))\n", "#comment the next 3 lines and see what happens\n", "while not Q.isEmpty():\n", " el = Q.dequeue()\n", "print(\"\\nQueue has size: {}\".format(len(Q)))\n", "end_t = time.time()\n", "print(\"\\nElapsed time: {:.2f}s\".format(end_t - start_t))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Download the complete source file: [MyFasterQueue.py](exercises/data_structures/MyFasterQueue.py)\n", "\n", "The problem with the previous code is that this time we will need to remove elements from the beginning of a list and this requires $n$ shifts with a cost $O(n)$, with $n$ number of elements in the list. Try commenting out the following lines:\n", "\n", "```python\n", "while not Q.isEmpty():\n", " el = Q.dequeue()\n", "```\n", "\n", "This would make the code above a lot faster (less than a second).\n", "\n", "The solution is to use Python's ```collections.dequeue```.\n", "\n", "## Collections\n", "\n", "Python provides several data structures in the ```collections``` module, like for example, **dequeues** etc. You can find more information at [https://docs.python.org/3.9/library/collections.html?highlight=collections#module-collections](https://docs.python.org/3.5/library/collections.html?highlight=collections#module-collections).\n", "\n", "### Exercise\n", "\n", "5. Implement a much faster queue by using the ```collections.dequeue``` collection.\n", "\n", "
Show/Hide Solution
\n" ] }, { "cell_type": "code", "execution_count": 22, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Q has 400000 elements\n", "Q has 0 elements\n", "\n", "Elapsed time: 0.10s\n" ] } ], "source": [ "from collections import deque\n", "import time\n", "\n", "Q = deque()\n", "start_t = time.time()\n", "for i in range(400000):\n", " #add to the right\n", " Q.append(i)\n", "print(\"Q has {} elements\".format(len(Q)))\n", "while len(Q) > 0:\n", " #remove from the left\n", " Q.popleft()\n", "print(\"Q has {} elements\".format(len(Q))) \n", "end_t = time.time()\n", "print(\"\\nElapsed time: {:.2f}s\".format(end_t - start_t))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n" ] } ], "metadata": { "celltoolbar": "Edit Metadata", "kernelspec": { "display_name": "3.10.14", "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.10.14" } }, "nbformat": 4, "nbformat_minor": 2 }