Array-Based Sequences Flashcards
examples of Python’s built-in ‘sequence’ classes
list, tuple, str
memory address
(an abstraction) computer system keeps track of what information is stored in each byte - each byte of mem associated w/ unique number
RAM
(how computer’s main memory performs) each byte of memory can be efficiently accessed regardless of address
array
group of related variables stored 1 after another in contiguous portion
why each cell of array uses same number of bytes?
can access in constant time (based on index): appropriate memory address —–>
start + cellsize*index
referential arrays
stores consecutive sequences of memory addresses at which elements of sequence reside (lists & tuples) - rel size of indiv ele’s may vary, but bits used to store mem addr’s is fixed
compact arrays
stores the bits that represent the primary data
advantages of compact over referential arrays
- overall memory lower (no overhead devoted to explicit storage of seq of mem ref’s)
- primary data stored consecutively in memory (not case w/ referential)
dynamic array
can change precise size of array (ie. list)
low-level array
size of array must be explicitly declared (cannot expand into subsequent cells)
why tuples more memory efficient than lists
immutable - no need for an underlying dynamic array w/ surplus capacity
shallow copy
references the SAME elements (with immutable ele’s, point is moot)
deep copy
has NEW elements (deepcopy function from copy module)
extend method for lists
receives ref’s to the ele’s (not copies of the ele’s)
amortization/amortized analysis
many simple, efficient op’s for each expensive op (ie. list append method exhibits amortized constant-time behavior)
