Set, Dictionary, JSON

Agenda

Brief intro to time complexity
- Understand why we need sets and dictionaries
Set
Dictionary
JSON

We started by discussing different types of data objects, both non-scalar (such as lists, tuples, dictionaries, and sets) and scalar (integers, logicals, floats)
I think we have also covered many of the foundation components in programming including branching (using if-elif-else statements) to implement code depending on different conditions, iterations (using for loop and while loop as well comprehension) to handle repetitive tasks, and functions and modules to make our script more manageable and efficient
Today we will be focused on two other non-scalar, iterable objects, which are sets and dictionaries
We will start with discussing the concept of time complexity and how it relates to why we would choose to use sets or dictionaries as opposed to lists or tuples although there are other important reasons to prioritize the former to the latter data types

Time Complexity

What is time complexity?

Originals from computer science
As the size of input grows, how does time behave?
Used to evaluate the efficiency of an algorithm

Time Complexity

Time complexity of operations with different data objects

Need to understand how objects are represented in memory
For instance, list:
- Ordered objects are stored one after another
- 0 -> 1 -> 2 -> 3 (start from 0, go one by one)

Time Complexity

Check whether an item is in the list (with in operator)

Looks through all items one by one from the start
- ‘apple’ is not ‘cherry’
- ‘orange’ is not ‘cherry’
- ‘cherry’ is ‘cherry’, stop, return True
Could have gone until end of the list.

Time Complexity

By default we think of the worst case scenario

So we look at upper limit
Assume the length of the list is n
In the worst-case scenario, the item being searched for is not present

Time Complexity

Big O notation

Denoted O( )
- See Big O notation for more detailed information
Big O notation describes the behavior of an algorithm as the size of input grows
O(n) means when input size doubles, triples, etc., time will grow linearly too (linear time)
O(1) (constant time), O(n²) (quadratic time), O(2ⁿ) (exponential time), etc.
Then, what is the time complexity of finding an item in a list?

Set

Properties of sets

Sets store unique elements—no duplicates
Sets do not order items
Use hashing to efficiently store and retrieve elements
- Hashing, through a hash function, maps elements to positions in memory
- See here for more on hashing
Great for look-ups and other operations (e.g., deletion)

With this in mind, let’s first have a look at the key properties of sets, which I think we did discuss briefly in one of the previous classes
First of all, sets do not allow duplicates and thus they have unique elements
Also, there is no order in sets, and thus indexing/slicing are unavailable
More importantly in today’s discussions, sets use hashing to efficiently store and retrieve elements
We will not get into the details of how hashing works but we can think of hashing as assigning elements to unique positions in memory so they can be found quickly, much like organizing books in a library
Specifically, when you store an element in a set, the set uses what is called “hash function” that calculates a unique hash code for the element and places it in a specific location in memory according to the hash code.
This allows you to access or delete the element quickly, without needing to search through the entire set (which is actually what lists do)
Hashing makes sets efficient for look-ups and other operations, because instead of scanning everything, you jump straight to the right spot based on the element’s hash code

Set

Checking whether an item is in a set

Always takes the same time
Does not depend on set size
O(1) (constant time in Big O notation)

Set

Time spent searching for 10ⁿ+1 in a list/set whose length is 10ⁿ

Set

Creating a set

Created with curly braces

Empty set is created with set()

Set

Let’s see how an item is searched from a set

E.g., create a set of individuals banned from flight

Set

Say John wants to buy a ticket

We can actually check the hash values

Set

Will only check the relevant memory location

List

It will check the list one by one, till the end if necessary

Set

Indexing/slicing

What will it return?

Set

Indexing/slicing

The order in which we supply the items does not matter for internal representation

Set

Methods

To add an element to a set, .add() an element to a set (without re-assignment)

Set

Methods

If we add again, it will not change anything (duplicates not allowed)

Set

Methods

union() will return the union of the two sets

But does not update the original set

Set

Methods

The update() method would both take the union and update original

Set

Methods

difference() will return the difference (no update though)

Original set still includes ‘Ali’

Set

Methods

difference_update() will actually modify the original set

Set

Methods

intersection() and intersection_update() work similarly
Check out this link for more

Set

Comprehension

Similar to list comprehension
Use curly braces {}
- Absence of key:value will make it a set
Unique letters in a string
An example

Set

Comprehension

Another example

Dictionary

Dictionaries are made up of key: value pairs

Naturally they are useful for storing associative data, where each key is associated with a specific value
Created with curly braces:

Dictionary

Initialize an empty dictionary with { }

Alternatively

Dictionary

Access the value using the key

E.g., salary['Jane']

Dictionary

But dictionaries are not quite indexable/sliceable

A way to get around this (rely on .items())

Dictionary

Assign new values to existing key (mutable)

Dictionary

Create new entry

Check if new entry is there

Dictionary

We could achieve the same functionality with two lists as long as those are stored in correct order (but not quite efficient)

Person	Grade
Ali	A+
Bella	A+
Rose	A
Sam	B+

Dictionary

An example

What’s Rose’s grade?

Dictionary

Time complexity

This is, again, time inefficient
Takes O(n) time
Dictionary takes the constant time, O(1)
Dictionary has unique, unordrered keys (just like set)

Dictionary

Methods

Let’s create one

Dictionary

Methods

Get all keys in the dictionary

Dictionary

Methods

Get all the values

Dictionary

Methods

Get all the pairs

Dictionary

Iterating over a dictionary

Will automatically iterate over keys if not specified (e.g., using grades.values())

Dictionary

Iterating over a dictionary

We can also iterate over pairs

Or, without the parentheses

Dictionary

Test if key in dictionary with in operator

Dictionary

Operations

Remove item from dictionary

Check grades

Alternatively

Dictionary

Nested dictionaries

E.g., science fictions

Dictionary

Nested dictionaries

E.g., science fictions

Dictionary

Nested dictionaries

E.g., science fictions
- Use PrettyPrinter function in pprint module
- For more on pprint see here

Dictionary

Nested dictionaries

Indexing/slicing

Dictionary

Dictionary methods

Check out the full list of dictionary methods here

Dictionary

Comprehension

Dictionary comprehension: the same thing, except the first part is a key:value pair

Dictionary

Comprehension

Combine two lists into a dictionary without dictionary comprehension

Dictionary

Comprehension

Another way, but still without dictionary comprehension
Use zip() function

Dictionary

Comprehension

With dictionary comprehension

Dictionary

Comprehension

We can add conditions with if-else block
Condition on key:

Condition on value:

Dictionary

Comprehension

What does it do?

JSON

JavaScript Object Notation

A file format that stores structured data in a simple and readable way
Very popular for exchanging data with web servers
Let’s see an example of Twitter here

JSON

JSON is built on two main data structures

A collection of key/value pairs ('object')
An ordered sequence of items ('array')
Makes it a very natural way of storing
- Dictionaries
- Lists

JSON

Python has built-in json module

json.loads() creates a dictionary or list by from a string

JSON

Python has built-in json module

Python reads this in as a dictionary/list

JSON

Python has built-in json module

Again, json.loads() creates a dict or a list from a string (not from a file)
From a string (thus the s)

JSON

Python has built-in json module

json.loads() creates a dict or a list from a string (not from a file)
From a string (thus the s)

JSON

Whether JSON will be read as dict or list depends on content

If it is structured in {}, it’ll be a dictionary
If it is structured in [], it’ll be a list
Of course, it can be any combination of things:
- A dictionary where values are a list
- A list of dictionaries
- Any different combinations or nesting of these
- This is what makes it very flexible

JSON

json.dumps() turns a dictionary/list as a string (thus the s)

JSON

json.dump() writes a dictionary/list to a JSON file

JSON

json.load() reads a JSON file as a dictionary/list

JSON

Dumps and loads

json.dumps(): turn a Python object into a JSON string
json.loads(): turn a JSON string back into a Python object

JSON

Dump and load

json.dump(): turn a Python object and write JSON into a file
json.load(): turn a JSON string back into a Python object