Home

Features:

• Columnar-storage

• Compressed with the Dictionary or Run-Length Encoding (RLE) when the column has duplicate values

  • Dictionary suits for repetitive categorical data, e.g., music genres

  • RLE suits for Data with long sequences of the same value, e.g., consecutive 'Open' or 'Closed' for stores

• Small size

• Metadata stores schema

• Strong Data Integrity

• Support nested data structure

Storage:

1. Row Groups: each row group contains a set of rows for each column

2. Column Chunks: each column within a row group is stored in a "chunk"

3. Encoding and Offsets: Dictionary or Run-Length Encoding (RLE)

4. Metadata: describes the structure of the data, including the schema and the encoding used for each column

5. Reconstruction During Reading: the process above reverses

A Simple Metadata Examples:

• Unordered, no index

• Unique Elements

• Heterogeneous, can contain integers, strings, tuples and so on at the same time

• Immutable Elements, can not be changed but can be added or removed

• Not require contiguous memory, hash table structure (an array of 'buckets')

• Use cases:

  • membership testing

  • remove duplicates

  • operations, like unions | , intersection & , difference - , symmetric difference ^ , issubset( ), isdisjoint( )

my_set = {1, "hello", (2, 3)} #integer, string and tuple
another_set = set([4, 5, 6]) #set function converts a list into a set

# add elements
my_set.add(4)

# remove elements
my_set.remove(4)

# membership testing, O(1)
2 in my_set

# set operations
union_set = my_set | another_set

• 0-based Indexing, access elements by their position with `[ ]`

• Heterogeneous Data contain different data types, including other tuples, lists, and dictionaries

• Immutable Tuple, once a tuple is created, elements of it can not be added, changed, or removed, but elements themselves can be modified if they are mutable objects

• Contiguous Memory

• Use cases

  • Return values in function

  • Immutable Data Collection

  • Represent a row with columns as elements for databases

  • Dictionary keys

my_tuple = ([1, 2], "hello")
my_tuple[0].append(3)
print(my_tuple) # Output: ([1, 2, 3], "hello")

# tuples without parentheses
another_tuple = 1, 2, 3

# single-element tuples
single_element_tuple = (1,)

# complicated tuples
book = (
     {"title": "1984", "author": "George Orwell", "publication_year": 1949},  
     ["Dystopian", "Political Fiction", "Social Science"],                
     (True, "John Doe")                                                      
      )

#Accessing book information
print(f"Title: {book[0]['title']}")
print(f"Author: {book[0]['author']}")
print(f"Genres: {', '.join(book[1])}")
print(f"Is Borrowed: {'Yes' if book[2][0] else 'No'}")

• Created using the array class from array module

• 0-Based Indexing

• Homogeneous, the type of elements is determined by a type code i

• Mutable, can modify the elements, append, or remove

• Contiguous Memory

• Store the data values themselves in the contiguous block (memory efficient)

• Use case

  • large numeric datasets

  • binary I/O operation

from array import array
int_array = array('i', [1, 2, 3])

print(int_array)
# Output is array('i', [1, 2, 3, 4, 5])

# access elements with index
print(int_array[0])
# Output is 1

# add new element
int_array.append(4)
print(int_array)
# Output is array('i', [1, 2, 3, 4, 5, 4])

• Support Multidimensional Indexing, access elements using a comma-separated tuple of indices

• Homogeneous, the same data type (improve efficiency)

• Mutable, modifying elements or reshaping it

• Contiguous Memory, is a fixed size determined at the time of creation

• Use case

  • Matrix Computation

  • Scientific Computing

  • Linear Algebra

  • Large datasets

import numpy as np
# create a 2D array (matrix)
matrix = np.array([[1, 2, 3], [4, 5, 6], [7, 8, 9]])

# access elements with index
row2_column3 = matrix[1, 2]

# change the elements
matrix[1, 2] = 20

# matrix computation
matrix_a = np.array([[1, 2], [3, 4]])
matrix_b = np.array([[5, 6], [7, 8]])
matrix_sum = np.add(matrix_a, matrix_b)

# Matrix multiplication
matrix_product = np.dot(matrix_a, matrix_b)

• 0-based Indexing and slicing
• Multidimensional List
• Heterogeneous Data Types
• Mutable
• Dynamic resizing and memory overhead (e.g., append remove insert pop )
• Concatenation (+) and Repetition (*)
• Sorting and Reversing

#Creating a list and adding elements
my_list = [1, 2, 3]
my_list.append(4)  # Add at the end
my_list.insert(1, 'a')  # Insert at index 1

#Accessing elements
print("First element:", my_list[0])  # Access first element

#Modifying elements
my_list[2] = 'b'  # Change the element at index 2

#Removing elements by value and by index
my_list.remove('a')  # Remove the first occurrence of 'a'
popped_element = my_list.pop(2)  # Remove and return the element at index 2

#Slicing
sublist = my_list[1:2] # Elements from index 1

#Concatenation and repetition
another_list = ['a', 'b']
con_list = my_list + another_list
rep_list= my_list * 3

#Sorting and reversing
my_list.reverse()
con_list.sort(key=str) # Convert all elements to strings


# Multidimensional list
matrix = [[1, 2, 3], [4, 5, 6], [7, 8]]

• A blueprint for creating objects

• Group data (Class attributes and Instance attributes) and functions (methods)

• Each method in a class must have self as its first parameter, which refers to the instance of the class

• Create an instance from the defined class, my_solution = Solution( )

#how to use class and methods included
#Create an instance of Solution, which is my_solution
my_solution = Solution()
result = my_solution.My_Method("abc", "pqr")
print(result)

The common tool is print(), especially for the loop, it is easy to check the changes in each loop

VSCode Debugger is a powerful tool to check the program flow:

Step 1: Install Python Extention to enhance the RUN AND DEBUG feature

Step 2: Open the folder and create a 'launch.json' file for future customisation

• breakpoint: where to pause the execution

  • Debug Cell (More near Execute Cell icon)

  • 

  • 

• The following sequence is Continue, Step Over, Step Into, Step Out, Restart, Disconnect

  • Continue: continue execution of this line until the end of the code cell
  • Step Over: execute this line of code then pause execution at the next line of code
  • Step Into: dive into this line of code and see details like what functions this line of code borrowed from other places in the same cell
  • Step Out: jump out from the function inside and back to the main
  • Restart: restart the debugging
  • Disconnect: end the debugging

Data is saved as 1 and 0 (i.e., the binary system) in a computer

• BIT (BINARY DIGIT): The smallest unit, i.g., 1 or 0

• Bytes: = 8 BITS, i.g., 01011011

• KB (KILOBYTE): =1,024 BYTES i.g., space for around 1/3 Page of Text

• MB (MEGABYTE): = 1,024 KB, i.g., space for 1 book, 1 photo, 1 minute of music

• GB (GIGABYTE): = 1,024 MB

• TB (Terabytes): = 1,024 GB

• ...

The number of values that BIT can represent is 2^ (the number of BITS) - 1

• O( ) the possible longest runtime

• Ω( ) the possible shortest runtime

• Selection Sort: go through all numbers, find the smallest number then swap the left of searching with the smallest number O(n^2) Ω(n^2)

• Bubble Sort: compare the numbers which two are close to each other, then make sure the smaller one is on the left and the larger one is on the right O(n^2) Ω(n)

• Merge Sort: divide the whole into two halves, sort the two halves, and then merge the two halves by comparing numbers from the smallest of the two, the key is to divide the cohort into two halves recursively until the recursively half only has one number O(n log n) Ω(n log n)

Hexadecimal is a base-16 number system

0 1 2 3 4 5 6 7 8 9 A B C D E F

• Hexadecimal is like a shorthand for binary, 1111 means F
• Add 0x before when it represents a memory address, e.g., for an integer, 0x7ffc3a7cffbc
• Color Code #FFFFFFF means Red 255 Blue 255 Green 255

The pointer is the address of data in memory

int main() {
    // A regular integer variable
    int var = 10;    
    // A pointer variable that can hold the address of an int
    int *ptr;
    // Store the address of var in ptr
    ptr = &var;
    
    // Prints the value of var
    printf("Value of var: %d\n", var);
    // Prints the memory address of var 
    printf("Address of var: %p\n", &var);
    // Prints the memory address stored in ptr 
    printf("Value of ptr: %p\n", ptr); 
    // Dereferences ptr and prints the value of var  
    printf("Value pointed to by ptr: %d\n", *ptr);
    return 0;
}

• Linear Data Structure
• Same Data Type
• Value means actual data, Index means relative location, starts from 0

• Fixed Size - Occupy the consecutive memory

  • Specify the number of elements the array will have

  • int arr[3]

• Single Pointer

//C code
#include <stdio.h>

int main() {
   int arr[3] = {10, 20, 30};
   
   // Pointer to the first element of arr
   int *ptr = arr;
   
   for(int i = 0; i < 3; i++) {
      
       // Accessing array elements using pointer arithmetic
       printf("%d ", *(ptr + i)); 
   }
   return 0;
}