Python Summary

Posted on | Post modified:
Words count in article: 1.5k | Reading time ≈ 9

Python Summary

A brief summary of Python, including some basic foundations.

immutable and mutable variable

There are two kinds of variables in Python which are immutable and mutable variable. As for immutable variables, some common type like int, float, string, tuple and set. And in terms of mutable variables, it includes dict and list.

We can not change the elements in immutable variables : 

1
2
3
sample_sentence = "This is a sentence"
sample_sentence[2] = '5'
>>> TypeError: 'str' object does not support item assignment

However, we can modify the mutable variables : 

1
2
3
4
sample_list = ['This', 'is', 'a', 'sentence']
sample_list[2] = 'A'
print(' '.join(sample_list))
>>> This is A sentence

According to this feature of the two above kind of vairables, we can use them in the parameters in functions. There's no return statement in the function, but the original list has been modified since the list type is mutable, and the reference is delivered in Python : 

1
2
3
4
5
6
7
def test_func(sample):
    sample[2] = 'A'

sample_list = ['This', 'is', 'a', 'sentence']
test_func(sample_list)
print(' '.join(sample_list))
>>> This is A sentence

As for the immutable variables, the situation is not similar with the above function. Since the type string is immutable, Python will create a new variable to store the parameters and copy the value of the original variables : 

1
2
3
4
5
6
7
8
def test_func(sample):
    sample = list(sample)
    sample[2] = 'A'

sample_sentence = 'This is s sentence'
test_func(sample_sentence)
print(sample_sentence)
>>> This is a sentence

Collective Data Types

Set

A data type for representing a collection of unique, unordered items.

Creating set

  • An empty set: a_set = set()

  • A set with a number of items: a_set = {"one", 2}

  • Build a set from a list: a_set = set([1, 2, 2, 3])

Adding new items to a set

  • Syntax: a_set.add('c')

Removing items from a set

  • remove(): accept one argument indicating the item to be removed; raise KeyError if the item does not exist

  • discard(): similar to remove(); does not raise KeyError if item does not exist

  • pop(): select an arbitrary item to remove and return it

  • clear(): remove all the items from a set in place

Set operations

  • Union: a_set.union(b_set), a_set | b_set

  • Intersection: a_set.intersection(b_set), a_set & b_set

  • Difference: a_set.difference(b_set), a_set - b_set

  • Symmetric difference: a_set.symmetric_difference (b_set), a_set ^ b_set

Dictionary

A mapping data type that associates a key with a value, keys must be immutable types; values can be of any data type, 3ach data item is represented as key:value.

Creating dictionary

  • An empty dictionary: a_dict = {} or a_dict = dict()

  • A dictionary with a number of items: a_dict = {'one':1, 'two':2}

  • Build a dictionary from a list of tuples: a_dict = dict([('a',1), ('b',1)])

Adding new items to a dictionary

  • Syntax: a_dict[new_key] = new_value

  • If new_key presents in the dictionary, the existing value associated to this key is updated to new_value

Removing items from a dictionary

  • Syntax: del a_dict[a_key]

Checking for a key in a dictionary

  • Syntax: a_key in a_dict or a_key not in a_dict

File Operation

The open(file, mode) function will open the specific file in the specific mode : open mode

Open modes for file writing :

  • open(file_handle, 'w'): overwrite the existing content of the output file with the new content

  • open(file_handle, 'a'): append the new content at the end of the output file

Writing lines to a file : * file_handle.write(the_line): write one line at a time to the file

Reading line by line : 

1
2
3
4
5
6
7
8
9
10
with open(file, 'a') as file_handle:
    lines = file_handle.readlines()
    for line in lines:
        print(line)
        
with open(file, 'a') as file_handle:
    line = file_handle.readline()
    while line:
        print(line)
        line = file_handle.readline()

Simple Stack

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Stack:
    def __init__(self):
        self.the_stack = []
        self.count = 0
        self.top = -1
        
    def __len__(self):
        return self.count
    
    def is_empty(self):
        return len(self) == 0
    
    def push(self, item):
        self.the_stack.append(item)
        self.count += 1
        self.top += 1
        
    def pop(self):
        assert not self.is_empty(), "Can not pop from an empty stack"
        item = self.the_stack[self.top]
        del self.the_stack[self.top]
        self.count -= 1
        self.top -= 1
        
        return item
    
    def peek(self):
        assert not self.is_empty(), "Can not peek from an empty stack"
        item = self.the_stack[self.top]
        
        return item

Simple Queue

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Queue:
    def __init__(self):
        self.the_queue = []
        self.count = 0
        self.front = 0
        self.rear = -1
        
    def __len__(self):
        return self.count
    
    def is_empty(self):
        return len(self) == 0
    
    def append(self, item):
        self.the_queue.append(item)
        self.count += 1
        self.rear += 1
    
    def serve(self):
        assert not self.is_empty(), "Can not serve from an empty queue"
        item = self.the_queue[self.front]
        del self.the_queue[self.front]
        self.count -= 1
        self.front += 1
        
        return item

Queue with capacity : 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Queue:
    def __init__(self, size):
        self.the_queue = [0] * size
        self.count = 0
        self.front = 0
        self.rear = len * (self.the_queue) - 1

    def __len__(self):
        return self.count

    def is_empty(self):
        return len(self) == 0
    
    def is_full(self):
        return len(self) == len(self.the_queue)
    
    def append(self, item):
        assert not self.is_full(), "Can not append to a full queue"
        self.rear += (self.rear + 1) % len(self.the_queue)
        self.the_queue[self.rear] = item
        self.count += 1

    def serve(self):
        assert not self.is_empty(), "Can not serve an empty queue"
        item = self.the_queue[self.front]
        del self.the_queue[self.front]
        self.front = (self.front + 1) % len(self.the_queue)
        self.count -= 1
        
        return item

Random Module

  • random(): return a random floating point number in the range [0.0, 1.0)

  • randint(a, b): return a random integer in the range [a, b]

Simple Search Algorithms

Linear Searching

1
2
3
4
5
def linear(target):
    for x in list_1:
        if x == target:
            return True
        return False

  • Best case: 1 operation

  • Worst case: n operations

Binary Seacrching

Time complexity: \(O(logn)\)

1
2
3
4
5
6
7
8
9
10
11
12
13
def binary(target):
    list_2.sort()
    low = 0
    high = len(list_2) - 1
    while low <= high:
        mid = (low + high) // 2
        if list_2[mid] == target:
            return True
        elif list_2[mid] < target:
            high = mid - 1
        else:
            low = mid + 1
    return False

Simple Sorting Algorithms

Bubble Sort

Time complexity: \(O(n^2)\) 

1
2
3
4
5
6
7
8
def bubble_sort(the_list):
    for i in range(len(the_list) - 1):
        for j in range(len(the_list) - i - 1):
            if the_list[j] > the_list[j+1]:
                temp = the_list[j]
                the_list[j] = the_list[j+1]
                the_list[j+1] = temp
    return the_list

Selection Sort

Time complexity: \(O(n^2)\) 

1
2
3
4
5
6
7
8
9
10
11
12
def selection_sort(the_list):
    for i in range(len(the_list) - 1):
        smallest = i
        for j in range(i, len(the_list)):
            if the_list[j] < the_list[smallest]:
                smallest = j
        
        temp = the_list[i]
        the_list[i] = the_list[smallest]
        the_list[smallest] = temp
    
    return the_list

Insertion Sort

Time complexity: \(O(n^2)\) 

1
2
3
4
5
6
7
8
9
10
def insertion_sort(the_list):
    for i in range(1, len(the_list)):
        current = the_list[i]
        pos = i
        while pos > 0 and the_list[pos-1] > current:
            the_list[pos] = the_list[pos-1]
            pos -= 1
        the_list[pos] = current
    
    return the_list

Testing

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
def calculate_GPA(grade_list):
    total_sum = 0.0
    gpa = 0.0
    
    for grade in grade_list:
        if grade.upper() == "A":
            total_sum += 4.0
        elif grade.upper() == "B":
            total_sum += 3.0
        elif grade.upper() == "C":
            total_sum += 2.0
        elif grade.upper() == "D":
            total_sum += 1.0
        elif grade.upper() == "F":
            total_sum += 0.0
        else:
            return -1

    gpa = float(total_sum / len(grade_list))
    return gpa

import unittest

class TestForGPA(unittest.TestCase):
    def test_calculate(self):
        self.assertEqual(calculate_GPA(['A','A','A']), 3.0)
       
test = TestForGPA()
suite = unittest.TestLoader().loadTestsFromModule(test)
unittest.TextTestRunner().run(suite)

[out]
F
======================================================================
FAIL: test_calculate (__main__.TestForGPA)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "<ipython-input-32-0f3c215f8395>", line 7, in test_calculate
    self.assertEqual(calculate_GPA(['A','A','A']), 3.0)
AssertionError: 4.0 != 3.0
----------------------------------------------------------------------
Ran 1 test in 0.001s
FAILED (failures=1)

Exception Handling

1
2
3
4
5
6
7
8
9
try:
    input_handle = open('simple_file.txt','r')
except FileNotFoundError:
    print('File not found')
else:
    pass
finally:
    import sys
    sys.exit()

Recursion

1
2
3
4
5
6
7
8
9
10
11
12
13
def rec_binary_search(the_list, target):
    if len(the_list) == 0:
        return False
    mid = len(the_list) // 2
    
    if the_list[mid] == target:
        return True
    elif the_list[mid] < target:
        smaller_list = the_list[:mid]
        rec_binary_search(smaller_list, target)
    else:
        smaller_list = the_list[mid+1:]
        rec_binary_search(smaller_list, target)

Merge Sort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
def merge_sort(the_list):
    n = len(the_list)
    if n > 1:
        mid = n // 2
        left = the_list[:mid]
        right = the_list[mid:]
        
        merge_sort(left)
        merge_sort(right)
        
        i = 0    # left list
        j = 0    # right list
        k = 0    # main list
        
        while i < len(left) and j < len(right):
            if left[i] <= right[j]:
                the_list[k] = left[i]
                i += 1
            else:
                the_list[k] = right[j]
                j += 1
            k += 1
            
        while i < len(left):
            the_list[k] = left[i]
            i += 1
            k += 1
            
        while j < len(right):
            the_list[k] = right[j]
            j += 1
            k += 1
        
        print(the_list)

Quick Sort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
def quick_sort(the_list):
    first = 0
    last = len(the_list) - 1
    quick_sort_aux(the_list, first, last)
    
def quick_sort_aux(the_list, first, last):
    if first < last:
        partition_point = partitioning(the_list, first, last)
        
        quick_sort_aux(the_list, first, partition_point - 1)
        quick_sort_aux(the_list, partition_point + 1, last)
        

def partitioning(the_list, first, last):
    pivot_value = the_list[first]
    left_index = first + 1
    right_index = last
    
    complete = False
    
    while not complete:
        while left_index <= right_index and the_list[left_index] <= pivot_value:
            left_index += 1
            
        while right_index >= left_index and the_list[right_index] >= pivot_value:
            right_index -= 1
            
        if right_index < left_index:
            complete = True
        else:
            temp = the_list[left_index]
            the_list[left_index] = the_list[right_index]
            the_list[right_index] = temp
        
    temp = the_list[first]
    the_list[first] = the_list[right_index]
    the_list[right_index] = temp
        
    return right_index
0%