CITS2200 - Lecture 2

← Back to Home

CITS2200 - Lecture 1
Objects & Arrays in Python - Slides cont.

Arrays

• An array is a group of memory locations that store related variables

Each memory location in an array is 2 bytes → called a cell

• Strings could be stored in the array because they are 2-bytes in size
  We use ASCII to represent characters
• But integers cannot as they are 4 bytes
  • Thus we store the address that points to the integer in memory

→ Arrays should not store data directly, instead store a memory address
See: Referential Array

The benefit of using fixed sized for each memory location in an array, is that we can calculate the index of a location:
e.g. if we have an array $A$, and the location of $A[i]$ is byte $j$, we can calculate the byte number of location $A[i+4]$ by the simple calculation $j+2\ast 4$

---

Referential Arrays in Python - Slides

Referential Array

• A referential array stores the reference of each object in the array
  • The actual objects are stored in other parts of memory

Lists

• Lists are the most important data structure in Python
  • They are implemented through arrays in Python
  • Lists are referential arrays
• Lists are mutable $-$ you can add or append objects

Remember: lists only store references for each object!

Compact Arrays

• Strings are stored as compact arrays not as referential arrays in Python
  • As said before, strings are compact enough to store within a cell
• The characters in a string are stored in the array instead of a reference
  • Therefore, these arrays are immutable

Compact arrays have the advantage of using less memory as we do not need to create an additional reference for the string

Dictionaries

• A dict is a special kind of list where each member is a pair of elements called a mapping

Example: {'ga': 'Irish', 'de': 'German'}

Dynamic Arrays

When we create an array, what would happen if we needed to add items to it later (i.e. we run out of space)? We have two options:

1. Allocate a large amount of memory anticipating it will be used
2. Re-allocate memory when needed to store new objects

The first option leads to large amounts of memory wastage

• There is no guarantee that memory will be used

How would the second option work? Assume we add a new item:

• We can allocate more memory elsewhere to store the larger array
• Then copy the references from the old array to the new location
  Why? $-$ the memory in the old location may be filled with other pieces of data meaning there would be no room to expand our array
• This unfortunately increases the time for the program to run

Computational Complexity Theory

Reducing memory usage has the trade-off of increasing time (reducing program speed) and vice-versa. There is an entire branch of computer science that looks at this time-space trade-off and aims to optimise it.

There is a difference between what you, as the programmer sees, versus what is really happening → this is known as abstraction
e.g. when we initialise an array, how much memory does Python allocate knowing it creates additional items?

You can see how Python allocates memory for a referential array here

---

CITS2200 - Lecture 3