Forem: Main

dict.fromkeys() method in Python

Main — Fri, 19 Apr 2024 23:17:49 +0000

Thefromkeys() method of dicttype is used to create a new dictionary with keys from a given iterable and values pre-filled with a specified default value.

The syntax is as shown below:


dict.setdefault(iterable, value = None)

The items in the created dictionary has the elements from the iterableas keys and the specified valueas the default value. If valueis not given, Nonewill be used.


keys = [1, 2, 3, 4, 5]

d = dict.fromkeys(keys)
print(d)

If the default value is given, the item's values will be populated with the value instead of None.


keys = ['one', 'two', 'three', 'four', 'five']

d = dict.fromkeys(keys, 0)
print(d)

In the above example, we specified 0 as the default value to thefromkeys() method.

Note that the iterable argument can be any valid iterable not just lists. In the following example we use a range() for the iterable argument.


d = dict.fromkeys(range(5))
print(d)

dict.setdefault() method in Python

Main — Fri, 19 Apr 2024 23:11:09 +0000

The setdefault()method is used to retrieve a value from a dictionary given its key. If an item with the given key does not exist in the dictionary, it adds it and sets a given value for it.

The syntax is as shown below:


d.setdefault(key, value = None)

If an item of the given key exists, its value is returned. Otherwise, the key with the specified value is added to the dictionary and the value is returned.


d = {
     'Tokyo': 'Japan',
     'Ottawa': 'Canada',
     'Kigali': 'Rwanda'
    }

value = d.setdefault('Kigali')
print(value)

In the above example, we used the setdefault()method with a key that exist in the dictionary, 'Kigali'. The value associated with the key is returned which is 'Rwanda'.

Consider the following example:


d = {
     'Tokyo': 'Japan',
     'Ottawa': 'Canada',
     'Kigali': 'Rwanda'
    }

value = d.setdefault('Manilla')
print(value)

print(d)

In the above example, the given key, 'Manilla' does not exist in the dictionary. Thesetdefault() method adds an item with the key and sets a default value of Noneto it because we did not specify another value.

with a default value given


d = {
     'Tokyo': 'Japan',
     'Ottawa': 'Canada',
     'Kigali': 'Rwanda'
    }

value = d.setdefault('Manilla', 'Philippines')
print(value)

print(d)

Implement Merge-Sort in python

Main — Fri, 19 Apr 2024 22:38:22 +0000

merge sort implementation


#merge sort

#the merge algorithm
def merge(L1, L2, L):
  i = 0
  j = 0
  while i+j < len(L):
    if j == len(L2) or (i < len(L1) and L1[i] < L2[j]):
       L[i+j] = L1[i]
       i += 1
    else:
       L[i+j] = L2[j]
       j += 1

#main function
def merge_sort(L):

  n = len(L)
  if n < 2:
     return # list is already sorted

  # divide
  mid = n // 2 #midpoint
  L1 = L[0:mid] # the first half
  L2 = L[mid:n] # the second half

  # conquer with recursion
  merge_sort(L1) # sort first sub-list
  merge_sort(L2) # sort second sub-list

  # merge result
  merge(L1, L2, L) 

#example
L = [7, 5, 1, 4, 2, 8, 0, 9, 3, 6]
print('Before: ', L)
merge_sort(L)
print('After: ', L)

The merge sort algorithm uses the divide and conquer technique to efficiently sort a list of elements.

Divide and conquer involves breaking down a larger problem into smaller more manageable sub-problems, solving the sub-problems and then merging their solutions to solve the original problem. In the case with merge-sort, the algorithm breaks down the list into smaller sub-lists, sorts those sub-lists recursively, and then merges the sorted sub-lists back together until the entire list is sorted

Merge sort has time complexity of O(nlogn) in both average and worst case scenarios, this makes it one of the fastest sorting algorithms and consequently, one of the most sought after.

Merge sort is stable, meaning that it preserves the relative order of equal elements in the original list.

Algorithm Description

Assuming we have a list L , the basic steps followed by merge sort are as highlighted below:

divide ** - If **L has zero or one element, it is already sorted, immediately return L. Otherwise, divide L's elements between two sub-lists, L1 and L2. Where, L1 contains first half of the elements and L2 the rest..
conquer - Recursively sort sub-lists L1 and L2.
merge - Combine the elements in a sorted state and put them back toL.

Example

Consider if we want to sort the following list using merge sort.

In the first step of merge sort, the list will be recursively divided into individual sub-lists. This means that the list will be split into two sub-lists and then each of the sub-lists will be split into two more sub-lists, and so on until each sub-list contains only a single element. The following figure demonstrates the splitting phase:

After the divide step is over, we need to sort each sub-list and then recursively merge it with the other sorted sub-lists. This is known as the "conquer" step.

At the beginning of the conquer step, each sub-lists is made up of a single element. Logically, a list with only one element is already sorted. Sublists with more than a single elements will have to be sorted before they are combined.

Merge sort implementation

In this section, we will implement the merge sort algorithm using functions.

For the sake of clarity, we will split the algorithm into two functions, merge() and merge_sort(). The merge()function will be responsible for combining two already sorted sub-lists into a single sorted list. The merge_sort() function is where the main logic of the algorithm will go.

The merge() function


#L is the list while L1 and L2 are the sublists.

def merge(L1, L2, L):
  i = j = 0
  while i+j < len(L):
    if j == len(L2) or (i < len(L1) and L1[i] < L2[j]):
       L[i+j] = L1[i]
       i += 1

    else:
       L[i+j] = L2[j]
       j += 1

#example
L = [2, 7, 4, 0, 6, 5]
L1 = [2, 4, 7]
L2 = [0, 6, 5]

merge(L1, L2, L)
print(L)

The merge() function above takes in two sorted sub-lists(L1 andL2) and puts their elements back to the original list(L) in a sorted state. It does so by determining from which sub-list the next item should be taken before inserting the picked item back to list L. For clarity, let us look at the function statement by statement:

i = j = 0 - This statement initializes two distinct variables, i and j each with a value of 0. The two variablesi, and jrepresents the position of the current element in L1and L2, respectively.
while i+j < len(L): - Loop until the value ofi + j is greater than the length of the list. Note that at this point, the merge operation will be complete.
if j == len(L2) or (i < len(L1) and L1[i] < L2[j]): L[i+j] = L1[i] i += 1 else: L[i+j] = L2[j] j += 1

-The j == len(L2) condition checks if there is elements to be picked in L2, remember thatjrepresents the position of the current element in L2, thus if it is equal to len(L2), it means that we have reached the end of L2, so we pick the next element from L1 and insert it toL.

-Due to the presence of or, the second condition i.e (i < len(L1) and L1[i] < L2[j])will only be tested if the first condition, i.e (j == len(L2)) fails, it means that L2 still has element . So we pick and insert intoL the smaller of the sub-lists' current element and then increment either iorjdepending on whose sub-list's element was picked.

-The elsestatement also caters for when L1has no more elements.

After implementing the merge() function, the implementation of the merge_sort()function become easier.

implementmerge_sort()


#the implementation of merge() is omitted, refer to the previous snippet.

def merge_sort(L):

  n = len(L)
  if n < 2:
     return # list is already sorted

  # divide
  mid = n // 2 #midpoint
  L1 = L[0:mid] # the first half
  L2 = L[mid:n] # the second half

  # conquer
  merge_sort(L1) # recursively sort first sub-list
  merge_sort(L2) # recursively sort second sub-list

  # merge
  merge(L1, L2, L) 

#usage example
L = [99, 9, 0, 2, 1, 0, 1, 100, -2, 8, 7, 4, 3, 2]
merge_sort(L)
print(L)

[-2, 0, 0, 1, 1, 2, 2, 3, 4, 7, 8, 9, 99, 100]

Themerge_sort()function does not return any value because the sorting happens to the original list.

The entire merge sort implementation is as shown below:


#merge sort implementation

def merge(L1, L2, L):
  i = 0
  j = 0
  while i+j < len(L):
    if j == len(L2) or (i < len(L1) and L1[i] < L2[j]):
       L[i+j] = L1[i]
       i += 1
    else:
       L[i+j] = L2[j]
       j += 1

def merge_sort(L):

  n = len(L)
  if n < 2:
     return # list is already sorted

  # divide
  mid = n // 2 #midpoint
  L1 = L[0:mid] # the first half
  L2 = L[mid:n] # the second half

  # conquer with recursion
  merge_sort(L1) # sort first sub-list
  merge_sort(L2) # sort second sub-list

  # merge result
  merge(L1, L2, L) 

#usage example
L = [99, 9, 0, 2, 1, 0, 1, 100, -2, 8, 7, 4, 3, 2]
merge_sort(L)
print(L)

Complexity analysis

The time complexities of merge sort with a list of size n, are as outlined below:

Best case - O(nlogn) , this happens when the input list is already sorted.
Average case -O(nlogn), when the input list is randomly sorted.
Worst case - O(nlogn), when the input list is reverse sorted.

Space complexity

Merge sort has a space complexity ofO(n) due to the space occupied by the sub-lists.

csv module in Python

Main — Fri, 19 Apr 2024 22:33:28 +0000

The csvmodule provide tools for working with and manipulating csv(comma separated values) files.

csv files are used to store tabular data in plain text formats. csv data consists of records and each record is made up of fields. Normally, a line in a csv file represents a single record while fields in a record are separated by commas.

The following is an example of csv data.


first_name,last_name,age,gender
John,Main,30,male
Jane,Doe,24,female
Morrison,Smith,22,male
Brian,Gates,32,male
Mary,Reagan,25,female

Typically, files with a .csvextension are normally associated with csv data.

Reading csv data

To read data from a csv file, use the reader()function. The function has the following basic syntax:


csv.reader(iterable)

The reader()function takes any iterable that yields a line during each iteration. This can be a file object, a list or any other iterable made of lines. It returns an iterator of lists, where each list represents a record in the csv data.

Consider if the previous csv data exists in a file called demo.csv.


import csv

with open('demo.csv') as file:
  reader = csv.reader(file)

  for row in reader:
     print(row)

['first_name', 'last_name', 'age', 'gender']

['John', 'Main', '30', 'male']

['Jane', 'Doe', '24', 'female']

['Morrison', 'Smith', '22', 'male']

['Brian', 'Gates', '32', 'male']

['Mary', 'Reagan', '25', 'female']

In the above example, we used data stored in a file object but as earlier mentioned, you can literally use any iterable. In the following example, we use a list instead of a file object.


import csv

data = """first_name,last_name,age,gender
John,Main,30,male
Jane,Doe,24,female
Morrison,Smith,22,male
Brian,Gates,32,male
Mary,Reagan,25,female"""

reader = csv.reader(data.splitlines())
for row in reader:
  print(row)

Writing csv data

The writer() function creates an object for writing csv data. It has the following basic syntax:


csv.writer(fileobj)

Where the fileobjis the opened file where the csv data will be written to.

After creating the writer object, we can then usewriterow() method to write a single record into the file or writerows() to write multiple rows at once.


import csv

with open('demo.csv', 'a') as file:
  writer = csv.writer(file)

  writer.writerow(('Ruth', 'Miller', 24, 'female'))
  writer.writerow(('Brandy', 'Jones', 22, 'male'))

Note that in the above example, we opened the demo.csv file with the "a" mode. This ensures that the new rows are appended to the file, if we had used the "w" mode instead, the existing rows would have been overwritten.


import csv

with open('demo.csv') as file:
  print(file.read())

first_name,last_name,age,gender

John,Main,30,male

Jane,Doe,24,female

Morrison,Smith,22,male

Brian,Gates,32,male

Mary,Reagan,25,female

Ruth,Miller,24,female

Brandy,Jones,22,male

As you can see above, the new records have been added successfully.

To add multiple rows at once, use the writer.writerows() method.


import csv

rows = [
   ('Stephen', 'King', 32, 'male'),
   ('Molly', 'Jones', 22, 'female')
  ]

with open('demo.csv', 'a') as file:
  writer = csv.writer(file)
  writer.writerows(rows)

Quoting behavior

In cases where you want records of certain types to be stored in quotes, you can specify the quotingflag when creating the writer object. For example, if you want string items to be in quotes but numeric values not to be, you can specify the quoting parameter as csv.QUOTE_NONNUMERIC.


import csv

rows = [
   ('Stephen', 'King', 32, 'male'),
   ('Molly', 'Jones', 22, 'female')
  ]

with open('demo.csv', 'w') as file:
  writer = csv.writer(file, quoting = csv.QUOTE_NONNUMERIC)
  writer.writerows(rows)

If you open thedemo.csvfile, you will see that in the written records , string fields are quoted.


import csv

with open('demo.csv') as file:
  print(file.read())

"Stephen","King",32,"male"

"Molly","Jones",22,"female"

All the quoting options are as shown in the following table:

csv dialects

Separating csv fields with a comma is just the popular convention, there is really no well defined standard on csv format. For example, you could as well separate the fields with spaces instead of commas. This means that any csv parser needs to be very flexible when dealing with csv delimiters.

Dialects allow us to specify to the parser the delimiter and other important parameters that will be used when parsing the csv files. The csv.list_dialects() function returns a list of the registered dialects.


import csv

print(csv.list_dialects())

['excel', 'excel-tab', 'unix']

The default dialect is excel, in which the fields are delimited with commas.

If for example, you have csv data in which the fields are delimited by a pipe character"|" or any other character instead of a comma, as shown below:


first_name|last_name|age|gender
John|Main|30|male
Jane|Doe|24|female
Morrison|Smith|22|male
Brian|Gates|32|male
Mary|Reagan|25|female

You can register a new dialect using thecsv.register_dialect(). You can then use the registered dialect with readerand writerobjects.


import csv

data = """first_name|last_name|age|gender
John|Main|30|male
Jane|Doe|24|female
Morrison|Smith|22|male
Brian|Gates|32|male
Mary|Reagan|25|female"""

csv.register_dialect('pipe', delimiter = '|')
print("Dialects: ", csv.list_dialects())

reader = csv.reader(data.splitlines(), dialect = 'pipe') #use the dialect

for row in reader:
  print(row)

Apart from delimiter, you can specify other dialect parameters depending on the nature of your csv data. The supported parameters are shown in the following tables:

parameter	default value	description
`delimiter`	`,`	Field separator.
`quotechar`	`"`	The character to enclose fields where quoting is allowed.
`lineterminator`	`\r \n`	The string/character used to terminate a line
`doublequote`	`True`	Whether quotchar parameters are doubled.
`escapechar`	`None`	Character used to indicate an escape sequence
`skipintialspace`	`False`	Ignore whitespace after the delimiter

Automatic dialect detection

In cases where the csv format is not well known, we can use the csv.Snifferclass, which automatically constructs a dialect object given a sample of csv data.

Consider if we have the following csv data.


first_name&last_name&age&gender
John&Main&30&male
Jane&Doe&24&female
Morrison&Smith&22&male
Brian&Gates&32&male
Mary&Reagan&25&female

In the above example, we used the "&"character as the delimiter.


import csv

data="""first_name&last_name&age&gender
John&Main&30&male
Jane&Doe&24&female
Morrison&Smith&22&male
Brian&Gates&32&male
Mary&Reagan&25&female"""

sniffer=csv.Sniffer()
dialect=sniffer.sniff(sample=data)

print("delimiter: ", dialect.delimiter)

reader = csv.reader(data.splitlines(), dialect = dialect)
for row in reader:
  print(row)

As you can see, the sniffer correctly detected that "&" is used as the delimiter character. However, you should keep in mind that the sniffer is not always correct, it can only be said to be making educated guesses.

Using named fields

You can usecsv.DictReader and csv.DictWriterclasses to use named fields when reading or writing csv data.

The two classes allows you to specify in advance a list of field names to alias the fields in the csv data.

`csv.DictReader`

The DictReaderclass allows you to read rows with the fields having an alias name.

Consider the following example:


import csv

data = """first_name,last_name,age,gender
John,Main,30,male
Jane,Doe,24,female
Morrison,Smith,22,male
Brian,Gates,32,male
Mary,Reagan,25,female"""

fields = 'fname', 'lname', 'age', 'gender'

reader = csv.DictReader(data.splitlines(), fieldnames = fields)
for row in reader:
  print(row['fname'], row['lname'])

Iterating through the DictReaderobject will yield a list of dictionaries, where each dictionary represents a row in the csv data.

`csv.DictWriter`

DictWriter objects writes data into a csv file with argument given as dictionaries. Consider the following example:


import csv

fields = 'fname', 'lname', 'age', 'gender'
data_to_wite = [
    {'fname':'Stephen', 'lname':'King', 'age':32, 'gender':'male'},
    {'age':22, 'lname':'Jones', 'fname':'Molly', 'gender':'female'},
]

with open('pynerds.txt', 'w') as file:
  writer = csv.DictWriter(file, fieldnames = fields)
  writer.writerows(data_to_wite)

As shown above, when using named fields, the order is not important as long as the field names are correct.


import csv

with open('demo.csv') as file:
  print(file.read())

Stephen,King,32,male

Molly,Jones,22,female

items(), keys() and values() methods in Python dictionary

Main — Mon, 15 Apr 2024 01:34:19 +0000

An element in a dictionary is also called an item. Each item is made up of a key and a value.

The three dictionary methods; items(), keys() and values()retrieves all items, keys and values respectively.

items() - Returns an iterable of all key-value pairs(items) present in the dictionary.
keys() - Returns an iterable with all the keys in the dictionary.
values()- Returns an iterable with all the values in the dictionary.

items() - Get all items present in a dictionary

To get an iterable containing all the items present in a dictionary, use theitems()method. The syntax is as shown below:


d.items()

The method does not take any argument.


d = {
      'Spain': 'Madrid',
      'Italy': 'Rome',
      'France': 'paris'
    }
#get the items
all_items = d.items()

print(all_items)

The items()method is useful when it comes to iterating over the dictionary items. Remember that iterating over a dictionary only yields its keys, so using the items()method allows you to access both the key and its corresponding value in one iteration.

iterating through a dictionary


d = {
      'Spain': 'Madrid',
      'Italy': 'Rome',
      'France': 'paris'
    }

for i in d:
   print(i)

In the above example, we used the for loop to iterate over a dictionary. As you can see, only the keys are returned. Now consider the same example with the items() method.

iterating over items()


d = {
      'Spain': 'Madrid',
      'Italy': 'Rome',
      'France': 'paris'
    }

for i in d.items():
   print(i)

As you can see, iterating through the items() object returns tuples in the form (key, value) for each dictionary item.

keys() - get all keys of a dictionary

Thekeys()method returns an object containing all the keys present in a dictionary.

it has the following syntax:


d.keys()

The method does not take any arguments.


d = {
      'Spain': 'Madrid',
      'Italy': 'Rome',
      'France': 'paris'
    }
#get the keys
all_keys = d.keys()

print(all_keys)
print(type(all_keys))

You can iterate through the returned object to get individual keys at each iteration.


d = {
      'Spain': 'Madrid',
      'Italy': 'Rome',
      'France': 'paris'
    }
#iterate through the keys
for k in d.keys():
   print(k)

values() - get all values in the dictionary

Finally, the values() method returns an object containing all the keys in the dictionary. It has the following syntax:


d.values()

The method does not take arguments.


d = {
      'Spain': 'Madrid',
      'Italy': 'Rome',
      'France': 'paris'
    }
#get the keys
all_values = d.values()

print(all_values)
print(type(all_values))

iterate through the values


d = {
      'Spain': 'Madrid',
      'Italy': 'Rome',
      'France': 'paris'
    }
#iterate through the keys
for v in d.values():
   print(v)

Conclusion

Use items()to get an iterable of two length tuples, where each tuple contains a key and a value of a dictionary item.
Use keys() to get an iterable of all the keys present in a dictionary.
use values() to get an iterable of all the values present in a dictionary.

Linked list vs Array

Main — Mon, 15 Apr 2024 01:27:52 +0000

Linked lists and arrays are two commonly used data structures. Each has its own advantages and disadvantages, and is suitable for specific scenarios than others. In this article we will compare the two data structures on various basis.

Definitions

An array is a data structure that stores a fixed-size collection of elements of the same type. The elements are stored contiguously in memory and each element can be accessed using an index. Lists in Python are implemented through arrays.


arr = ['Java', 'Python', 'Ruby', 'C++'] # an array

#get an element at specific index
print(arr[2]) # the element at the third position

On the other hand, a linked list is a linear data structure in which elements are connected through references. Each element, also known as a node , contains a data field and a reference to the next node in the list. Basically, a node in a linked list will look as shown below:


class Node:
    def __init__ (self, element, nxt):
        self.data = element #Users element
        self.next = nxt #The next node in the list

The data instance attribute keeps the value of the element stored by the node, while the nextattribute stores a reference to the next node in the list.

Insertion and Deletion

Arrays

Insertion and deletion in an array can be expensive, especially if the size is large and the element is inserted or deleted from the beginning or middle of the array.

When you insert or delete an element at an arbitrary position in an array, each elements after that position shifts.

In case with insertion, the elements shifts to the right, creating a gap for the new element to be inserted. The following figure illustrates this better.

With deletion, the elements shifts to the left to occupy the space that has been left by the removed element.

Insertion and deletion in arrays have a worst case time complexity of O(n), as all the elements after the insertion or deletion shifts.This can be costly for large arrays with a lot of elements.

The only exception is when insertion or deletion happens at the end of the array, as there is no need to shift any elements. Insertion and deletion at the last position has a time complexity of O(1). This makes the end of an array the best place to insert or delete elements if possible

Linked list

Insertion and deletion in a linked list is easier and much more efficient compared to in array. In a linked list, both insertion and deletion have a constant time complexity, O(1).

With insertion, the new element can be inserted at any position by just updating the relevant nodes to reference the new node. While with deletion, an element can simply be dereferenced and removed from the list without affecting the references of other nodes. This is because each node only has a reference to the next node, so removing one node does not affect the references of other nodes.

Accessing elements

Accessing elements in an array is much more efficient compared to in a linked list. The elements in arrays are stored in contagious memory locations, we can, therefore, directly access an element using its index. This ensures a constant time complexity(O(1)) regardless of the size of the array or the location of the element to be accessed.

On the other hand, elements in linked list are scattered throughout the memory, thus we have to traverse the entire list to access a specific element. Since the elements are not stored contiguously we cannot use index to access an element, we have to traverse the list starting from the head node until we reach the desired element Thus, accessing elements has a worst case time complexity of O(n).

Memory allocation and efficiency

Arrays are more memory-efficient as they only require memory for the individual elements, and not for any additional references. However, they also have a fixed size that cannot be changed, this makes them less flexible and not very suitable for representing dynamic data.

A linked list requires extra memory to store the references, which can be disadvantageous if the list contains a large number of elements. On the better side, memory allocation for a linked list is dynamic, meaning new nodes can be allocated as and when needed. This makes linked lists flexible for adding or removing elements.

Summary

Array	Linked list
A collection of homogeneous items in which an item can be accessed using its index	A sequence of nodes where each node references the next node in the list.
Have a fixed size that is defined at declaration.	Are of dynamic size.
Faster access to elements as each element can be accessed with its index at a time complexity of `O(1)`.	Accessing elements is inefficient and has a worst time complexity of `O(n)`.
Insertion and deletion operations become more inefficient the closer you move to the beginning of the array. Both has a worst time complexity of `O(n)`	Very efficient insertion and deletion operations. Both operations have a time complexity of `O(1)` at any position.
Relatively less memory footprint as only the elements are stored.	More memory footprint, as references to other nodes have to be stored in addition to the actual element.

Insertion sort in Python

Main — Mon, 15 Apr 2024 01:16:24 +0000

Insertion sort is a simple yet relatively efficient comparison-based sorting algorithm.

Compared to other basic sorting algorithm such as bubble sortand selection sort, insertion sort performs relatively well especially on small-to-medium and mostly sorted lists. It also has a stable sorting behavior, meaning that elements with equal values will maintain their original relative order after sorting.

Insertion sort works in-place, in that it re-arranges the elements of the original list instead of creating a new list. This makes it efficient in terms of memory usage.

Compared to other advanced sorting algorithm such as quicksortand mergesort, insertion sort is relatively easy to understand and implement. However it has an average and worst-time complexities ofO(n2), this means that it can be inefficient when sorting large dataset. It works well when the input list is small in size and or it is nearly sorted.

Algorithm Description

In insertion sort, the input array/list is divided into two segments, the sorted segment on the left and the *unsorted segment * on the right. Initially, the sorted segment is made up of only the first element of the list, while the unsorted segment is made up of the rest of the list elements.

The algorithm iterates through the unsorted segment and takes one element at a time, comparing it with the elements in the sorted segment. It finds the correct position for the element in the sorted segment and inserts it there, shifting the other elements if necessary. The process continues until all elements in the unsorted segment are inserted into their correct positions in the sorted segment.

The following is the higher-level description of the steps in the insertion sort algorithm:

The first element is already sorted.
Pick the next element.
Compare it with the the elements in the sorted segment.
Insert it before all larger elements.
Repeat steps 2-4 with the rest of the unsorted elements until the entire list is sorted.

Insertion sort Example

In this part we will demonstrate the steps insertion sort algorithm would follow to sort the following list.

In the first step the sorted segment is only made up of the first element of the list. Logically, a list with only one item is already sorted.

We will use color green to indicate the elements in the sorted segment and red for element in the unsorted segment.

We start by picking an unsorted element and placing it at its position in the sorted segment. The first unsorted element is 4, so we pick it and insert it at its place in the sorted segment.

In the above case, 4 is smaller than7 so the two are swapped. We now move on to the next unsorted element which is 8.

In the above case, we found that 8 is already sorted so no need for performing any action.

After placing 5 at its place, the unsorted segment is now only made up of a single element, 6. let us put it in its place.

After performing the above step, we are done and the list is now sorted.

Insertion sort implementation.

We can implement insertion sort through nested loops. the first loop picks the current unsorted element and the inner loop inserts it at its place in the sorted segment. The most suitable approach of implementing this is by use of an outer for loopand an inner while loop.


def insertion_sort(lst):

   for i in range(1, len(lst)):
      j = i
      while (j > 0) and lst[j-1] > lst[j]:
         lst[j-1], lst[j] = lst[j], lst[j-1] #swap the elements
         j -=1

#sort a list
L = [99, 9, 0, 2, 1, 0, 1, 100, -2, 8, 7, 4, 3, 2]

insertion_sort(L)
print("The sorted list is: ", L)

The insertion_sort() function above, does not return any value because the input list is being sorted in-place.

Forloops are useful when we know in advance the number of iterations needed and in contrast, while loops are more suitable in cases where we do not know in advance the number of iterations to be performed. The fitness of each of the two loops is clearly shown in the above implementation of insertion sort. Using an inner whileloop ensures that we can efficiently get out of the loop after the element is placed at its position without using extra conditional checks.

Descending insertion sort

To sort the list elements in descending order using insertion sort, we simply need to change a single statement in the insertion_sort() function and actually just a single character.

Changing the > character in the second condition of the while loop to< character will make the algorithm to sort the elements in descending order i.e we need to change the statement fromwhile (j > 0) and lst[j-1] > lst[j]: to while (j > 0) and lst[j-1] < lst[j]:.

descending insertion sort


def insertion_sort(lst):

   for i in range(1, len(lst)):
      j = i
      while (j > 0) and lst[j-1] < lst[j]: #changed > to <
         lst[j-1], lst[j] = lst[j], lst[j-1] #swap the elements
         j -=1

#sort a list
L = [99, 9, 0, 2, 1, 0, 1, 100, -2, 8, 7, 4, 3, 2]

insertion_sort(L)
print("The sorted list is: ", L)

Algorithm analysis

The running time complexities of insertions sort are as shown below:

*best case - * O(n), this is when the list is already sorted.
*Average case * - O(n2), this is when the list is randomly sorted.
Worst case - O(n2), When the list is reverse sorted.

Applications of insertion sort

The following list outlines cases where insertion sort may be suitable:

When the dataset is not very large in size.
When the elements are almost sorted.
When simplicity and stability are needed.

Insertion sort is relatively more performant compared to other basic sorting algorithm such as bubble sort or selection sort. However, itsO(n2) average and worst running time makes it limited compared to other sorting algorithms such as quicksort or mergesort. It is, therefore, more suitable when sorting small sets of data.

Python Function Scope

Main — Mon, 15 Apr 2024 01:08:35 +0000

When you use a name in a Python program such as variable name function name,etc, Python creates, changes or looks up the name in a namespace. A namespace is the complete list of names that exists in a given context.

There are two types of namespaces, global namespace and local namespace.

The scope of an object determines the locations in the program where it can be accessed, by default, objects are only accessible from within the namespace that they occur. Objects in the global namespace are accessible from anywhere in the program, this are the names that are declared at the top level of a module or a script i.e not inside a function, a class, etc. On the other hand, names declared inside a block such as a function are local to that block and are only accessible within the block.

When we define a function, Python sets up a local namespace for the function. Any object declared inside the function will only be accessible within the function, the object is said to be local to that function. Trying to access local objects outside their scope will raise a NameError. For example:

def demo():
    x = 100
    print(x)

demo()
//100
print(x)
//NameError: name 'x' is not defined

Objects inside a function are localized such that they will not crash with objects with similar names outside that function.This allows same name to be used for different objects in different scopes without causing conflicts.

If a function declares a name that also exists in the global namespace, the local name takes precedence over the global name and overwrites it only inside that function. Example:


x = 200
def demo():
    x = 100
    print(x)

demo()
//100
print(x)
//200

In the above example, there are two distinct variables with a name x, one in the global namespace with a value of 200and another in function demo's local namespace with a value of 100. The value of xis, therefore, determined by the location where we are using it. Making any changes to the'x' inside the function demo does not affect in any way the value of the 'x' outside its scope.

Name Resolution, The LEGB Rule

When we mention an object by name, the Python interpreter follows an inside-out approach in order to identify the object we are referring to. This approach is often referred to as the LEGB rule, which stands for Local, Enclosing, Global, Built-in. This rule can be summarized as follows:

Local, first : Look for this name first in the local namespace and use local version if available. If not, go to higher namespace.
Enclosing, second : If the current function is enclosed within another function, look for the name in that outer function. If not, go to higher namespace.
Global, third : Look for the name in the objects defined at global namespace
Built-in,last : Finally, look for the variable among Python’s built-in names.

If the interpreter goes through all the 4 stages and does not locate the name, a NameErroris raised, of course if the operation was not an assignment operation in which case an object with that name will be created in the local scope instead of raising the error.

Example:


x = 200
def demo():
    x = 300
    def inner():
        print(x)
    inner()

demo()
//300

In the above case, in the call to printx, the interpreter fails to find an object with a name x in the function inner's scope, it moves outward to the enclosing function in which case it finds an'x' with a value of 300thus terminating the search. If still an object with a name 'x'was not located in the enclosing function 'demo', the globalxwith a value of 200would have been returned.

More Examples:


x = 500
def demo():
   print(x)
   x = 300
   print(x)

demo()
//500
//300
def demo2():
   y = 400
   def inner():
       print(x + y)
   inner()

demo2()
//900

The Global Statement

The global statement is the only thing that is capable of transforming a name defined inside a function to a global name. This means that the name will behave just like names defined in the global namespace and will be accessible from anywhere in the program.

Examples:


def demo():
   global x
   x = 200

demo()
print(x)
//200

If a global name exists similar to the name specified in the global statement, any modifications done to the object it identifies will take effect at a global level. Examples:


x = 100
def demo():
    global x
    x = 500

demo()
print(x)
//500

To declare multiple global names in one global statement, we use the global keyword followed by the comma separated names, example:


def demo():
   global x, y, z
   x = 4
   y = 3
   z = x + y

demo()
print(x, y, z)
//4, 3, 7

While the global statement can be useful at times, it can make code mor obscured as it can make it difficult to keep track of the global names. It should, therefore, be avoided whenever possible, after all names inside a function are made local to that function by default because it is the best policy. We can Instead, pass global values as function arguments and then return the modified values.

The nonlocal Statement

The nonlocalstatement is a close cousin of the globalstatement. While the globalstatement makes a name available at global level, the nonlocalstatement makes a name available to the enclosing function's scope. This also allows the nested function to make changes to variables defined in the enclosing function. Examples:


def demo():
    x = 400
    def inner():
        nonlocal x
        x = 600
    inner()
    print(x)

demo()
//600
def demo2():
    def inner():
        nonlocal y 
        y = 500
    inner()
    print(y)

demo2()
//500

Note: We cannot use the nonlocalstatement with a top level function, trying this will raise a SyntaxError


def demo():
    nonlocal y
    y = 100

demo()
//SyntaxError: no binding for nonlocal 'y' found

Bubble sort in Python

Main — Sun, 14 Apr 2024 17:52:34 +0000

#Optimized bubble sort
def bubble_sort(lst):

  swapped = True
  c = 0
  while swapped == True:
    swapped = False
    for j in range(len(lst)-1):  
      
      if(lst[j]>lst[j+1]):
        lst[j], lst[j + 1] = lst[j + 1], lst[j] #swap the elements
        swapped = True
      c +=1
  return c

#sort a list
L = [9, 0, 2, 1, 0, 1, 100, -2, 8, 7, 4, 3, 2]

bubble_sort(L)  
print("The sorted list is: ", L)

Bubble sort is the most basic sorting algorithm. Its simplicity makes it suitable for introducing computer science students to sorting algorithms. However, it has an average and worst case running time of O(n²), making it highly inefficient for sorting medium to large dataset.

Bubble sort is highly limited compared to other sorting algorithms and, therefore, not suitable for practical environments beyond educational ones.

Despite its limitations, understanding the operation of bubble sort is essential for you to understand how more advanced sorting algorithms works.

In the following parts we will understand how the bubble sort algorithm operates and how to implement it in Python.

Bubble sort Algorithm description

In bubble sort algorithm, each pair of adjacent elements are compared and only swapped if they are not in order. That is , if the first element in the pair is larger than the other element, the elements are swapped.

The swapping of elements happens in-place meaning that the original list gets modified.

If we have a list of n elements, the bubble sort algorithm can be performed through the steps shown below:

Compare the first element with the next element after it.
If the first element is greater:
- Swap the two elements.
Move to the next pair of elements in the list.
Repeat step1 -3 until the end of the list is reached.
Once no more swaps are needed, the list is sorted.

With the above steps, the largest elements gradually moves to the end of the list until the list is sorted.

Direct Implementation

To implement bubble sort, you can use nested loops, the following example shows how we can achieve this with for loops:

with nested for loops

def bubble_sort(lst):

  for i in range(len(lst)-1):
    for j in range(len(lst)-1):  

      if(lst[j]>lst[j+1]):
        lst[j], lst[j + 1] = lst[j + 1], lst[j] #swap the elements

#sort a list
L = [9, 0, 2, 1, 0, 1, 100, -2, 8, 7, 4, 3, 2]

bubble_sort(L)  
print("The sorted list is: ", L)

The bubble_sort() function does not return any value because the sorting happens to the original list.

As show in the above example, nested for loops provides a much direct way of implementing the bubble sort algorithm, but we can also use nested while loops to achieve the same, as shown below.

with while loops

def bubble_sort(lst):

  i = 0
  while i <  len(lst):
    j = 0
    while j < len(lst)-1:
      if(lst[j]>lst[j+1]):
        lst[j], lst[j + 1] = lst[j + 1], lst[j]
      j += 1
    i += 1

L = [9, 7, 1, 2, 4, 1, 3, 0, 6, 5, 8]
bubble_sort(L)  
print("The sorted list is: ", L)

Optimized Implementation

The previous implementation of bubble sort has one avoidable performance inefficiency. This is because whether the list is already sorted, not sorted or reverse sorted, the algorithm still finishes with the worst-case running time of O(n²).

Note that if the algorithm moves through the entire list without performing the swap operation on any pair of elements, it means that the list is already sorted. We can, therefore, optimize bubble sort to avoid performing unnecessary comparisons by defining an intermediate variable to check whether a swap operation has taken place or not.

optimized bubble sort

def bubble_sort(lst):

  swapped = True
  c = 0
  while swapped == True:
    swapped = False
    for j in range(len(lst)-1):  
      
      if(lst[j]>lst[j+1]):
        lst[j], lst[j + 1] = lst[j + 1], lst[j] #swap the elements
        swapped = True
      c +=1
  return c

#sort a list
L = [9, 0, 2, 1, 0, 1, 100, -2, 8, 7, 4, 3, 2]

bubble_sort(L)  
print("The sorted list is: ", L)

Optimized bubble sort has a best case running time of O(n), this is is when the list is already in a sorted state. It still has an average and worst case running time of O(n²).

Bubble sort's space and time complexity

space complexity

Bubble sort has a space complexity of O(1) this is because no extra lists are used in its internal logic. The sorting happens directly on the input list without the use of intermediate lists.

Time complexity

The unoptimized version of bubble sort has a time complexity of O(n²) regardless of whether the input list is already sorted, not sorted or reverse sorted.

On the other hand, the time complexity cases of the optimized version are as highlighted below:

Best-O(n) - This happens when the input list is already sorted as we simply traverse through the list once.
Average-O(n²) - When the input list is not sorted and the elements are in arbitrary order.
Worst-O(n²) - When the input list is reverse sorted and, therefore, the swap operation happens with every comparison.

Selection sort in Python

Main — Sun, 14 Apr 2024 17:43:34 +0000

Selection sort is a simple comparison-based sorting algorithm. It is relatively inefficient compared to other sorting algorithms making it not suitable for sorting large sets of data. However, understanding how it works is a foundational step for understanding more sophisticated sorting algorithms and generally how sorting algorithms operates.

This algorithm has an average and worst time complexities of O(n²) where n is the number of elements in the array/list.

Selection sort works in-place meaning that it reorders the elements in the original list rather than creating a new list. This makes it memory-efficient.

Algorithm Description

In selection sort, an array/list is divided into two segments; the sorted segment on the left and the unsorted segment on the right. Initially, the sorted segment is empty while the unsorted segment consists of the entire list. At each step, the algorithm selects the smallest unsorted element and exchanges it with the first element of the unsorted segment. This gradually increases the size of the sorted segment while reducing that of the unsorted segment and eventually the entire list becomes sorted.

The algorithm can be achieved through the following steps:

Set MIN to position 0.
Find the smallest element in the list.
Swap it with the value at MIN.
Increment MIN.
Repeat steps 1-4 until the list is sorted.

Example

Consider if we start with the following unsorted list.

Elements in the sorted segment are in color green while those in the unsorted segment are in red.Two upper arrows will be used to indicate a swap operation.

At first step, the unsorted segment consists of the entire list. The MIN pointer is at the beginning of the list where the value is 4, the smallest value in the list is 0, so need to swap 4 and 0.

In the above step 0 and 4 are swapped. The sorted segment now contains a single element. In the next step, the smallest unsorted element is 1, so we need to swap it with the value at the second position which is 6.

And we go on like that with the next pairs i. 6 and 3.

The sorted segment is becoming larger while the unsorted segment is diminishing.

In the above step, 4 is already sorted so we just move to the next element.

And finally, after the last step, the list is now sorted.

Selection sort implementation

The selection sort algorithm can be implemented with nested loops.

with for loops

def selection_sort(lst):
  for i in range(len(lst)):
    smallest = i

    for j in range(i + 1, len(lst)):
      if lst[j] < lst[smallest]:
        smallest = j

    lst[i], lst[smallest] = lst[smallest], lst[i] #swap the elements

#sort a list
L = [99, 9, 0, 2, 1, 0, 1, 100, -2, 8, 7, 4, 3, 2]
selection_sort(L)

print("The sorted list is: ", L)

In the above implementation, the sorted segment of the list starts at 0 and ends at i while the unsorted segment starts at i + 1 and ends at n-1 where n is the length of the list.

The outer loop traverses through all elements of the list. While inner loop's only traverses the unsorted segment (beginning at i.e i + 1 ) , it finds the position of the smallest unsorted element and assigns it to the smallest variable. The smallest element is then swapped with the outer loops current value in the lst[i], lst[smallest] = lst[smallest], lst[i] statement.

with nested while loops

We can also implement the selection sort algorithm using nested while loops, as shown below:

def selection_sort(lst):
  i = 0
  while i < len(lst):

    smallest = i
    j = i + 1
    while j < len(lst):
      if lst[j] < lst[smallest]:
        smallest = j
      j += 1
    
    lst[i], lst[smallest] = lst[smallest], lst[i] #swap the elements
    i += 1

#sort a list
L = [99, 9, 0, 2, 1, 0, 1, 100, -2, 8, 7, 4, 3, 2]

selection_sort(L)
print("The sorted list is: ", L)

Descending selection sort

To make the selection sort algorithm to sort the elements in descending order, we simply need to change the sign from < to > in the comparison line i.e from if lst[j] < lst[smallest]: . to if lst[j] > lst[smallest]: .This is as shown below:

#descending selection sort
def selection_sort(lst):
  for i in range(len(lst)):
    smallest = i

    for j in range(i + 1, len(lst)):
      if lst[j] > lst[smallest]:
        smallest = j

    lst[i], lst[smallest] = lst[smallest], lst[i] #swap the elements

#sort a list
L = [99, 9, 0, 2, 1, 0, 1, 100, -2, 8, 7, 4, 3, 2]
selection_sort(L)

print("The sorted list is: ", L)

Complexity Analysis

space complexity

The selection sort algorithm has a space complexity of O(1) . This means that it is memory-efficient as it does extra extra memory except for holding the basic variables e.g smallest.

time complexity

The presence of nested loops in the selection sort algorithm implies that it has a time complexity of O(n²), this is for both average case and worst case scenarios.

Set methods in Python

Main — Sun, 07 Apr 2024 12:59:04 +0000

A set is an abstract data type that represents an unordered collection of unique elements.

Sets just like lists are mutable meaning that operations such as insertion and deletion can be performed on them in-place and without creating a new set.

In Python, sets are represented using the set type/class. This class defines a number of methods to support various operations on sets. The operations can be sub-divided into:

Elementary operations such as insertion, deletion, etc.
Set operations such as union, intersection, difference, etc .

Methods for Elementary operations

Set, like most data structures, supports basic operations such as Insertion and deletion. This is achieved through several methods defined in the set class.

`add()`

The add() method is used to add a single element to the set. It takes one parameter, which is the element to be added

myset.add(x)

`x`	The element to be added to the set.

Sets can only contain unique elements thus the operation will have no effect if the element already exists.

myset = {1, 2, 3}

#add some elements
myset.add(4)
myset.add(5)

#this has no effect because the elements exists.
myset.add(2)
myset.add(1)

print(myset)

`clear()`

The clear() method takes no argument, it removes all elements present in a set effectively turning it to an empty set.

myset.clear()

#a non-empty set
myset = {1, 2, 3, 4}

#remove all elements
myset.clear()
print(myset)

`copy()`

The copy() method is used to create a shallow copy of the set.This means that the method returns a new set object that contains all the elements of the original set but will not be affected if any changes are made to the original set.

The method takes does not take any arguments.

myset.copy()

The method returns a new set which is a shallow copy of the original set.

myset = {3, 5, 7}

copied = myset.copy()
print(copied)

`discard()`

The discard() method removes an element from the set if it is present. It does not raise an exception if the element is not present.

myset.discard(x)

`x`	The element to be removed.

myset = {1, 3, 5, 6, 7, 8, 9}

#remove an element
myset.discard(6)
myset.discard(8)

print(myset)

#no exception is raised if the element does not exist
myset.discard(10)

`pop()`

The pop() method removes and returns an arbitrary/random element from the set. It raises a KeyError if the set is empty.

myset.pop()

The method takes no arguments, it returns the removed arbitrary element.

myset = {0, 2, 4, 6, 8, 10}

#remove and return an arbitrary element
print(myset.pop())
print(myset.pop())
print(myset.pop())
print(myset.pop())

print(myset)

`remove()`

The remove() method just like discard() , removes an element from a set if it is a member. However, if the element is not present, remove() will raise a KeyError whereas discard() will not.

myset.remove(x)

`x`	The element to be removed.

The method removes element x from the set , it raises a KeyError exception if the element is not present.

myset = {1, 3, 5, 6, 7, 8, 9}

myset.remove(6)
myset.remove(8)
print(myset)

#raises an exception
myset.remove(10)

`update()`

The update() method is used to extend a set with elements from an iterable object. This means elements from the iterable that are not already present in the set will be added to the set.

myset.extend(iterable)

iterable An iterable object containing the elements to be added to the set.

myset = {1, 3, 5}

#The iterable with the elements
elements = [5, 7, 9, 11]

#add elements to the set
myset.update(elements)
print(myset)

Methods for set operations

Apart from the usual operations, sets also supports operations that are only unique to them. Such operations includes Union, intersection, Difference, etc.

In this part we will explore the various methods that are meant for performing set operations.

`difference()`

The difference() method returns the difference of two or more sets as a new set. The returned set contains only those items from the first set that are not present in the other sets.

set1.difference(set2 [,set3] [, set4], ...)

The method takes in arbitrary number of sets as arguments and returns a set with the elements of the original set(set1) which are not present in the input sets. Note that if multiple sets are given as inputs, they will be combined into one set before the operation.

set1 = {1, 3, 5, 7, 9, 11}
set2 = {3, 9, 13}
set3 = {7, 9, 11}

diff = set1.difference(set2, set3)
print(diff)

`difference_update()`

The difference_update() method is similar to the difference() method in that both returns those elements from one set that are not present in the other(s). However, the difference_update() method updates the original set by removing elements found in the second set rather than creating a new set.

set1.difference_update(set2 [,set3][, set4]...)

The method removes elements from set1 that are present in the input sets(set2, set3, etc).

set1 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
set2 = {0, 2, 4}
set3 = {6, 8}

set1.difference_update(set2, set3)
#elements are removed from the original set
print(set1)

`intersection()`

The intersection() method returns the intersection of two sets as a new set. This is a set that contains all the elements that are common between two given sets.

set1.intersection(set2 [,set3] [,set4]...)

The method returns elements that are common in both the original set and the input set.

set1 = {1, 2, 3, 4, 5}
set2 = {1, 3, 5, 7, 9}

result = set1.intersection(set2)
print(result)

`intersection_update()`

This method is just like the intersection() method except that it does not create a new set, instead, it updates the original set.

s1 = {1,2,3,4,5} 
s2 = {3,4,5,6,7} 
s1.intersection_update(s2)

print(s1)

`symmetric_difference()`

The symmetric_difference() method returns a new set with elements that are in either of the sets, but not in both.

set1.symmetric_difference(set2)

s1 = {'a', 'b', 'c', 5}
s2 = {3, 5, 7, 'c'}

result = s1.symmetric_difference(s2)
print(result)

`symmetric_difference_update()`

Just like symmetric_difference() except that it updates the original list rather than creating a new one.

set1.symmetric_difference_update(set2)

s1 = {'a', 'b', 'c', 5}
s2 = {3, 5, 7, 'c'}

s1.symmetric_difference_update(s2)
print(s1)

`isdisjoint()`

The isdisjoint() method in checks whether two sets have a common item or not. If there are common elements in sets, it returns False otherwise it will return True.

set1.isdisjoint(set2)

It returns True if there is no any common element between set1 and set2, otherwise False.

s1 = {'a', 'b', 'c'}
s2 = {1, 2, 3, 4}
s3 = {0, 2, 4}

print(s1.isdisjoint(s2))
print(s1.isdisjoint(s3))
print(s2.isdisjoint(s3))

issubset()

The issubset() method checks if all elements of a set are present in another set (passed as an argument).

set1.issubset(set2)

It returns True if all elements in set1 are present in set2, otherwise False.

evens = {0, 2, 4, 6, 8}
odds = {1, 3, 5, 7, 9}
digits = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}

print(evens.issubset(digits))
print(odds.issubset(digits))
print(evens.issubset(odds))

`issuperset()`

The issuperset() method checks whether the current set is a superset of the input set. That is if all the elements in the input set are contained within the current set.

set1.issuperset(set2)

The method returns True if all elements of set2 are in set1, otherwise False.

evens = {0, 2, 4, 6, 8}
odds = {1, 3, 5, 7, 9}
digits = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}

print(digits.issuperset(evens))
print(digits.issuperset(odds))
print(evens.issuperset(odds))

Instance, Class and Static methods in Python

Main — Sun, 07 Apr 2024 12:51:37 +0000

Methods are functions that are associated with a particular object or class. The three types of methods are :

Instance methods: These methods are associated with instances of a class and can access and modify the data within an instance.
Class methods: These methods are associated with a class rather than instances. They are used to create or modify class-level properties or behaviors.
Static methods: These are utility methods that do not have access to any object-level or class-level data.

Understanding the difference between the 3 types of methods will be crucial in ensuring that you write classes that are properly organized, efficient, easy to maintain and which are a close reflection of the real life objects they are being modeled after.

The following example shows how each of these methods are defined in a class. We will talk about the technical details in a while.

class Example:
    #define an instance method
    def method(self):
        Return "I am an instance method"
    
    #define a class method
    @classmethod
    def class_method(cls):
        return "I am a class method"
    
    #Define a static method
    @staticmethod
    def static_method():
        return "I am a static method"

Instance Methods

Instance methods are functions defined inside a class that perform operations on instances rather than the class itself.

If you have interacted with Python classes, it is likely that you have encountered and used instance methods. You can easily identify the methods by looking for the parameter self in the method definition.

#define the class
class Example:
    #Define an instance method
    def method(self):
        return "I am an instance method. I will only work when called by objects of this class!"

#create an object
e = Example()
#call an instance method
print(e.method())

Instance methods are able to access and modify an instance variables and data.

class Student:

   #Define the constructor
   def __init__(self, name, grade):
       self.name = name  
       self.grade = grade

   #define other instance methods
   def change_grade(self, new_grade):
       self.grade = new_grade 

   def print_info(self):
       print(f"{self.name} is in grade {self.grade}") 

s1 = Student("Bob", 9)

s1.print_info() 

s1.change_grade(10)

s1.print_info()

Note: Calling an instance method from the class itself will raise a TypeError.

#define the class
class Example:

    #Define an instance method
    def method(self):
        return "I am an instance method. I will only work when called by objects!"

#Try calling an instance method from the class itself. An error is raised!.
print(Example.method())

Instance methods cannot modify class level variables

Instance methods are only able to access and modify instance variables, which exist only within the scope of an instance of a class. As such, they cannot access or modify class level variables.

class Example:
   #Define a class level variable
   x = 10

   #The following method will modify the value of x at instance level rather than at class level
   def modify(self):
      self.x = 1000


print(Example.x)

e = Example()
e.modify()
print(Example.x)

Class Methods

Class methods are methods that are bound to a class rather than to objects. These methods can be called directly from the class itself as well as from the instances.

Class methods take cls as the first argument. The cls argument is a reference to the class, and is used to access class attributes and methods. It is analogous to the self argument for instance methods.

We use the @classmethod decorator to define a class method. The syntax is as follows:

@classmethod
def method_name(cls):
    #method body

Class methods operate on the class itself, rather than on an instances of the class. They are used to provide general functionality for objects of that particular class.

Consider the following example:

class Example:
   #Define a class level variable
   x = 10

   #The following method will modify the value at class level
   @classmethod
   def modify(cls, v):
      """Modify the value of the class level variable x with the new variable v"""
      cls.x = v


print(Example.x)

#Call class method from the class itself
Example.modify(100)
print(Example.x)

#call class method from an instance
e = Example()
e.modify(1000)
print(Example.x)

The following example shows how we can keep a count of all the active instances of a class using class method.

#Define the class
class Example:
   
   #The variable to keep the count
   count = 0

   def __init__(self):
      self.increase_count() #Call increas count each time a new object is created.
   
   @classmethod
   def increase_count(cls):
       """This method increases the global level variable, 'count' """
       cls.count +=1
  
   @classmethod
   def get_count(cls):
       return cls.count

#The following exampls demonstrate the methods at work.

print(Example.get_count())

e1 = Example()
print(Example.get_count())

e2 = Example()
e3 = Example()
print(Example.get_count())

e4 = Example()
e5 = Example()
print(e5.get_count())

Static methods

From the above discussions, instance methods operate on instances, while class method operate on the class itself.

Static methods, as the name suggests are just static. They belong to a class but the do not have access to class or instance variables. They are simply meant for providing utility services that are not class or instance specific.

Note: While instance method and class methods always take self, cls as their first arguments respectively. Static methods do not take any mandatory argument as the first argument. This is because they are not bound to either the class or instances and are simply called directly.

Static methods are defined using the @staticmethod decorator. The syntax is as follows:

@staticmethod
def method_name(params):
   #method body

class Example:

   @staticmethod
   def method():
      print("I am a static method.")

Example.method()

e = Example()
e.method()

As shown above, static methods can be called from the class itself as well as from the instances.

Consider if we have the class Rectangle, we can define a utility/static methods for calculating the area and the perimeter.

#define the class

class Rectangle:
   
   def __init__(self, w, l):
       self.width = w
       self.length = l

   #define some instance methods
   def area(self):
       """This method will call the static method 'calculate_area' """
       return self.calculate_area(self.width, self.length)

   def perimeter(self):
      """This method will call the static method 'calculate_perimeter' """
      return self.calculate_perimeter(self.width, self.length)

   #Define utilty methods that are accessible from the class as well as instances
   @staticmethod
   def calculate_area(w, l):
       return w * l

   @staticmethod
   def calculate_perimeter(w, l):
       return 2 * ( w + l)

#Use utility methods from the class
print(Rectangle.calculate_area(7, 4))
print(Rectangle.calculate_perimeter(7, 4))

#from instances
r = Rectangle(20, 30)
print(r.area())
print(r.perimeter())

r2 = Rectangle(100, 50)
print(r2.area())
print(r2.perimeter())

Summary

Instance methods operate at instance level. They take self as their first argument
Class methods operate at class level, they have access to class variables. They are defined using the @classmethod decorator. They take cls as the first argument.
Static methods are utility methods, they do not have access to class or instance variables. They are defined using the @staticmethod decorator and they do not take any mandatory first argument.

Forem: Main

dict.fromkeys() method in Python

Related articles

dict.setdefault() method in Python

Related articles

Implement Merge-Sort in python

Algorithm Description

Example

Merge sort implementation

Complexity analysis

Space complexity

Related articles

csv module in Python

Reading csv data

Writing csv data

Quoting behavior

csv dialects

Automatic dialect detection

Using named fields

csv.DictReader

csv.DictWriter

Related articles

items(), keys() and values() methods in Python dictionary

items() - Get all items present in a dictionary

keys() - get all keys of a dictionary

values() - get all values in the dictionary

Conclusion

Related articles

Linked list vs Array

Definitions

Insertion and Deletion

Arrays

Linked list

Accessing elements

Memory allocation and efficiency

Summary

Related articles

Insertion sort in Python

Algorithm Description

Insertion sort Example

Insertion sort implementation.

Descending insertion sort

Algorithm analysis

Applications of insertion sort

Related articles

Python Function Scope

Name Resolution, The LEGB Rule

The Global Statement

The nonlocal Statement

Related articles

Bubble sort in Python

Bubble sort Algorithm description

Direct Implementation

Optimized Implementation

Bubble sort's space and time complexity

space complexity

Time complexity

Related articles

Selection sort in Python

Algorithm Description

Example

Selection sort implementation

with nested while loops

Descending selection sort

Complexity Analysis

space complexity

time complexity

Related articles

Set methods in Python

Methods for Elementary operations

add()

clear()

copy()

discard()

pop()

remove()

update()

Methods for set operations

difference()

difference_update()

`csv.DictReader`

`csv.DictWriter`

`add()`

`clear()`

`copy()`

`discard()`

`pop()`

`remove()`

`update()`

`difference()`

`difference_update()`

`intersection()`

`intersection_update()`

`symmetric_difference()`

`symmetric_difference_update()`

`isdisjoint()`

`issuperset()`