Book Image

Hands-On Data Structures and Algorithms with Python - Second Edition

By : Dr. Basant Agarwal, Benjamin Baka
Book Image

Hands-On Data Structures and Algorithms with Python - Second Edition

By: Dr. Basant Agarwal, Benjamin Baka

Overview of this book

Data structures allow you to store and organize data efficiently. They are critical to any problem, provide a complete solution, and act like reusable code. Hands-On Data Structures and Algorithms with Python teaches you the essential Python data structures and the most common algorithms for building easy and maintainable applications. This book helps you to understand the power of linked lists, double linked lists, and circular linked lists. You will learn to create complex data structures, such as graphs, stacks, and queues. As you make your way through the chapters, you will explore the application of binary searches and binary search trees, along with learning common techniques and structures used in tasks such as preprocessing, modeling, and transforming data. In the concluding chapters, you will get to grips with organizing your code in a manageable, consistent, and extendable way. You will also study how to bubble sort, selection sort, insertion sort, and merge sort algorithms in detail. By the end of the book, you will have learned how to build components that are easy to understand, debug, and use in different applications. You will get insights into Python implementation of all the important and relevant algorithms.
Table of Contents (16 chapters)

Generators and co-routines

We can create functions that do not just return one result but rather an entire sequence of results, by using the yield statement. These functions are called generators. Python contains generator functions, which are an easy way to create iterators and are especially useful as a replacement for unworkably long lists. A generator yields items rather than builds lists. For example, the following code shows why we might choose to use a generator, as opposed to creating a list:

#compares the running time of a list compared to a generator 
import time
#generator function creates an iterator of odd numbers between n and m
def oddGen(n,m):
while n<m:
yield n
n+=2

#builds a list of odd numbers between n and m
def oddLst(n,m):
lst=[]
while n<m:
lst.append(n)
n+=2
return lst

#the time it takes to perform sum on an iterator
t1=time.time()
sum(oddGen(1,1000000))
print("Time to sum an iterator: %f" % (time.time() - t1))
#the time it takes to build and sum a list
t1=time.time()
sum(oddLst(1,1000000))
print("Time to build and sum a list: %f" % (time.time() - t1))

This prints out the following:

As we can see, building a list to do this calculation takes significantly longer. The performance improvement as a result of using generators is because the values are generated on demand, rather than saved as a list in memory. A calculation can begin before all the elements have been generated and elements are generated only when they are needed.

In the preceding example, the sum method loads each number into memory when it is needed for the calculation. This is achieved by the generator object repeatedly calling the __next__ () special method. Generators never return a value other than None.

Typically, generator objects are used in for loops. For example, we can make use of the oddLst generator function created in the preceding code to print out odd integers between 1 and 10:

for i in oddLst (1,10):print(i)

We can also create a generator expression, which, apart from replacing square brackets with parentheses, uses the same syntax and carries out the same operation as list comprehensions. Generator expressions, however, do not create a list; they create a generator object. This object does not create the data, but rather creates that data on demand. This means that generator objects do not support sequence methods such as append() and insert().

You can, however, change a generator into a list using the list() function:

Classes and object programming

Classes are a way to create new kinds of objects and they are central to object-oriented programming. A class defines a set of attributes that are shared across instances of that class. Typically, classes are sets of functions, variables, and properties.

The object-oriented paradigm is compelling because it gives us a concrete way to think about and represent the core functionality of our programs. By organizing our programs around objects and data rather than actions and logic, we have a robust and flexible way to build complex applications. The actions and logic are still present, of course, but by embodying them in objects, we have a way to encapsulate functionality, allowing objects to change in very specific ways. This makes our code less error-prone, easier to extend and maintain, and able to model real-world objects.

Classes are created in Python using the class statement. This defines a set of shared attributes associated with a collection of class instances. A class usually consists of a number of methods, class variables, and computed properties. It is important to understand that defining a class does not, by itself, create any instances of that class. To create an instance, a variable must be assigned to a class. The class body consists of a series of statements that execute during the class definition. The functions defined inside a class are called instance methods. They apply some operations to the class instance by passing an instance of that class as the first argument. This argument is called self by convention, but it can be any legal identifier. Here is a simple example:

class Employee(object):
numEmployee=0
def init (self,name,rate):
self.owed=0
self.name=name
self.rate=rate
Employee.numEmployee += 1

def del (self):
Employee.numEmployee-=1

def hours(self,numHours):
self.owed += numHours*self.rate
return ("%.2f hours worked" % numHours)

def pay(self):
self.owed=0
return("payed %s " % self.name)

Class variables, such as numEmployee, share values among all the instances of the class. In this example, numEmployee is used to count the number of employee instances. Note that the Employee class implements the __init__ and __del__ special methods, which we will discuss in the next section.

We can create instances of the Employee objects, run methods, and return class and instance variables by doing the following:

Special methods

We can use the dir(object) function to get a list of attributes of a particular object. The methods that begin and end with two underscores are called special methods. Apart from the following exception, special methods are generally called by the Python interpreter rather than the programmer; for example, when we use the + operator, we are actually invoking a to _add_ () call. For example, rather than using my_object._len_ (), we can use len(my_object); using len() on a string object is actually much faster, because it returns the value representing the object's size in memory, rather than making a call to the object's _len_ method.

The only special method we actually call in our programs, as common practice, is the _init_ method, to invoke the initializer of the superclass in our own class definitions. It is strongly advised not to use the double underscore syntax for your own objects because of potential current or future conflicts with Python's own special methods.

We may, however, want to implement special methods in custom objects, to give them some of the behavior of built-in types. In the following code, we create a class that implements the _repr_ method. This method creates a string representation of our object that is useful for inspection purposes:

class my_class():
def __init__(self,greet):
self.greet=greet
def __repr__(self):
return 'a custom object (%r) ' % (self.greet)

When we create an instance of this object and inspect it, we can see we get our customized string representation. Notice the use of the %r format placeholder to return the standard representation of the object. This is useful and best practice because, in this case, it shows us that the greet object is a string indicated by the quotation marks:

Inheritance

Inheritance is one of the most powerful features of object-oriented programming languages. It allows us to inherit the functionality from other classes. It is possible to create a new class that modifies the behavior of an existing class through inheritance. Inheritance means that if an object of one class is created by inheriting another class, then the object would have all the functionality, methods, and variables of both the classes; that is, the parent class and new class. The existing class from which we inherit the functionalities is called the parent/base class, and the new class is called the derived/child class.

Inheritance can be explained with a very simple example—we create an employee class with attributes such as name of employee and rate at which he is going to be paid hourly. We can now create a new specialEmployee class inheriting all the attributes from the employee class.

Inheritance in Python is done by passing the inherited class as an argument in the class definition. It is often used to modify the behavior of existing methods.

An instance of the specialEmployee class is identical to an Employee instance, except for the changed hours() method. For example, in the following code we create a new specialEmployee class that inherits all the functionalities of the Employee class, and also change the hours() method:

class specialEmployee(Employee):
def hours(self,numHours):
self.owed += numHours*self.rate*2
return("%.2f hours worked" % numHours)

For a subclass to define new class variables, it needs to define an __init__() method, as follows:

class specialEmployee(Employee):
def __init__(self,name,rate,bonus):
Employee.__init__(self,name,rate) #calls the base classes
self.bonus=bonus

def hours(self,numHours):
self.owed += numHours*self.rate+self.bonus
return("%.2f hours worked" % numHours)

Notice that the methods of the base class are not automatically invoked and it is necessary for the derived class to call them. We can test for the class membership using the built-in isinstance(obj1,obj2) function. This returns True if obj1 belongs to the class of obj2 or any class derived from obj2. Let's consider the following example to understand this, where obj1 and obj2 are the objects of the Employee and specialEmployee classes respectively:

#Example issubclass() to check whether a class is a subclass of another class  
#Example isinstance() to check if an object belongs to a class or not

print(issubclass(specialEmployee, Employee))
print(issubclass(Employee, specialEmployee))

d = specialEmployee("packt", 20, 100)
b = Employee("packt", 20)
print(isinstance(b, specialEmployee))
print(isinstance(b, Employee))

# the output prints
True
False
False
True

Generally, all the methods operate on the instance of a class defined within a class. However, it is not a requirement. There are two types of methods—static methods and class methods. A static method is quite similar to a class method, which is mainly bound to the class, and not bound with the object of the class. It is defined within a class and does not require an instance of a class to execute. It does not perform any operations on the instance and it is defined using the @staticmethod class decorator. Static methods cannot access the attributes of an instance, so their most common usage is as a convenience to group utility functions together.

A class method operates on the class itself and does not work with the instances. A class method works in the same way that class variables are associated with the classes rather than instances of that class. Class methods are defined using the @classmethod decorator and are distinguished from instance methods in the class. It is passed as the first argument, and this is named cls by convention. The exponentialB class inherits from the exponentialA class and changes the base class variable to 4. We can also run the parent class's exp() method as follows:

class exponentialA(object):
base=3
@classmethod
def exp(cls,x):
return(cls.base**x)

@staticmethod
def addition(x, y):
return (x+y)

class exponentialB(exponentialA):
base=4

a = exponentialA()
b= a.exp(3)
print("the value: 3 to the power 3 is", b)
print('The sum is:', exponentialA.addition(15, 10))
print(exponentialB.exp(3))

#prints the following output
the value: 3 to the power 3 is 27
The sum is: 25
64

The difference between a static method and a class method is that a static method doesn't know anything about the class, it only deals with the parameters, whereas the class method works only with the class, and its parameter is always the class itself.

There are several reasons why class methods may be useful. For example, because a subclass inherits all the same features of its parent, there is the potential for it to break inherited methods. Using class methods is a way to define exactly what methods are run.

Data encapsulation and properties

Unless otherwise specified, all attributes and methods are accessible without restriction. This also means that everything defined in a base class is accessible from a derived class. This may cause problems when we are building object-oriented applications where we may want to hide the internal implementation of an object. This can lead to namespace conflicts between objects defined in derived classes with the base class. To prevent this, the methods we define private attributes with have a double underscore, such as __privateMethod(). These method names are automatically changed to __Classname_privateMethod() to prevent name conflicts with methods defined in base classes. Be aware that this does not strictly hide private attributes, rather it just provides a mechanism for preventing name conflicts.

It is recommended to use private attributes when using a class property to define mutable attributes. A property is a kind of attribute that rather than returning a stored value computes its value when called. For example, we could redefine the exp() property with the following:

class Bexp(Aexp):
base=3
def exp(self):
return(x**cls.base)