Skip to main content

A Python Tale of Iterators and Generators

Hello my friends in this Entry we are going to talk about a really cool topic (Well that's what I think) that is Iterators and Generators with the Python Programming Language, and for explaining each of this I'm going to build a class representing a Linked List data structure and how you can use Python Built-in Functions to iterate, create iterators or generators on custom classes.



Linked List


Accordinly to the Wikipedia, “a linked list is a linear collection of data elements, in which linear order is not given by their physical placement in memory. Each pointing to the next node by means of a pointer. It is a data structure consisting of a group of nodes which together represent a sequence”.

And here I give you a class implementation of the Linked List already built with some basics helper methods, most of this code I took it from the blog article of Adnan Alam, he explains really well this class, though I made some changes from the original code.
## linkedlist.py
 
class Node:
    
    def __init__(self,data=None,next_node=None):
        self.data = data
        self.next_node = next_node
    
    def get_data(self):
        return self.data
 
    def set_data(self, data):
        self.data = data
    
    def get_next(self):
        return self.next_node
    
    def set_next(self,new_node):
        self.next_node = new_node
 
    def __str__(self):
 
        return self.data.__str__()
 
class LinkedList:
    
    def __init__(self, front=None):
        self.front = front
 
    def insert_front(self, data):
        new_node = Node(data)
        new_node.set_next(self.front)
        self.front = new_node
 
    def insert_rear(self, data):
 
        new_node = Node(data)
        if self.front is None:
            self.front = new_node
        else:
            current = self.front
            while current.get_next():
                current = current.get_next()
            current.set_next(new_node)
 
    def delete(self, data):
 
        current = self.front
        prev = None
        while current:
            if current.get_data() == data:
                if prev:
                    prev.set_next(current.get_next())
                else:
                    self.front = current.get_next()
                break
            else:
                prev = current
                current = current.get_next()
 
    def search(self, data):
        current = self.front
        while current:
            if current.get_data() == data:
                return True
            else:
                current = current.get_next()
        return False
 
    def __len__(self):
        current = self.front
        count = 0
        while current:
            count +=1
            current = current.get_next()
        return count
 
    def __str__(self):
        current = self.front
        temp = []
        while current:
            temp.append(current.get_data())
            current = current.get_next()
 
        return temp.__str__()

Here we have two classes, a class for Node and a class for LinkedList, if you are not used to Object Oriented Programming in Python take a look at my two earlier entries in this topic.
Now as mentioned it before, this data structure could represent a sequence, so this could mean that we can index or iterate through it, well not yet, we need to provide to this class the methods that will allow us to perform these operations.

Set and Get Item

In our own data structures sometimes we want to have the capability to perform indexing access to the sequences, in same way we get and set elements in a Python List, we can achieved this by implementing __getitem__ and __setitem__ methods to our class, Python List are really versatile in this kind of operations, you can even slice using square  brackets, but we are going to go that far, we are going to implement simple index access capable of doing even negatives, some validations must be done like only integers and values less or equal than the size of the sequence, let's build these methods.
    def __getitem__(self, key):
 
        if type(key) != int:
 
            raise TypeError
 
        size = self.__len__()
 
        if key  < 0 and abs(key) > size:
 
            raise IndexError
 
        if key  < 0:
 
            key = size + key
 
        if key >  size - 1:
 
            raise IndexError
 
        current = self.front
        counter = 0
        while current:
            if counter == key:
                return current
            else:
                current = current.get_next()
                counter += 1
 
    def __setitem__(self, key, data):
 
        if type(key) != int:
 
            raise TypeError
 
        size = self.__len__()
 
        if key  < 0 and abs(key) > size:
 
            raise IndexError
 
        if key  < 0:
 
            key = size + key
 
        if key >  size - 1:
 
            raise IndexError
 
        current = self.front
        counter = 0
        while current:
            if counter == key:
                current.set_data = data
            else:
                current = current.get_next()
                counter += 1

Now let's make some tests on this
>>> item1 = 2020
>>> item2 = 4040
>>> item3 = 6060
>>> item4 = 8080
>>> linked = LinkedList()
>>> linked.insert_front(item1)
>>> linked.insert_front(item2)
>>> linked.insert_front(item3)
>>> linked.insert_front(item4)
>>> print linked
[8080, 6060, 4040, 2020]
>>> linked[1]
6060
>>> linked[2]
4040
>>> linked[-1]
2020
>>> linked[2] = 3030
>>> print linked
[8080, 6060, 3030, 2020]

Pretty cool right? Now If we want to iterate through this linked list using a for loop, is not possible yet and that is because, so far this class is not an iterator.

Iterators

we turn these objects into iterators if we build  the __iter__ and next methods to our LinkedList class, these methods are used by the for loop for  iteration, and the code is as follow.
    def __iter__(self):
        self.n = 0
        return self
 
    def next(self):
        if self.n < self.__len__():
            result = self.__getitem__(self.n)
            self.n += 1
            return result
        else:
            raise StopIteration

As you can see if there is no more elements to iterate we need to raise a stop iteration error, this will indicate the for loop to stop, let's try this now.
>>> item1 = 101
>>> item2 = 102
>>> item3 = 103
>>> item4 = 104
>>> linked = LinkedList()
>>> linked.insert_front(item1)
>>> linked.insert_front(item2)
>>> linked.insert_front(item3)
>>> linked.insert_front(item4)
>>> print linked
[104, 103, 102, 101]
>>> for i in linked:
         print i
 
         
104
103
102
101

Something to keep in mind is that for Python 3, next for classes is used with double underscore __next__; now that we have cover iterators let's talk about generators.

Generators

Generators are a kind of iterators, well they behave like iterators, but they are implemented as functions and instead of returning a value they yield a value, the main advantage of this is that they do not allocate all the values in memory rather calculated on the fly, that is why is called generators, you won't find too much differences in terms of performance until you find you self in need of processing really large data sets.
A really simple generator is the calculation of Fibonacci numbers; here I show you a simple code for this.
def fibonacci(n):
    """
    Yields the first n elements of the Fibonnaci
    """
    a = b = 1
    for i in range(n):
        yield a
        a, b = b, a + b

Now let's test this
>>> gen1 = fibonacci(4)
>>> gen1.next()
1
>>> gen1.next()
1
>>> gen1.next()
2
>>> gen1.next()
3
>>> gen1.next()
 
Traceback (most recent call last):
  File "<pyshell#13>", line 1, in <module>
    gen1.next()
StopIteration
>>> for i in fibonacci(10):
         print i
 
         
1
1
2
3
5
8
13
21
34
55

Something to point out here is that generators as well iterators can only be iterated with next once until they reach the end, and they can be easily used with for loops, now let's say we want to convert our Linked List into a generator; we can build a generator method and yield each value at a time.
    def gen(self, n=None):
 
        if n == None:
 
            n = self.__len__()
 
        for i in range(n):
 
            yield self.__getitem__(i)

And finally let's test this
>>> item1 = 2020
>>> item2 = 4040
>>> item3 = 6060
>>> item4 = 8080
>>> linked = LinkedList()
>>> linked.insert_front(item1)
>>> linked.insert_front(item2)
>>> linked.insert_front(item3)
>>> linked.insert_front(item4)
>>> print linked
[8080, 6060, 4040, 2020]
for i in linked.gen():
         print i
 
         
8080
6060
4040
2020

Well remember that this has meaning if there are too much elements in the LinkedList, so technics to process this information is required in order to improve execution performance.
We have come to the end of this entry; well I hope you have found this entry helpful to you. So thanks for coming by my new entry and I hope you have enjoyed this as much as I enjoyed writing it, stop by the comments if you want to discuss about this, share in your social media and subscribe. Cheers my friends.

Popular posts from this blog

Multithreading web scraping with Python

Hello my friends today in this entry we are going to talk about a very trendy topic, web scraping and how to do it with our beautiful Python programming language, so open your Python Idle and get set because in this Tutorial Entry we are going to code once again.

Python Free Books

Hello my friends in an earlier post I talked about some dive deep Python Books that you could purchase to start learning Python, you can check that entry in this link, and now I have decided to write this entry to give you a list of online and free Python books.


These books are supposed to be hosted documentation; they are written in restructured text (reStructuredText) and translated into beautiful HTML or PDF with a tool called Sphinx. This documentation format is supposed to be used for writing your own packages and modules documentation, but experts also use them to write practical books and tutorials of different languages and they can be uploaded and hosted for free in different online platforms, one of them is read the docs website.

Singleton - Design Patterns in Python

Hello my friends, here in this quickly entry we are going to talk about the most basic but very useful Design Pattern and that is the Singleton, but first let's discuss as always a little about theory.
Design PatternsThis is the next step in the programing learning curve, after Object Oriented Programming there is a list of topics that you could learn next, I strongly recommend Python Design Patterns. Accordingly to the Wikipedia, “a software design pattern is a general reusable solution to a commonly occurring problem within a given context in software design”, in other words is the same code to the same kind of problems; in general we tend to find the same kind of problems when we are designing our software, and we tend to solve this problems with the same solution, in time and each time this solution is improved and finally is considered a standard or a pattern in software design, so it becomes a design pattern.