Basic built-in types

Roles

  • list: Stores an ordered, mutable (changeable), and indexed collection of elements.

  • tuple: Stores an ordered, immutable (unchangeable), and indexed collection of elements.

  • dict: Stores a key-value pair collection that is ordered (insertion order since Python >=3.7), mutable, and indexed by unique hashable keys.

  • set: Stores an unordered collection of unique hashable elements (duplicates are not allowed).

  • string: Stores a sequence of characters used to represent and store text-based ordered, immutable (unchangeable), and indexed data.

Main methods

List

Tuple

Dict

Set

append() \(O(1)\)

count() \(O(n)\)

clear() \(O(1)\)

add() \(O(1)\)

clear() \(O(n)\)

index() \(O(n)\)

copy() \(O(n)\)

clear() \(O(n)\)

copy() \(O(n)\)

fromkeys() \(O(n)\)

copy() \(O(n)\)

count() \(O(n)\)

get() \(O(1)\)

difference() \(O(|s|)\)

extend() \(O(k)\)

items() \(O(n)\)

difference_update() \(O(|s|)\)

index() \(O(n)\)

keys() \(O(n)\)

discard() \(O(1)\)

insert() \(O(n)\)

pop() \(O(1)\)

intersection() \(O(\min(|s|, |t|))\)

pop() \(O(1), O(n)\)

popitem() \(O(1)\)

intersection_update() \(O(\min(|s|, |t|))\)

remove() \(O(n)\)

update() \(O(n)\)

isdisjoint() \(O(\min(|s|, |t|))\)

reverse() \(O(n)\)

values() \(O(n)\)

issubset() \(O(|s|)\)

sort() \(O(n \log n)\)

issuperset() \(O(|s|)\)

pop() \(O(1)\)

remove() \(O(1)\)

union() \(O(|s| + |t|)\)

update() \(O(|t|)\)

The time complexity notation means for a problem of size \(n\):

  • \(O(1)\): Constant time

  • \(O(n)\): Linear time

  • \(O(n \log n)\): Log-linear time

  • \(|s|\): set size

Looping tips

  • To get the index when iterating over a sequence use enumerate.

  • To iterate simultaneously on two sequences, use zip.

  • To iterate over a dict use the items method.

  • Never modify a dict or a set by adding or discarding elements while looping over it, however, you can change values.

Exercise (easy)

  1. what would be the most appropriate standard structure to store and query student number (unique int) - grade (int) data in order to efficiently find a given student grade, add or remove a student?

  2. what issue can you anticipate if the data is now name (str) - grade (int)?

  3. how would you check if an entry student number - grade has been entered for a given student? Make sure your proposals work even if the student is not present. What is the best solution if one is also interested in the student’s grade? Write the code and test it.

  4. can one use a tuple of ints as a dict key or in a set, what about a list of ints? Why?

Correction

  1. ‘efficiently’ suggests that the number of students might be large. Student numbers are unique and hashable (they can act as keys). A dict {student_number: grade, ...}̀ is appropriate: query / add / remove in constant time.

  2. A name, even though it could act as a key, is not unique. Adding a new student with the same name would result in the loss of the initial student grade.

  3. src
    1def is_graded(student: int, grades: dict[int, int]) -> bool:  # best
2    grade = grades.get(student)
3    return grade is not None
    src
    1def get_student_grade(student: int, grades: dict[int, int]) -> int | None:
2    return grades.get(student)
    tests
    1def test_is_graded_present() -> None:
2    grades: dict[int, int] = {0: 10, 1: 11}  # later, fixtures will be used
3    student: int = 0
4    assert is_graded(student, grades)
    tests
    1def test_is_graded_absent() -> None:
2    grades: dict[int, int] = {0: 10, 1: 11}  # later, fixtures will be used
3    student: int = 2
4    assert not is_graded(student, grades)
    tests
    1def test_get_student_grade_present() -> None:
2    grades: dict[int, int] = {0: 10, 1: 11}  # later, fixtures will be used
3    student: int = 0
4    grade: int = 10
5    assert get_student_grade(student, grades) == grade
    tests
    1def test_get_student_grade_absent() -> None:
2    grades: dict[int, int] = {0: 10, 1: 11}  # later, fixtures will be used
3    student: int = 2
4    assert get_student_grade(student, grades) is None

  4. Yes, because it is hashable. No for the opposite reason.

Exercise (intermediate)
student_group_graph

Example of a student group repartition

Students (int) belong to project groups (int). A group is constituted of at least one student. Each student belongs to at least one group.

  1. what structure would you suggest to efficiently both query all students belonging to a given group and if a given student belongs to a given group?

  2. then, how would you obtain a structure which gives you the groups to which every student belongs? Write the code and test it.

  3. how would you test if a group has no student in common with an other group?

Correction

  1. ‘efficiently’ suggests that the number of students and groups might be large. A dict of sets {group: {student_number_0, ...}, ...}̀ allows to first get the students of a group as a set in constant time, and then check the presence of a student in constant time.

  2. src
     1def inverse_to_group_affiliation_of_students(
 2    student_composition_of_groups: dict[int, set[int]],
 3) -> dict[int, set[int]]:  # later, improvement of type hinting
 4    """from a dict[group, students], tranpose to dict[student: groups]"""
 5    group_affiliation_of_students: dict[int, set[int]] = {}
 6    for group, students in student_composition_of_groups.items():
 7        for student in students:
 8            if student not in group_affiliation_of_students:
 9                # later, improvement defaultdict
10                group_affiliation_of_students[student] = set()
11            group_affiliation_of_students[student].add(group)
12    return group_affiliation_of_students
    tests
     1def test_inverse_to_group_affiliation_of_students() -> None:
 2    student_composition_of_groups: dict[int, set[int]] = {
 3        0: {10, 11},
 4        1: {10, 12},
 5    }  # later, fixtures will be used
 6    obtained = inverse_to_group_affiliation_of_students(student_composition_of_groups)
 7    expected: dict[int, set[int]] = {
 8        10: {0, 1},
 9        11: {0},
10        12: {1},
11    }
12    assert obtained == expected

  3. A possibility:

    src
     1def has_no_common_student_between_groups(
 2    groups: list[int], student_composition_of_groups: dict[int, set[int]]
 3) -> bool:
 4    """add in a set the students from several groups,
 5    if there is no student in common between any group,
 6    then the size of the set is the sum of the size of every group"""
 7    sum_group_sizes: int = 0
 8    students_merged: set[int] = set()
 9    for group in groups:
10        students: set[int] = student_composition_of_groups[group]
11        sum_group_sizes += len(students)
12        students_merged |= students
13    return len(students_merged) == sum_group_sizes
    tests
     1def test_no_student_in_common_between_groups_true() -> None:
 2    student_composition_of_groups: dict[int, set[int]] = {
 3        0: {10, 11},
 4        1: {12},
 5    }  # later, fixtures will be used
 6    groups: list[int] = [0, 1]
 7
 8    obtained = has_no_common_student_between_groups(
 9        groups, student_composition_of_groups
10    )
11    expected = True
12    assert obtained == expected
    tests
     1def test_no_student_in_common_between_groups_false() -> None:
 2    student_composition_of_groups: dict[int, set[int]] = {
 3        0: {10, 11},
 4        1: {10, 12},
 5    }  # later, fixtures will be used
 6    groups: list[int] = [0, 1]
 7
 8    obtained = has_no_common_student_between_groups(
 9        groups, student_composition_of_groups
10    )
11    expected = False
12    assert obtained == expected