Sequences are quite possibly the most widely used data structure in programming. This article will give an overview on how to use them. We will use the Fibonacci sequence to demonstrate these concepts, since they are also quite a popular interview question, hopefully this will make these concepts easy to remember. In this article we will focus on lists and generators, however the same methods can be used for dictionaries.
First recall how we usually access elements of a list in Python
mylist = [1, 2, 3, 4, 5]
mylist[0]
# 1
mylist[1:4]
# [2,3,4]
mylist[-1]
#5
Let's begin with a simple object that contains the first 10 Fibonacci numbers.
class Fib10:
def __init__(self):
self.fibs = [1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
Say we wanted to be able to access the elements within this class the way we typically do with lists in Python. Trying this with an instance of our Fib10 class results in the following:
f = Fib10()
f[1]
'''
TypeError: 'Fib10' object is not subscriptable
'''
If you ever see the TypeError: object is not subscriptable exception, the reason why is that a special method has not be included in the class.
Therefore if we want to be able to access elements in the typical way there are a few methods we will need to implement.
__getitem__ Method.
Below we define a __getitem__ method which returns the elements based on the given slice_ we pass through to the method. First let's see how this method works with Python's built in list objects.
mylist = [1, 2, 3, 4, 5]
mylist.__getitem__(0) == mylist[0]
#True
mylist.__getitem__(slice(2,5)) == mylist[2:5]
# True
Our our Fibonacci class. We also implement the __len__ method to allow us to call the len() keyword on an instance of our object.
class Fib10:
def __init__(self):
self.fibs = [1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
def __getitem__(self, slice_):
return self.fibs[slice_]
def __len__(self):
return len(self.fibs)
f = Fib10()
f[0]
# 1
f[-1]
# 55
f[:4]
f[:4]
# [1,1,2,3]
Since we have the __len__ method defined in our class we can also loop through all the elements using a common looping technique.
for i in range(len(f)):
print(f[i], end= ' ')
'''
1 1 2 3 5 8 13 21 34 55
'''
__setitem__ Method
Recall that with normal lists in Python we can set an element in a list using the following syntax:
mylist = [1, 2, 3, 4, 5]
mylist[1] = 10
print(mylist)
#[1, 10, 3, 4, 5]
mylist[:1] = [5,6]
print(mylist)
#[5, 6, 10, 3, 4, 5]
Behind the scenes Python is using the following:
mylist = [1, 2, 3, 4, 5]
mylist.__setitem__(1, 10)
print(mylist)
#[1, 10, 3, 4, 5]
mylist.__setitem__(slice(0,1), [5,6])
print(mylist)
#[5, 6, 10, 3, 4, 5]
In our case we probably don't want to be able to be able to allow setting the Fibonacci numbers, but clearly in many cases we will want it. But we can implement the method and add a custom error message if someone tries to set values in the way discussed above.
class Fib10:
def __init__(self):
self.fibs = [1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
def __len__(self):
return len(self.fibs)
def __getitem__(self, slice_):
return self.fibs[slice_]
def __setitem__(self, slice_, values):
raise TypeError("Not allowed to modify the Fibonacci Numbers")
So although this is a very contrived example, hopefully this demonstrates the ability for us to customize the behavior of our code.
Nth Fibonacci Number
Obviously we probably wouldn't want to only have the first 10 Fibonacci numbers in an object. Let's take a look at a function from the Python docs for calculating the nth Fibonacci number. We will use the LRU cache here as it will make the code run faster. This method can be imported from Python's built-in library functools. We will use this method to demonstrate how to implement some important methods.
from functools import lru_cache
@lru_cache()
def fib(n):
if n < 2:
return n
else:
return fib(n-1) + fib(n-2)
for i in range(1,11):
print(fib(i), end = ' ')
'''
1 1 2 3 5 8 13 21 34 55
'''
We will use this function in the objects below to demonstrate the implementation of the iterator protocol in Python.
__next__ & __iter__ Methods
Let's recall what the next and iter keywords actually do in Python.
l = iter([1,2,3,4,5])
print(next(l))
for i in range(4):
print(next(l))
'''
1
2
3
4
5
'''
If we were to try to call next(l) again we would get a StopIteration exception. This is because generators consume the variables in the iterator. After running the commands above, try to run list(l) and notice the fact that it is now an empty list. This is known as an iterator becoming exhausted.
Iterator Protocol on Class
Let's use the Fibonacci function we created and implement the iterator protocol (__next__ and __iter__). We have set this fib function to be a static method. Notice below that all we need for __iter__ is to return self.
class Fibonacci:
def __init__(self, n):
self.n = n
self.i = 0
def __iter__(self):
return self
def __next__(self):
if self.i >= self.n:
raise StopIteration('Exhausted!!!')
fib_i = Fibonacci.fib(self.i)
self.i += 1
return fib_i
@staticmethod
@lru_cache(maxsize=None)
def fib(n):
if n < 2:
return n
else:
return Fibonacci.fib(n-1) + Fibonacci.fib(n-2)
Let's see what we can do with the class now.
1) Call next on our object.
f = Fibonacci(100)
for i in range(100):
print(next(f), end=' ')
Out:
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040 1346269 2178309 3524578 5702887 9227465 14930352 24157817 39088169 63245986 102334155 165580141 267914296 433494437 701408733 1134903170 1836311903 2971215073 4807526976 7778742049 12586269025 20365011074 32951280099 53316291173 86267571272 139583862445 225851433717 365435296162 591286729879 956722026041 1548008755920 2504730781961 4052739537881 6557470319842 10610209857723 17167680177565 27777890035288 44945570212853 72723460248141 117669030460994 190392490709135 308061521170129 498454011879264 806515533049393 1304969544928657 2111485077978050 3416454622906707 5527939700884757 8944394323791464 14472334024676221 23416728348467685 37889062373143906 61305790721611591 99194853094755497 160500643816367088 259695496911122585 420196140727489673 679891637638612258 1100087778366101931 1779979416004714189 2880067194370816120 4660046610375530309 7540113804746346429 12200160415121876738 19740274219868223167 31940434634990099905 51680708854858323072 83621143489848422977 135301852344706746049 218922995834555169026
2) Return list of first n Fibonnaci numbers
This is very simple to do, note that the class above will return an iterator object, as discussed at the beginning of this section. To convert it to a list we can just convert the iterator to a list using the list keyword.
Generate a list of the first 100 Fibonnaci numbers
3) Iterate through the object
for fib in Fibonacci(10):
print(fib, end = ' ')
'''
0 1 1 2 3 5 8 13 21 34
'''
Let's add the ability to get an item within the sequence, this requires implementing the __getitem__ method we discussed previously. Notice we set the list of Fibonaccis to None in the constructor, and only call on it if we request an item by indexing. Let's say we want to retrieve every 3rd , 6th and 10th Fibonacci number from the sequence up to a given value.
from functools import lru_cache
class Fibonacci:
def __init__(self, n):
self.n = n
self.i = 0
self.fibs_list = None
def __len__(self):
return self.n
def __iter__(self):
return self
def __getitem__(self, slice_):
if self.fibs_list:
print('returning from list in memory')
return self.fibs_list[slice_]
else:
print('generating fibonnacis for the first time')
self.fibs_list = list(Fibonacci(self.n))
return self.fibs_list[slice_]
def __next__(self):
if self.i >= self.n:
raise StopIteration('finished')
fib_i = Fibonacci.fib(self.i)
self.i += 1
return fib_i
@staticmethod
@lru_cache(maxsize=None)
def fib(n):
if n < 2:
return n
else:
return Fibonacci.fib(n-1) + Fibonacci.fib(n-2)
f = Fibonacci(100)
s1 = slice(0, 100, 3)
f[s1]
s2 = slice(0,100,6)
f[s2]
s3 = slice(0,100,10)
f[s1]
Notice that we only calculate the Fibonnacis once and then on further slices we simply retrieve the items from the list we created in the constructor.
__contains__ Method
To demonstrate this concept we are going to check whether a number is a member of the Fibonacci sequence
You may be familiar with using the in method in Python generally to check whether a variable is a member of a list. Let's say we want to be able to check whether a number of a member of the Fibonaccis up to and including n. Actually we can already Use the in method on our class. See the example below
from functools import lru_cache
class Fibonacci:
def __init__(self, n):
self.n = n
self.i = 0
self.fibs_list = None
def __len__(self):
return self.n
def __iter__(self):
return self
def __getitem__(self, slice_):
if self.fibs_list:
print('returning from list in memory')
return self.fibs_list[slice_]
else:
print('generating fibonnacis for the first time')
self.fibs_list = list(Fibonacci(self.n))
return self.fibs_list[slice_]
def __next__(self):
print('__next__ called')
if self.i >= self.n:
raise StopIteration('finished')
fib_i = Fibonacci.fib(self.i)
self.i += 1
return fib_i
@staticmethod
@lru_cache(maxsize=None)
def fib(n):
if n < 2:
return n
else:
return Fibonacci.fib(n-1) + Fibonacci.fib(n-2)
33 in Fibonacci(10)
5 in Fibonacci(10)
Since the __contains__ method is not implemented, Python is calling the __next__ to check whether it exists. The problem with this is that it will become exhausted unless we instantiate a new object each time we want to check whether a number is in the sequence.
Out:
__next__ called
__next__ called
__next__ called
__next__ called
__next__ called
__next__ called
__next__ called
__next__ called
__next__ called
__next__ called
__next__ called
True
Of course we could just convert the iterator to a list and then check whether an item is a member. Let's take an example of that, we will check and time how long it takes to calculate whether the first 1 million positive integers are members of the Fibonacci sequence.
from functools import lru_cache
import time
class Fibonacci:
def __init__(self, n):
self.n = n
self.i = 0
self.fibs_list = None
def __len__(self):
return self.n
def __iter__(self):
return self
def __getitem__(self, slice_):
if self.fibs_list:
print('returning from list in memory')
return self.fibs_list[slice_]
else:
print('generating fibonnacis for the first time')
self.fibs_list = list(Fibonacci(self.n))
return self.fibs_list[slice_]
def __next__(self):
if self.i >= self.n:
raise StopIteration('finished')
fib_i = Fibonacci.fib(self.i)
self.i += 1
return fib_i
@staticmethod
@lru_cache(maxsize=None)
def fib(n):
if n < 2:
return n
else:
return Fibonacci.fib(n-1) + Fibonacci.fib(n-2)
l = list(Fibonacci(1000))
%timeit [num in l for num in range(1_000_000)]
The results are given below. Note that we aren't even including the computation time it took to generate the first 1000 Fibonacci numbers and the computation is still rather slow. Which can be annoying in real projects.
7.9 s ± 53.3 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
How can we use the __contains__ method to fix this problem?
Well since the using in with a set is so much faster, perhaps we want to ensure that Python checks a set object as opposed to a list when checking the elements of a list. We can also store this set within the object so we only need to call the set once and then check whether the number passed in to __contains__ is an element of the set. Again we only compute this set if the in keyword is called on our object.
from functools import lru_cache
class Fibonacci:
def __init__(self, n):
self.n = n
self.i = 0
self.fibs_list = None
self.fibs_set = None
def __len__(self):
return self.n
def __iter__(self):
return self
def __getitem__(self, slice_):
if self.fibs_list:
print('returning from list in memory')
return self.fibs_list[slice_]
else:
print('generating fibonnacis for the first time')
self.fibs_list = list(Fibonacci(self.n))
return self.fibs_list[slice_]
def __next__(self):
if self.i >= self.n:
raise StopIteration('finished')
fib_i = Fibonacci.fib(self.i)
self.i += 1
return fib_i
@staticmethod
@lru_cache(maxsize=None)
def fib(n):
if n < 2:
return n
else:
return Fibonacci.fib(n-1) + Fibonacci.fib(n-2)
def __contains__(self, fib_n):
if self.fibs_set == None:
self.fibs_set = set(Fibonacci(self.n))
return fib_n in self.fibs_set
else:
return fib_n in self.fibs_set
f = Fibonacci(1000)
%timeit [num in f for num in range(1_000_000)]
Notice how much faster this is compared to the previous method. Since sets are not subscriptable we will still keep the list of Fibonaccis but ensure that when in is called we only use sets for performance reasons.
204 ms ± 3.12 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
This is a good example of using OOP to customize objects to suit our needs.
Summary
- __getitem__ and __setitem__ are analogous to the getter and setter which were discussed in the properties section .
- __iter__ and __next__ are known as the iterator protocol when implemented in a class.
- We can do a lot of customization to suit the use case by learning about these items. Notice the increase in performance for our final Fibonacci example.
Suggested Exercises to Check Knowledge
- Create a class for both both the squares and cubes which takes parameter n and returns a list of the squares/cubes.