Algorithms

Algorithms Overview

• Algorithm Analysis
• Algorithm Design
• Big O Notation
• Searching Algorithms
• Sorting Algorithms

Overview (Cont.)

• List Pointer Structures
• Linked Lists
• Stacks
• Queue
• Trees

Objectives

Algorithm Analysis

• A Priori Analysis
  • This is a theoretical analysis of an algorithm. Efficiency of an algorithm is measured by assuming that all other factors, for example, processor speed, are constant and have no effect on the implementation.​
• A Posterior Analysis
  • This is an empirical analysis of an algorithm. The selected algorithm is implemented using programming language. This is then executed on target computer machine. In this analysis, actual statistics like running time and space required, are collected.

Algorithm Complexity

• Time Factor
  • Time is measured by counting the number of key operations such as comparisons in the sorting algorithm.
• Space Factor
  • Space is measured by counting the maximum memory space required by the algorithm.

Algorithm Design

From the data structure point of view, the following are some important categories of algorithms −

• Search - Algorithm to search an item in a data structure.
• Sort - Algorithm to sort items in a certain order.
• Insert - Algorithm to insert item in a data structure.
• Update - Algorithm to update an existing item in a data structure.
• Delete - Algorithm to delete an existing item from a data structure.

Characteristics of an Algorithm

Not all procedures can be called an algorithm. An algorithm should have the following characteristics −

• Unambiguous - Algorithm should be clear and unambiguous. Each of its steps (or phases), and their inputs/outputs should be clear and must lead to only one meaning.
• Input - An algorithm should have 0 or more well-defined inputs.
• Output - An algorithm should have 1 or more well-defined outputs, and should match the desired output.
• Finiteness - Algorithms must terminate after a finite number of steps.
• Feasibility - Should be feasible with the available resources.
• Independent - An algorithm should have step-by-step directions, which should be independent of any programming code.

How to Write an Algorithm?

There are no well-defined standards for writing algorithms. Rather, it is problem and resource dependent. Algorithms are never written to support a particular programming code.

As we know that all programming languages share basic code constructs like loops (do, for, while), flow-control (if-else), etc. These common constructs can be used to write an algorithm.

We write algorithms in a step-by-step manner, but it is not always the case. Algorithm writing is a process and is executed after the problem domain is well-defined. That is, we should know the problem domain, for which we are designing a solution.

Example

Problem − Design an algorithm to add two numbers and display the result.

• Step 1 - START ADD
• Step 2 - get values of a & b
• Step 3 - c ← a + b
• Step 4 - display c
• Step 5 - STOP

Searching Algorithms

Searching is integral to life - We search for things all the time; or at least I do! As often is the case, just as it is in life, so it is in computer science and searching plays a very important role when it comes to working with data. A search algorithm is any algorithm which solves the Search problem, namely, to retrieve information stored within some data structure, or calculated in the search space of a problem domain. Examples of such structures include but are not limited to a Linked List, an Array data structure, or a Search tree. The appropriate search algorithm often depends on the data structure being searched, but also on any a priori knowledge about the data. Searching also encompasses algorithms that query the data structure, such as the SQL SELECT command.

Linear Search Algorithm

The Linear Search Algorithm is a simple algorithm, where each item in the list (starting from the first item) is investigated until the required item is found, or the end of the list is reached.

The Linear Search algorithm is implemented in Python as follows:

							
								def linearSearch(item, my_list):
									found = False
									position = 0
									while position < len(my_list) and not found:
										if my_list[position] == item:
											found = True
										position = position + 1
									return found
							
						

Let's test the code. Enter the following statement at the end of the Python script above:

							
								bag = ['book', 'pencil', 'pen', 'note book', 'sharpener', 'eraser']
								item = input('What item do you want to check for in the bag?')
								itemFound = linearSearch(item, bag)
								if itemFound:    
									print ('Yes, the item is in the bag')
								else:
									print ('Oops, your item seems not to be in the bag')
							
						

Binary Search

Binary Search: Search a sorted array by repeatedly dividing the search interval in half. Begin with an interval covering the whole array. If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half. Otherwise narrow it to the upper half. Repeatedly check until the value is found or the interval is empty.

The idea of binary search is to use the information that the array is sorted and reduce the time complexity to O(Log n).

Binary Search

We basically ignore half of the elements just after one comparison.

• Compare x with the middle element.
• If x matches with middle element, we return the mid index.
• Else If x is greater than the mid element, then x can only lie in right half subarray after the mid element. So we recur for right half.
• Else (x is smaller) recur for the left half.

Sorting Algorithms

Sorting refers to arranging data in a particular format. Sorting algorithm specifies the way to arrange data in a particular order. Most common orders are in numerical or lexicographical order.

The importance of sorting lies in the fact that data searching can be optimized to a very high level, if data is stored in a sorted manner. Sorting is also used to represent data in more readable formats. Below we see five such implementations of sorting in python.

• Bubble Sort
• Merge Sort
• Insertion Sort
• Shell Sort
• Selection Sort

Bubble Sort

Bubble sort is a comparison-based algorithm in which each pair of adjacent elements is compared and the elements are swapped if they are not in order.

Swap the elements to arrange in order

							
								def bubblesort(list):
									for iter_num in range(len(list) -1, 0, -1):
										for idx in range(iter_num):
											if list[idx] > list[idx+1]:
												temp = list[idx]
												list[idx] = list[idx+1]
												list[idx+1] = temp
								list =[19,2,31,45,6,11,121,27]
								bubblesort(list)
								print(list)
							
						

When the above code is executed, it produces the following result:

[2,6,11,19,27,31,45,121]

Merge Sort

Merge sort divides the array into equal halves and then combines them in a sorted manner

							
								def merge_sort(unsorted_list):
									if len(unsorted_list)<=1:
										return unsorted_list
							
						

Find the middle point and divide it

							
								middle = len(unsorted_list)// 2
								left_list = unsorted_list[:middle]
								right_list = unsorted_list[middle:]
								left_list = merge_sort(left_list)
								right_list = merge_sort(right_list)
								return list(merge(left_list, right_list))
							
						

Merge the sorted halves

							
								def merge(left_half,right_half):
									res =[]
									while len(left_half)!= 0 and len(right_half)!= 0:
										if left_half[0]< right_half[0]:
											res.append(left_half[0])
											left_half.remove(left_half[0])
										else:
											res.append(right_half[0])
											right_half.remove(right_half[0])
									if len(left_half) == 0:
										res = res + right_half
									else:
										res = res + left_half
									return res
								unsorted_list =[64,34,25,12,22,11,90]
								print(merge_sort(unsorted_list))
							
						

When the above code is executed, it produces the following result:

[11,12,22,25,34,64,90]

Insertion Sort

Insertion sort involves finding the right place for a given element in a sorted list. So in beginning we compare the first two elements and sort them by comparing them. Then we pick the third element and find its proper position among the previous two sorted elements. This way we gradually go on adding more elements to the already sorted list by putting them in their proper position.

							
								def insertion_sort(InputList):
									for i in range(1, len(InputList)):
										j = i-1
										nxt_element =InputList[i]
								# Compare the current element with next one
										while(InputList[j]> nxt_element)and(j> = 0):
											InputList[j+1]  =InputList[j]
											j = j-1
										InputList[j+1] = nxt_element
								list = [19,2,31,45,30,11,121,27]
								insertion_sort(list)
								print(list)
							
						

When the above code is executed, it produces the following result:

[2,11,19,27,30,31,45,121]

Shell Sort

Shell Sort involves sorting elements which are away from ech other. We sort a large sublist of a given list and go on reducing the size of the list until all elements are sorted. The below program finds the gap by equating it to half of the length of the list size and then starts sorting all elements in it. Then we keep resetting the gap until the entire list is sorted.

							
								def shellSort(input_list):
									gap = len(input_list)// 2
									while gap >0:
										for i in range(gap, len(input_list)):
											temp = input_list[i]
											j = i
								# Sort the sub list for this gap
											while j > = gap and input_list[j - gap]> temp:
												input_list[j] = input_list[j - gap]
												j = j-gap
											input_list[j] = temp
								# Reduce the gap for the next element
										gap = gap//2
								list =[19,2,31,45,30,11,121,27]
								shellSort(list)
								print(list)
							
						

When the above code is executed, it produces the following result:

[2,11,19,27,30,31,45,121]

Selection Sort

In selection sort we start by finding the minimum value in a given list and move it to a sorted list. Then we repeat the process for each of the remaining elements in the unsorted list. The next element entering the sorted list is compared with the existing elements and placed at its correct position. So at the end all the elements from the unsorted list are sorted.

							
								def selection_sort(input_list):
									for idx in range(len(input_list)):
										min_idx = idx
										for j in range( idx +1, len(input_list)):
											if input_list[min_idx]> input_list[j]:
												min_idx = j
							
						

Swap the minimum value with the compared value

							
										input_list[idx], input_list[min_idx]= input_list[min_idx], input_list[idx]

								l =[19,2,31,45,30,11,121,27]
								selection_sort(l)
								print(l)
							
						

When the above code is executed, it produces the following result:

[2,11,19,27,30,31,45,121]

Lists and Pointer Structures

At this point in training you will have already seen lists in Python. They are convenient and powerful. Normally, any time you need to store something in a list, you use python's built-in list implementation. In this chapter, however, we are more interested in understanding how lists work. So we are going to study list internals. As you will notice, there are different types of lists.

Python's list implementation is designed to be powerful and to encompass several different use cases. We are going to be a bit more strict in our definition of what a list is. The concept of a node is very important to lists. We shall discuss them in this chapter, but this concept will, in different forms, come back throughout the rest of the book. In this lesson, we are going to deal quite a bit with pointers. So it may be useful to remind ourselves what these are.

Understanding Pointers in Python

To begin with, imagine that you have a house that you want to sell. Lacking time, you contact an agent to find interested buyers. So you pick up your house and take it over to the agent, who will in turn carry the house to anybody who may want to buy it. Ludicrous, you say? Now imagine that you have a few Python functions that work with images. So you pass high-resolution image data between your functions.

Of course, you don't carry your house around. What you would do is write the address of the house down on a piece of scrap paper and hand it over to the agent. The house remains where it is, but the note containing the directions to the house is passed around. You might even write it down on several pieces of paper. Each one is small enough to fit in your wallet, but they all point to the same house.

As it turns out, things are not very different in Python land. Those large image files remain in one single place in memory. What you do is create variables that hold the locations of those images in memory. These variables are small and can easily be passed around between different functions.

That is the big benefit of pointers: they allow you to point to a potentially large segment of memory with just a simple memory address.

Support for pointers exists in your computer's hardware, where it is known as indirect addressing.

In Python, you don't manipulate pointers directly, unlike in some other languages, such as C or Pascal. This has led some people to think that pointers aren't used in Python. Nothing could be further from the truth. Consider this assignment in the Python interactive shell:

							
								>>> s = set()
							
						

We would normally say that s is a variable of the type set. That is, s is a set. This is not strictly true, however. The variable s is rather a reference (a "safe" pointer) to a set. The set constructor creates a set somewhere in memory and returns the memory location where that set starts. This is what gets stored in s.

Python hides this complexity from us. We can safely assume that s is a set and that everything works fine.

Arrays

An array is a sequential list of data. Being sequential means that each element is stored right after the previous one in memory. If your array is really big and you are low on memory, it could be impossible to find large enough storage to fit your entire array. This will lead to problems.

Of course, the flip side of the coin is that arrays are very fast. Since each element follows from the previous one in memory, there is no need to jump around between different memory locations. This can be a very important point to take into consideration when choosing between a list and an array in your own real-world applications.

Pointer Structures

Contrary to arrays, pointer structures are lists of items that can be spread out in memory. This is because each item contains one or more links to other items in the structure. What type of links these are dependent on the type of structure we have. If we are dealing with linked lists, then we will have links to the next (and possibly previous) items in the structure. In the case of a tree, we have parent-child links as well as sibling links.

In a tile-based game where the game map is built up of hexes, each node will have links to up to six adjacent map cells. There are several benefits with pointer structures. First of all, they don't require sequential storage space. Second, they can start small and grow arbitrarily as you add more nodes to the structure.

However, this comes at a cost. If you have a list of integers, each node is going to take up the space of an integer, as well as an additional integer for storing the pointer to the next node.

Arrays

An array is a sequential list of data. Being sequential means that each element is stored right after the previous one in memory. If your array is really big and you are low on memory, it could be impossible to find large enough storage to fit your entire array. This will lead to problems.

Of course, the flip side of the coin is that arrays are very fast. Since each element follows from the previous one in memory, there is no need to jump around between different memory locations. This can be a very important point to take into consideration when choosing between a list and an array in your own real-world applications.

Singly Linked Lists

Nodes

Before we get into the details of what singly lists are, we must learn what nodes are. This is because nodes are the building blocks of a linked list. A node consists of two parts:

Data part - contains the data

Address part - this is pointer that points to location of the next node In a singly linked list, each node’s address part contains the information about the location of the next node. This forms a series of chain or links. The first node of the linked list is kept track by the head pointer. The last node points to None.

Let us see the following diagram to understand this better:

Note: In the above figure, the last element 1 points to None. Even though these nodes are drawn contiguous to each other, in reality, they may or may not be in contiguous memory locations.

Tip: Always try to draw these data structures to get a clear understanding.

Creating a Singly Linked List

How to create a Singly Linked List? Creating classes Firstly, you must create a node in order to create a singly linked list. To do this, we create a class Node with data and nextNode attributes. As discussed earlier, the data attribute will contain the data and the nextNode will simply point to the next node in the linked list. We will make the default value of nextNode to be None. You can use getter and setter methods to do this.

Now that the Node class is created, it is time to create the LinkedList class. This has only one attribute, head. By default, this will point to None. If the head points to None it means that the linked list is empty. To keep track of the number of nodes in the linked list, we can add a size attribute to the LinkedList class and default it to 0.

Inserting a Node This is a method of the LinkedList class. Remember, to make the coding simple and efficient we will always add the new node to the beginning of the linked list. In other words, the head will always point to the most recently added node. If we add the new node to the end of the list, we need to do the extra work of finding the end of the list and then adding it. This is a wasteful operation.

However, if you maintain another pointer, let’s call it the tail pointer such that it points to the last node, this can be done. You can insert a new node anywhere in the linked list. We have discussed the former approach i.e insertion at the beginning of the linked list.

Let’s say we need to add 7 to a linked list, we need to do the following steps:

Create a node object with 7 as the data and the next node pointing to head node Point the head pointer to this new node. Finally, increment the size attribute by 1. It is always a good practice to return True if insertion was successful. This way the user knows what is happening.

Print Nodes This is a method of the LinkedList class. To print the data present in all the nodes of the linked list, we need to traverse one node at a time and print each node’s data part.

Writing a Singly Linked List

							
								Class Node:
									def _init_(self, data, nextNode = None):
										self.data = data
										self.nextNode = nextNode
										
									def getData(self):
										return self.data
										
									def getNextNode(self):
										return self.nextNode
										
									def setNextNode(self, val):
										self.nextNode = val

								class LinkedList:
									def _init_(self, head = None):
										self.head = head
										self.size = 0
										
									def getSize(self):
										return self.size
										
									def addNode(self, data):
										newNode = Node(data, self.head)
										self.head = newNode
										self.size+=1
										return True
										
									def printNode(self):
										curr = self.head
										while curr:
											print(curr.data)
											curr = curr.getNextNode()

								myList = LinkedList()
								print("Inserting")
								print(myList.addNode(5))
								print(myList.addNode(15))
								print(myList.addNode(25))
								print("Printing")
								myList.printNode()
								print("Size")
								print(myList.getSize)
							
						

What are the advantages and disadvantages of Singly Linked Lists?

• Advantages
  • It’s a dynamic data structure in which insertion and deletion are simple as we don’t need to shift the elements. Just updating the next pointer will do the job for us.
  • Stack and Queue data structures can be easily implemented using linked lists.

• Disadvantages
  • Additional memory is used up by the next pointers.
  • Random access is not possible. You must traverse the linked list from the beginning to get to a particular node.

Doubly Linked List

Doubly Linked List is a variation of the linked list. The linked list is a linear data structure which can be described as the collection of nodes. Nodes are connected through pointers. Each node contains two fields: data and pointer to the next field. The first node of the linked list is called the head, and the last node of the list is called the tail of the list.

One of the limitations of the singly linked list is that it can be traversed in only one direction that is forward. The doubly linked list has overcome this limitation by providing an additional pointer that points to the previous node. With the help of the previous pointer, the doubly linked list can be traversed in a backward direction thus making insertion and deletion operation easier to perform. So, a typical node in the doubly linked list consists of three fields:

Data represents the data value stored in the node. Previous represents a pointer that points to the previous node. Next represents a pointer that points to the next node in the list.

The above picture represents a doubly linked list in which each node has two pointers to point to previous and next node respectively. Here, node 1 represents the head of the list. The previous pointer of the head node will always point to NULL. Next pointer of node one will point to node 2. Node 5 represents the tail of the list whose previous pointer will point to node 4, and the next will point to NULL.

Creating a Doubly Linked List

Define a Node class which represents a node in the list. It will have three properties:

• data
• previous - which will point to the previous node
• next - which will point to the next node.

Define another class for creating a doubly linked list, and it has two nodes: head and tail.

Initially, head and tail will point to null.

It first checks whether the head is null, then it will insert the node as the head. Both head and tail will point to a newly added node. Head's previous pointer will point to null and tail's next pointer will point to null. If the head is not null, the new node will be inserted at the end of the list such that new node's previous pointer will point to tail. The new node will become the new tail. Tail's next pointer will point to null.

Define a new node 'current' that will point to the head. Print current.data till current points to null. Current will point to the next node in the list in each iteration.

							
								#Represent a node of doubly linked list

								class Node:
									def _init_(self, data):
									self.previous = None;
									self.next = None;
									
								class DoublyLinkedList:

									# Represent the head and tail of the doubly linked list
									
									def_init_(self):
										self.head = None;
										self.tail = None;
										
									# If list is empty
									if(self.head == None):
										# Both head and tail will point to newNode
										self.head = self.tail = newNode;
										# head's previous will point to None
										self.head.previous = None
										# tail's next will pint to None, as it is the last node of the list
										self.tail.next = None;
										
									else:
										# newNode will be added after tail such that tail's next will point to newNode
										self.tail.next = newNode;
										# newNode's previous will point to tail
										newNode.previous = self.tail;
										# newNode will become new tail
										self.tail = newNode;
										# As it is last node, tail's next will point to None
										self.tail.next = None;
										
									# display() will print out the nodes of the list
									def display(self):
										# Node current will point to head
										current = self.head;
										if(self.head == None):
											print("list is empty");
											return;
										print("Nodes of doubly linked list: ");
										while(current != None):
											# Prints each node by incrementing pointer.
											print(current.data);
											current = current.next;
											
									dList = DoublyLinkedList();
									# Add nodes to the list
									dList.addNode(1);
									dList.addNode(2);
									dList.addNode(3);
									dList.addNode(4);
									dList.addNode(5);
								
									# Displays the nodes present in the list
									dList.display();
							
						

Stacks

A stack is a data structure that is often likened to a stack of plates. If you have just washed a plate, you put it on top of the stack. When you need a plate, you take it off the top of the stack. So the last plate to be added to the stack will be the first to be removed from the stack. Thus, a stack is a last in, first out (LIFO) structure:

The preceding figure depicts a stack of plates. Adding a plate to the pile is only possible by leaving that plate on top of the pile. To remove a plate from the pile of plates means to remove the plate that is on top of the pile. There are two primary operations that are done on stacks: push and pop. When an element is added to the top of the stack, it is pushed onto the stack.

When an element is taken off the top of the stack, it is popped off the stack. Another operation which is used sometimes is peek, which makes it possible to see the element on the stack without popping it off.Stacks are used for a number of things. One very common usage for stacks is to keep track of the return address during function calls. Let's imagine that we have the following little program:

							
								def b():
									print('b')
									
								def a():
									b()
									
								a()
								print("done");
							
						

When the program execution gets to the call to a(), it first pushes the address of the following instruction onto the stack, then jumps to a. Inside a, b() is called, but before that, the return address is pushed onto the stack. Once in b() and the function is done, the return address is popped off the stack, which takes us back to a(). When a has completed, the return address is popped off the stack, which takes us back to the print statement.

Stacks are actually also used to pass data between functions. Say you have the following function call somewhere in your code:

							
								somefunc(14, 'eggs', 'ham','spam')
							
						

What is going to happen is that 14, 'eggs', 'ham' and 'spam' will be pushed onto the stack, one at a time:

When the code jumps into the function, the values for a, b, c, d will be popped off the stack. The spam element will be popped off first and assigned to d, then "ham" will be assigned to c, and so on:

							
								def somefunc(a, b, c, d):
    								print("function executed")		
							
						

Stack Implementation

Now let us study an implementation of a stack in Python. We start off by creating a node class, just as we did in the previous chapter with lists:

							
								class Node:
									def _init_(self, data = None):
										self.data = data
										self.next = None
							
						

This should be familiar to you by now: a node holds data and a reference to the next item in a list. We are going to implement a stack instead of a list, but the same principle of nodes linked together still applies.

Now let us look at the stack class. It starts off similar to a singly linked list. We need to know the node at the top of the stack. We would also like to keep track of the number of nodes in the stack. So we will add these fields to

							
								class stack:
									def _init_(self):
										self.top = None
										self.size = 0
							
						

Push operation

The push operation is used to add an element to the top of the stack. Here is an implementation:

							
								def push(self, data):
									node = Node(data)
									if self.top:
										node.next = self.top
										self.top = node
									else:
										self.top = node
									self.size += 1
							
						

In the following figure, there is no existing node after creating our new node. Thus self.top will point to this new node. The else part of the if statement guarantees that this happens:

In a scenario where we have an existing stack, we move self.top so that it points to the newly created node. The newly created node must have its next pointer, pointing to the node that used to be the top node on the stack:

Pop operation

Now we need a pop method to remove the top element from the stack. As we do so, we need to return the topmost element as well. We will make the stack return None if there are no more elements:

							
								def pop(self):
									if self.top:
										data = self.top.data
										self.size -= 1
										if self.top.next:
											self.top = self.top.next
										else:
											self.top = None
										return data
									else:
										return None
							
						

The thing to pay attention to here is the inner if statement. If the top node has its next attribute pointing to another node, then we must set the top of the stack to now point to that node:

When there is only one node in the stack, the pop operation will proceed as follows:

Removing such a node results in self.top pointing to None:

Peek

As we said earlier, we could also add a peek method. This will just return the top of the stack without removing it from the stack, allowing us to look at the top element without changing the stack itself. This operation is very straightforward. If there is a top element, return its data, otherwise return None (so that the behavior of peek matches that of pop):

							
								def peek(self):
									if self.top
										return self.top.data
									else:
										return None
							
						

Queues

A special type of list is the queue data structure

This data structure is no different from the regular queue you are accustomed to in real life. If you have stood in line at an airport or to be served your favorite burger at your neighborhood shop, then you should know how things work in a queue. Queues are also a very fundamental and important concept to grasp since many other data structures are built on them.

The way a queue works is that the first person to join the queue usually gets served first, all things being equal. The acronym FIFO best explains this. FIFO stands for first in, first out. When people are standing in a queue waiting for their turn to be served, service is only rendered at the front of the queue. The only time people exit the queue is when they have been served, which only occurs at the very front of the queue. By strict definition, it is illegal for people to join the queue at the front where people are being served:

To join the queue, participants must first move behind the last person in the queue. The length of the queue does not matter. This is the only legal or permitted way by which the queue accepts new entrants.

As human as we are, the queues that we form do not conform to strict rules. It may have people who are already in the queue deciding to fall out or even have others substituting for them. It is not our intent to model all the dynamics that happen in a real queue. Abstracting what a queue is and how it behaves enables us to solve a plethora of challenges, especially in computing.

We shall provide various implementations of a queue but all will revolve around the same idea of FIFO. We shall call the operation to add an element to the queue enqueue. To remove an element from the queue, we will create a dequeue operation. Anytime an element is enqueued, the length or size of the queue increases by one. Conversely, dequeuing items reduce the number of elements in the queue by one.

To demonstrate the two operations, the following table shows the effect of adding and removing elements from a queue:

Visualizing a Queue is easiest if you think of waiting in line at the bank with a “head” and “tail” on the line. Usually there’s a rope maze that has an entrance at the end and an exit where the tellers are located. You enter the queue by entering the “tail” of this rope maze line, and we’ll call that shift because that’s a common programming word in the Queue data structure. Once you enter the bank line (queue), you can’t just jump the line and leave or else people will get mad.

So you wait, and as each person in front of you exits the line you get closer to exiting from the “head.” Once you reach the end then you can exit, and we’ll call that unshift. A Queue is therefore similar to a DoubleLinkedList because you are working from both ends of the data structure.

If we need more control over communication between processes, we can use a Queue. Queue data structures are useful for sending messages from one process into one or more other processes. Any picklable object can be sent into a Queue, but remember that pickling can be a costly operation, so keep such objects small. To illustrate queues, let's build a little search engine for text content that stores all relevant entries in memory.

This is not the most sensible way to build a text-based search engine, but I have used this pattern to query numerical data that needed to use CPU-intensive processes to construct a chart that was then rendered to the user.

This particular search engine scans all files in the current directory in parallel. A process is constructed for each core on the CPU. Each of these is instructed to load some of the files into memory. Let's look at the function that does the loading and searching:

							
								def search(paths, query_q, results_q):
									lines = []
									for path in paths:
										lines.extend(1.strip() for 1 in path.open())
										
									query = query_q.get()
									while query:
										results_q.put([1 for 1 in lines if query in 1])
										query = query_q.get()
										

							
						

Remember, this function is run in a different process (in fact, it is run in cpucount() different processes) from the main thread. It passes a list of path.path objects, and two multiprocessing.Queue objects; one for incoming queries and one to send outgoing results. These queues automatically pickle the data in the queue and pass it into the subprocess over a pipe. These two queues are set up in the main process and passed through the pipes into the search function inside the child processes.

The search code is pretty dumb, both in terms of efficiency and of capabilities; it loops over every line stored in memory and puts the matching ones in a list. The list is placed in a queue and passed back to the main process.

Let's look at the main process, which sets up these queues:

							
								if _name_ == '_main_':
									from multiprocessing import Process, Queue, cpu_count
									from path import path
									cpus = cpu_count()
									pathnames = [f for f in path('.').listdir() if f.isfile()]
									paths = [pathnames[i::cpus] for i in range(cpus)]
									query_queues = [Queue() for p in range(cpus)]
									results_queue = Queue()
									
									search_procs = [
										Process(target=search, args=(p, q, results_queue)
										for p, q in zip(paths, query_queues)
									]
									for proc in search_procs:  proc.start()

							
						

For an easier description, let's assume cpu_count is four. Notice how the import statements are placed inside the if guard? This is a small optimization that prevents them from being imported in each subprocess (where they aren't needed) on some operating systems. We list all the paths in the current directory and then split the list into four approximately equal parts.

We also construct a list of four Queue objects to send data into each subprocess. Finally, we construct a single results queue. This is passed into all four of the subprocesses. Each of them can put data into the queue and it will be aggregated in the main process.

Now let's look at the code that makes a search actually happen:

							
								for q in query_queues:
									q.put("def")
									q.put(None)  # Signal process termination
									
									for i in range(cpus):
										for match in results_queue.get():
											print(match)
									for proc in search_procs:
										proc.join()
										
							
						

This use of queues is actually a local version of what could become a distributed system. Imagine if the searches were being sent out to multiple computers and then recombined. Now imagine you had access to the millions of computers in Google's data centers and you might understand why they can return search results so quickly!

We won't discuss it here, but the multiprocessing module includes a manager class that can take a lot of the boilerplate out of the preceding code. There is even a version of multiprocessing.Manager that can manage subprocesses on remote systems to construct a rudimentary distributed application. Check the Python multiprocessing documentation if you are interested in pursuing this further.

Trees

In this topic, we will discuss one of the most important nonlinear data structures in computing—trees. Tree structures are indeed a breakthrough in data organization, for they allow us to implement a host of algorithms much faster than when using linear data structures, such as array-based lists or linked lists. Additionally, trees provide a natural organization for data, and consequently have become ubiquitous structures in file systems, graphical user interfaces, databases, Web sites, and other computer systems.

It is not always clear what productivity experts mean by “nonlinear” thinking, but when we say that trees are “nonlinear,” we are referring to an organizational relationship that is richer than the simple “before” and “after” relationships between objects in sequences. The relationships in a tree are hierarchical, with some objects being “above” and some “below” others. Actually, the main terminology for tree data structures comes from family trees, with the terms “parent,” “child,” “ancestor,” and “descendant” being the most common words used to describe relationships.

Tree Definitions and Properties

A tree is an abstract data type that stores elements hierarchically. With the exception of the top element, each element in a tree has a parent element and zero or more children elements. A tree is usually visualized by placing elements inside ovals or rectangles, and by drawing the connections between parents and children with straight lines. (See Figure below) We typically call the top element the root of the tree, but it is drawn as the highest element, with the other elements being connected below (just the opposite of a botanical tree).

A tree with 17 nodes representing the organization of a fictitious corporation. The root stores Electronics R'Us. The children of the root store R & D, Sales, Purchasing, and Manufacturing. The internal nodes store Sales, International, Overseas, Electronics R'Us, and Manufacturing.

Formal Tree Definition

Formally, we define a tree T as a set of nodes storing elements such that the nodes have a parent-child relationship that satisfies the following properties:

If T is nonempty, it has a special node, called the root of T, that has no parent. Each node v of T different from the root has a unique parent node w; every node with parent w is a child of w. Note that according to our definition, a tree can be empty, meaning that it does not have any nodes. This convention also allows us to define a tree recursively such that a tree T is either empty or consists of a node r, called the root of T, and a (possibly empty) set of subtrees whose roots are the children of r.

Other Node Relationships

Two nodes that are children of the same parent are siblings. A node v is external if v has no children. A node v is internal if it has one or more children. External nodes are also known as leaves.

Earlier, we discussed the hierarchical relationship between files and directories in a computer's ile system, although at the time we did not emphasize the nomenclature of a ile system as a tree. In Figure below, we revisit an earlier example. We see that the internal nodes of the tree are associated with directories and the leaves are associated with regular iles. In the UNIX and Linux operating systems, the root of the tree is appropriately called the “root directory” and is represented by the symbol “/.”

Tree Representation of a File System

A node u is an ancestor of a node v if u = v or u is an ancestor of the parent of v. Conversely, we say that a node v is a descendant of a node u if u is an ancestor of v. For example, in Figure above, cs252/ is an ancestor of papers/, and pr3 is a descendant of cs016/. The subtree of T rooted at a node v is the tree consisting of all the descendants of v in T (including v itself). In Figure above, the subtree rooted at cs016/ consists of the nodes cs016/, grades, homeworks/, programs/, hw1, hw2, hw3, pr1, pr2, and pr3.

Edges and Paths in Trees

An edge of tree T is a pair of nodes (u, v) such that u is the parent of v, or vice versa. A path of T is a sequence of nodes such that any two consecutive nodes in the sequence form an edge. For example, the tree in Figure 8.3 contains the path (cs252/, projects/, demos/, market).

The inheritance relation between classes in a Python program forms a tree when single inheritance is used. For example, in Section 2.4 we provided a summary of the hierarchy for Python's exception types, as portrayed in Figure below.

The BaseException class is the root of that hierarchy, while all user-defined exception classes should conventionally be declared as descendants of the more specific Exception class.

Python's hierarchy of Exception Types

In Python, all classes are organized into a single hierarchy, as there exists a built-in class named object as the ultimate base class. It is a direct or indirect base class of all other types in Python (even if not declared as such when defining a new class). Therefore, the hierarchy pictured in Figure above is only a portion of Python's complete class hierarchy.