Category: python Data Structure

Python – Algorithm Types ”; Previous Next The efficiency and accuracy of algorithms have to be analysed to compare them and choose a specific algorithm for certain scenarios. The process of making this analysis is called Asymptotic analysis. It refers to computing the running time of any operation in mathematical units of computation. For example, the running time of one operation is computed as f(n) and may be for another operation it is computed as g(n2). This means the first operation running time will increase linearly with the increase in n and the running time of the second operation will increase exponentially when n increases. Similarly, the running time of both operations will be nearly the same if n is significantly small. Usually, the time required by an algorithm falls under three types − Best Case − Minimum time required for program execution. Average Case − Average time required for program execution. Worst Case − Maximum time required for program execution. Asymptotic Notations The commonly used asymptotic notations to calculate the running time complexity of an algorithm. Ο Notation Ω Notation θ Notation Big Oh Notation, Ο The notation Ο(n) is the formal way to express the upper bound of an algorithm”s running time. It measures the worst case time complexity or the longest amount of time an algorithm can possibly take to complete. For example, for a function f(n) Ο(f(n)) = { g(n) : there exists c > 0 and n0 such that f(n) ≤ c.g(n) for all n > n0. } Omega Notation, Ω The notation Ω(n) is the formal way to express the lower bound of an algorithm”s running time. It measures the best case time complexity or the best amount of time an algorithm can possibly take to complete. For example, for a function f(n) Ω(f(n)) ≥ { g(n) : there exists c > 0 and n0 such that g(n) ≤ c.f(n) for all n > n0. } Theta Notation, θ The notation θ(n) is the formal way to express both the lower bound and the upper bound of an algorithm”s running time. It is represented as follows − θ(f(n)) = { g(n) if and only if g(n) = Ο(f(n)) and g(n) = Ω(f(n)) for all n > n0. } Common Asymptotic Notations A list of some common asymptotic notations is mentioned below − constant − Ο(1) logarithmic − Ο(log n) linear − Ο(n) n log n − Ο(n log n) quadratic − Ο(n2) cubic − Ο(n3) polynomial − nΟ(1) exponential − 2Ο(n) Print Page Previous Next Advertisements ”;

Discuss Python Data Structure ”; Previous Next Computers store and process data with an extra ordinary speed and accuracy. So, it is highly essential that the data is stored efficiently and can be accessed fast. Also, the processing of data should happen in the smallest possible time, but without losing the accuracy. Data structures deal with how the data is organised and held in the memory, when a program processes it. It is important to note that, the data that is stored in the disk as part of persistent storages (like relational tables) are not referred as data structure here. An Algorithm is step by step set of instruction to process the data for a specific purpose. So, an algorithm utilises various data structures in a logical way to solve a specific computing problem. In this tutorial, we will cover these two fundamental concepts of computer science using the Python programming language. Print Page Previous Next Advertisements ”;

Python – Useful Resources ”; Previous Next The following resources contain additional information on Python Data Structure. Please use them to get more in-depth knowledge on this. Useful Video Courses Python Flask and SQLAlchemy ORM 22 Lectures 1.5 hours Jack Chan More Detail Python and Elixir Programming Bundle Course 81 Lectures 9.5 hours Pranjal Srivastava More Detail TKinter Course – Build Python GUI Apps 49 Lectures 4 hours John Elder More Detail A Beginner”s Guide to Python and Data Science 81 Lectures 8.5 hours Datai Team Academy More Detail Deploy Face Recognition Project With Python, Django, And Machine Learning Best Seller 93 Lectures 6.5 hours Srikanth Guskra More Detail Professional Python Web Development with Flask 80 Lectures 12 hours Stone River ELearning More Detail Print Page Previous Next Advertisements ”;

Python – Algorithm Analysis ”; Previous Next Efficiency of an algorithm can be analyzed at two different stages, before implementation and after implementation. They are the following − 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 Suppose X is an algorithm and n is the size of input data, the time and space used by the algorithm X are the two main factors, which decide the efficiency of X. 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. The complexity of an algorithm f(n) gives the running time and/or the storage space required by the algorithm in terms of n as the size of input data. Space Complexity Space complexity of an algorithm represents the amount of memory space required by the algorithm in its life cycle. The space required by an algorithm is equal to the sum of the following two components − A fixed part that is a space required to store certain data and variables, that are independent of the size of the problem. For example, simple variables and constants used, program size, etc. A variable part is a space required by variables, whose size depends on the size of the problem. For example, dynamic memory allocation, recursion stack space, etc. Space complexity S(P) of any algorithm P is S(P) = C + SP(I), where C is the fixed part and S(I) is the variable part of the algorithm, which depends on instance characteristic I. Following is a simple example that tries to explain the concept − Algorithm: SUM(A, B) Step 1 − START Step 2 − C ← A + B + 10 Step 3 − Stop Here we have three variables A, B, and C and one constant. Hence S(P) = 1 + 3. Now, space depends on data types of given variables and constant types and it will be multiplied accordingly. Time Complexity Time complexity of an algorithm represents the amount of time required by the algorithm to run to completion. Time requirements can be defined as a numerical function T(n), where T(n) can be measured as the number of steps, provided each step consumes constant time. For example, addition of two n-bit integers takes n steps. Consequently, the total computational time is T(n) = c ∗ n, where c is the time taken for the addition of two bits. Here, we observe that T(n) grows linearly as the input size increases. Print Page Previous Next Advertisements ”;

Python – Searching Algorithms ”; Previous Next Searching is a very basic necessity when you store data in different data structures. The simplest approach is to go across every element in the data structure and match it with the value you are searching for.This is known as Linear search. It is inefficient and rarely used, but creating a program for it gives an idea about how we can implement some advanced search algorithms. Linear Search In this type of search, a sequential search is made over all items one by one. Every item is checked and if a match is found then that particular item is returned, otherwise the search continues till the end of the data structure. Example def linear_search(values, search_for): search_at = 0 search_res = False # Match the value with each data element while search_at < len(values) and search_res is False: if values[search_at] == search_for: search_res = True else: search_at = search_at + 1 return search_res l = [64, 34, 25, 12, 22, 11, 90] print(linear_search(l, 12)) print(linear_search(l, 91)) Output When the above code is executed, it produces the following result − True False Interpolation Search This search algorithm works on the probing position of the required value. For this algorithm to work properly, the data collection should be in a sorted form and equally distributed.Initially, the probe position is the position of the middle most item of the collection.If a match occurs, then the index of the item is returned.If the middle item is greater than the item, then the probe position is again calculated in the sub-array to the right of the middle item. Otherwise, the item is searched in the subarray to the left of the middle item. This process continues on the sub-array as well until the size of subarray reduces to zero. Example There is a specific formula to calculate the middle position which is indicated in the program below − def intpolsearch(values,x ): idx0 = 0 idxn = (len(values) – 1) while idx0 <= idxn and x >= values[idx0] and x <= values[idxn]: # Find the mid point mid = idx0 + int(((float(idxn – idx0)/( values[idxn] – values[idx0])) * ( x – values[idx0]))) # Compare the value at mid point with search value if values[mid] == x: return “Found “+str(x)+” at index “+str(mid) if values[mid] < x: idx0 = mid + 1 return “Searched element not in the list” l = [2, 6, 11, 19, 27, 31, 45, 121] print(intpolsearch(l, 2)) Output When the above code is executed, it produces the following result − Found 2 at index 0 Print Page Previous Next Advertisements ”;

Python – Amortized Analysis ”; Previous Next Amortized analysis involves estimating the run time for the sequence of operations in a program without taking into consideration the span of the data distribution in the input values. A simple example is finding a value in a sorted list is quicker than in an unsorted list. If the list is already sorted, it does not matter how distributed the data is. But of course the length of the list has an impact as it decides the number of steps the algorithm has to go through to get the final result. So we see that if the initial cost of a single step of obtaining a sorted list is high, then the cost of subsequent steps of finding an element becomes considerably low. So Amortized analysis helps us find a bound on the worst-case running time for a sequence of operations. There are three approaches to amortized analysis. Accounting Method − This involves assigning a cost to each operation performed. If the actual operation finishes quicker than the assigned time then some positive credit is accumulated in the analysis. In the reverse scenario it will be negative credit. To keep track of these accumulated credits, we use a stack or tree data structure. The operations which are carried out early ( like sorting the list) have high amortized cost but the operations that are late in sequence have lower amortized cost as the accumulated credit is utilized. So the amortized cost is an upper bound of actual cost. Potential Method − In this method the saved credit is utilized for future operations as mathematical function of the state of the data structure. The evaluation of the mathematical function and the amortized cost should be equal. So when the actual cost is greater than amortized cost there is a decrease in potential and it is used utilized for future operations which are expensive. Aggregate analysis − In this method we estimate the upper bound on the total cost of n steps. The amortized cost is a simple division of total cost and the number of steps (n).. Print Page Previous Next Advertisements ”;

Python – Sorting Algorithms ”; Previous Next 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 It 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. Example def bubblesort(list): # Swap the elements to arrange in order 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) Output When the above code is executed, it produces the following result − [2, 6, 11, 19, 27, 31, 45, 121] Merge Sort Merge sort first divides the array into equal halves and then combines them in a sorted manner. Example def merge_sort(unsorted_list): if len(unsorted_list) <= 1: return unsorted_list # Find the middle point and devide 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)) Output 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. Example 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) Output When the above code is executed, it produces the following result − [19, 2, 31, 45, 30, 11, 27, 121] Shell Sort Shell Sort involves sorting elements which are away from each 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. Example 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) Output 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. Example 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) Output When the above code is executed, it produces the following result − [2, 11, 19, 27, 30, 31, 45, 121] Print Page Previous Next Advertisements ”;

Python Data Structure – Quick Guide ”; Previous Next Python – DS Introduction Here, we will understand what is data structure with regards to Python programming language. Data Structure Overview Data structures are fundamental concepts of computer science which helps is writing efficient programs in any language. Python is a high-level, interpreted, interactive and object-oriented scripting language using which we can study the fundamentals of data structure in a simpler way as compared to other programming languages. In this chapter we are going to study a short overview of some frequently used data structures in general and how they are related to some specific python data types. There are also some data structures specific to python which is listed as another category. General Data Structures The various data structures in computer science are divided broadly into two categories shown below. We will discuss about each of the below data structures in detail in subsequent chapters. Liner Data Structures These are the data structures which store the data elements in a sequential manner. Array − It is a sequential arrangement of data elements paired with the index of the data element. Linked List − Each data element contains a link to another element along with the data present in it. Stack − It is a data structure which follows only to specific order of operation. LIFO(last in First Out) or FILO(First in Last Out). Queue − It is similar to Stack but the order of operation is only FIFO(First In First Out). Matrix − It is two dimensional data structure in which the data element is referred by a pair of indices. Non-Liner Data Structures These are the data structures in which there is no sequential linking of data elements. Any pair or group of data elements can be linked to each other and can be accessed without a strict sequence. Binary Tree − It is a data structure where each data element can be connected to maximum two other data elements and it starts with a root node. Heap − It is a special case of Tree data structure where the data in the parent node is either strictly greater than/ equal to the child nodes or strictly less than it’s child nodes. Hash Table − It is a data structure which is made of arrays associated with each other using a hash function. It retrieves values using keys rather than index from a data element. Graph − It is an arrangement of vertices and nodes where some of the nodes are connected to each other through links. Python Specific Data Structures These data structures are specific to python language and they give greater flexibility in storing different types of data and faster processing in python environment. List − It is similar to array with the exception that the data elements can be of different data types. You can have both numeric and string data in a python list. Tuple − Tuples are similar to lists but they are immutable which means the values in a tuple cannot be modified they can only be read. Dictionary − The dictionary contains Key-value pairs as its data elements. In the next chapters we are going to learn the details of how each of these data structures can be implemented using Python. Python – DS Environment Python is available on a wide variety of platforms including Linux and Mac OS X. Let”s understand how to set up our Python environment. Local Environment Setup Open a terminal window and type “python” to find out if it is already installed and which version is installed. Unix (Solaris, Linux, FreeBSD, AIX, HP/UX, SunOS, IRIX, etc.) Win 9x/NT/2000 Macintosh (Intel, PPC, 68K) OS/2 DOS (multiple versions) PalmOS Nokia mobile phones Windows CE Acorn/RISC OS BeOS Amiga VMS/OpenVMS QNX VxWorks Psion Python has also been ported to the Java and .NET virtual machines Getting Python The most up-to-date and current source code, binaries, documentation, news, etc., is available on the official website of Python www.python.org You can download Python documentation from this website given herewith,www.python.org/doc. The documentation is available in HTML, PDF, and PostScript formats. Installing Python Python distribution is available for a wide variety of platforms. You need to download only the binary code applicable for your platform and install Python. If the binary code for your platform is not available, you need a C compiler to compile the source code manually. Compiling the source code offers more flexibility in terms of choice of features that you require in your installation. Here is a quick overview of installing Python on various platforms − Unix and Linux Installation Here are the simple steps to install Python on Unix/Linux machine. Open a Web browser and go to www.python.org/downloads. Follow the link to download zipped source code available for Unix/Linux. Download and extract files. Editing the Modules/Setup file if you want to customize some options. run ./configure script make make install This installs Python at standard location /usr/local/bin and its libraries at /usr/local/lib/pythonXX where XX is the version of Python. Windows Installation Here are the steps to install Python on Windows machine. Open a Web browser and go to www.python.org/downloads. Follow the link for the Windows installer python-XYZ.msi file where XYZ is the version you need to install. To use this installer python-XYZ.msi, the Windows system must support Microsoft Installer 2.0. Save the installer file to your local machine and then run it to find out if your machine supports MSI. Run the downloaded

Python – Hash Table ”; Previous Next Hash tables are a type of data structure in which the address or the index value of the data element is generated from a hash function. That makes accessing the data faster as the index value behaves as a key for the data value. In other words Hash table stores key-value pairs but the key is generated through a hashing function. So the search and insertion function of a data element becomes much faster as the key values themselves become the index of the array which stores the data. In Python, the Dictionary data types represent the implementation of hash tables. The Keys in the dictionary satisfy the following requirements. The keys of the dictionary are hashable i.e. the are generated by hashing function which generates unique result for each unique value supplied to the hash function. The order of data elements in a dictionary is not fixed. So we see the implementation of hash table by using the dictionary data types as below. Accessing Values in Dictionary To access dictionary elements, you can use the familiar square brackets along with the key to obtain its value. Example # Declare a dictionary dict = {”Name”: ”Zara”, ”Age”: 7, ”Class”: ”First”} # Accessing the dictionary with its key print (“dict[”Name”]: “, dict[”Name”]) print (“dict[”Age”]: “, dict[”Age”]) Output When the above code is executed, it produces the following result − dict[”Name”]: Zara dict[”Age”]: 7 Updating Dictionary You can update a dictionary by adding a new entry or a key-value pair, modifying an existing entry, or deleting an existing entry as shown below in the simple example − Example # Declare a dictionary dict = {”Name”: ”Zara”, ”Age”: 7, ”Class”: ”First”} dict[”Age”] = 8; # update existing entry dict[”School”] = “DPS School”; # Add new entry print (“dict[”Age”]: “, dict[”Age”]) print (“dict[”School”]: “, dict[”School”]) Output When the above code is executed, it produces the following result − dict[”Age”]: 8 dict[”School”]: DPS School Delete Dictionary Elements You can either remove individual dictionary elements or clear the entire contents of a dictionary. You can also delete entire dictionary in a single operation.To explicitly remove an entire dictionary, just use the del statement. Example dict = {”Name”: ”Zara”, ”Age”: 7, ”Class”: ”First”} del dict[”Name”]; # remove entry with key ”Name” dict.clear(); # remove all entries in dict del dict ; # delete entire dictionary print (“dict[”Age”]: “, dict[”Age”]) print (“dict[”School”]: “, dict[”School”]) Output This produces the following result. Note that an exception is raised because after del dict dictionary does not exist anymore. dict[”Age”]: dict[”Age”] dict[”School”]: dict[”School”] Print Page Previous Next Advertisements ”;

Python – Backtracking ”; Previous Next Backtracking is a form of recursion. But it involves choosing only option out of any possibilities. We begin by choosing an option and backtrack from it, if we reach a state where we conclude that this specific option does not give the required solution. We repeat these steps by going across each available option until we get the desired solution. Below is an example of finding all possible order of arrangements of a given set of letters. When we choose a pair we apply backtracking to verify if that exact pair has already been created or not. If not already created, the pair is added to the answer list else it is ignored. Example def permute(list, s): if list == 1: return s else: return [ y + x for y in permute(1, s) for x in permute(list – 1, s) ] print(permute(1, [“a”,”b”,”c”])) print(permute(2, [“a”,”b”,”c”])) Output When the above code is executed, it produces the following result − [”a”, ”b”, ”c”] [”aa”, ”ab”, ”ac”, ”ba”, ”bb”, ”bc”, ”ca”, ”cb”, ”cc”] Print Page Previous Next Advertisements ”;