# by default, only the result of the last expression in a cell is displayed after evaluation.
# the following forces display of *all* self-standing expressions in a cell.
from IPython.core.interactiveshell import InteractiveShell
InteractiveShell.ast_node_interactivity = "all"
Iteration simply refers to the process of accessing — one by one — the items stored in some container. The order of the items, and whether or not the iteration is comprehensive, depends on the container.
In Python, we typically perform iteration using the for loop.
# e.g., iterating over a list
l = [2**x for x in range(10)]
for n in l:
print(n)
1 2 4 8 16 32 64 128 256 512
# e.g., iterating over the key-value pairs in a dictionary
d = {x:2**x for x in range(10)}
for k,v in d.items():
print(k, '=>', v)
0 => 1 1 => 2 2 => 4 3 => 8 4 => 16 5 => 32 6 => 64 7 => 128 8 => 256 9 => 512
# e.g., iterating over a list
l = (2**x for x in range(10)) #generator items are not created until you need them
for n in l:
print(n)
1 2 4 8 16 32 64 128 256 512
iter, and next¶We can iterate over anything that is iterable. Intuitively, if something can be used as the source of items in a for loop, it is iterable.
But how does a for loop really work?
m = [2**x for x in range(10)]
#for n in l:
# print(n)
# it creates an iterator object
# repeatedly calls next on that iterator object until StopIteration exception is thrown
m
[1, 2, 4, 8, 16, 32, 64, 128, 256, 512]
myIter = iter(m) #__iter__
myIter
<list_iterator at 0x2592adb52b0>
myIter.__next__()
1
myIter.__next__()
2
myIter.__next__()
4
myIter.__next__()
8
myIter.__next__()
16
myIter.__next__()
32
myIter.__next__()
64
myIter.__next__()
128
myIter.__next__()
256
myIter.__next__()
512
myIter.__next__()
--------------------------------------------------------------------------- StopIteration Traceback (most recent call last) <ipython-input-19-fbfe836098d2> in <module> ----> 1 myIter.__next__() StopIteration:
class MyIterator:
def __init__(self, max):
self.max = max
self.curr = 0
# the following methods are required for iterator objects
def __next__(self):
if self.curr<self.max:
self.curr+=1
return self.curr
else:
raise StopIteration
def __iter__(self):
return self
it = MyIterator(5)
next(it)
1
next(it)
2
next(it)
3
next(it)
4
next(it)
5
next(it)
--------------------------------------------------------------------------- StopIteration Traceback (most recent call last) <ipython-input-27-bc1ab118995a> in <module> ----> 1 next(it) <ipython-input-20-8bc19cbf50b3> in __next__(self) 11 return self.curr 12 else: ---> 13 raise StopIteration 14 15 def __iter__(self): StopIteration:
it = MyIterator(10)
while True:
try:
print(next(it))
except StopIteration:
break
it = MyIterator(10)
for i in it:
print(i)
1 2 3 4 5 6 7 8 9 10
For a container type, we need to implement an __iter__ method that returns an iterator.
import numpy as np
class ArrayList:
def __init__(self): #constructor
self.data = np.empty(1, dtype=object) # new Object[1] of Null
# contains None
self.size = 0
# self.iteratorIndex=0 #only allows for one itertor
def append(self, value): # amortized O(1)
if self.size==len(self.data):
newArray = np.empty(2*len(self.data), dtype=object) # O(1)
# copy everything over
for i in range(0, self.size): #O(n) O(self.size) worst case
newArray[i]=self.data[i]
self.data=newArray
self.data[self.size]=value # best case O(1)
self.size+=1
def _normalize_idx(self, nidx): #helper function to translate a neg idx to pos idx
if nidx<0:
nidx+=self.size
if nidx<0:
nidx=0
return nidx
def __getitem__(self, idx): #assume valid 0<=idx<self.size
"""Implements `x = self[idx]`"""
assert(isinstance(idx, int))
idx = self._normalize_idx(idx) # now the idx is non-negative
if idx>=self.size:
raise IndexError()
return self.data[idx] #O(1) only on positive index
def __setitem__(self, idx, value): #assume valid 0<=idx<self.size
"""Implements `self[idx] = x`"""
assert(isinstance(idx, int))
idx = self._normalize_idx(idx) # now the idx is non-negative
if idx>=self.size:
raise IndexError()
self.data[idx]=value #O(1)
def __delitem__(self, idx): #assume valid 0<=idx<self.size #worst case O(n)
"""Implements `del self[idx]`"""
assert(isinstance(idx, int))
idx = self._normalize_idx(idx) # now the idx is non-negative
if idx>=self.size:
raise IndexError()
for i in range(idx+1,self.size): #first to move is idx+1, last to move is at self.size-1
self.data[i-1]=self.data[i]
self.data[self.size-1]=None
self.size-=1
def __len__(self):
"""Implements `len(self)`"""
return self.size
def __repr__(self):
"""Supports inspection"""
# [1, -4, 3] []
out="["
if self.size>0:
out=out+str(self.data[0])
for i in range(1, self.size):
out=out+", "+str(self.data[i])
out=out+"]"
return out
def __iter__(self): # for arraylist class
#only allows for one itertor
# if self.iteratorIndex<self.size:
# val=self.data[self.iteratorIndex]
# self.iteratorIndex+=1
# return val
# else:
# raise StopIteration
class ArrayListIterator:
def __init__(self, lst): #lst will be an ArrayList object
self.idx=0
self.theArrayList=lst
def __iter__(self):
return self # return a ArrayListIterator object
def __next__(self):
if self.idx<self.theArrayList.size:
val=self.theArrayList[self.idx]
self.idx+=1
return val
else:
raise StopIteration()
# this is the code that actually runs in the __iter__ for the arraylist class
return ArrayListIterator(self) # this self is an arraylist object
l = ArrayList()
for x in range(10):
l.append(2**x)
l
[1, 2, 4, 8, 16, 32, 64, 128, 256, 512]
it = iter(l) # this is calling the ArrayList __iter__
it
<__main__.ArrayList.__iter__.<locals>.ArrayListIterator at 0x1f224d2f850>
type(it)
__main__.ArrayList.__iter__.<locals>.ArrayListIterator
next(it)
1
next(it)
2
next(it)
4
next(it)
next(it)
next(it)
next(it)
next(it)
next(it)
8
16
32
64
128
256
next(it)
512
next(it)
--------------------------------------------------------------------------- StopIteration Traceback (most recent call last) <ipython-input-17-bc1ab118995a> in <module> ----> 1 next(it) <ipython-input-8-5231f4cd10d4> in __next__(self) 88 return val 89 else: ---> 90 raise StopIteration() 91 # this is the code that actually runs in the __iter__ for the arraylist class 92 return ArrayListIterator(self) # this self is an arraylist object StopIteration:
for x in l:
print(x)
1 2 4 8 16 32 64 128 256 512
yield¶What's a "generator"?
[2**x for x in range(5)]
[1, 2, 4, 8, 16]
_
[1, 2, 4, 8, 16]
g=(2**x for x in range(5))
for x in g:
print(x)
1 2 4 8 16
for x in g: #cannot reuse a generator once it runs out
print(x)
# a generator object is another type of iterator, any function with a "yield" statement
#instead of a "return" is a generator function
# when you call the function again, it continues after that previous yield
def foo():
yield 1
foo()
<generator object foo at 0x000001F225242E40>
g=foo()
next(g)
1
next(g)
--------------------------------------------------------------------------- StopIteration Traceback (most recent call last) <ipython-input-31-e734f8aca5ac> in <module> ----> 1 next(g) StopIteration:
def foo1():
print('one')
yield 1
print('two')
yield 2
print('three')
yield 3
h=foo1()
h
<generator object foo1 at 0x000001F225242D60>
next(h)
one
1
next(h)
two
2
next(h)
three
3
next(h)
--------------------------------------------------------------------------- StopIteration Traceback (most recent call last) <ipython-input-36-31146b9ab14d> in <module> ----> 1 next(h) StopIteration:
def foo2():
print('one')
yield 1
print('two')
yield 2
print('three')
yield 3
print('done')
m=foo2()
m
<generator object foo2 at 0x000001F2252336D0>
next(m)
one
1
next(m)
two
2
next(m)
three
3
next(m)
done
--------------------------------------------------------------------------- StopIteration Traceback (most recent call last) <ipython-input-45-8efa10874b95> in <module> ----> 1 next(m) StopIteration:
import numpy as np
class ArrayList:
def __init__(self): #constructor
self.data = np.empty(1, dtype=object) # new Object[1] of Null
# contains None
self.size = 0
# self.iteratorIndex=0 #only allows for one itertor
def append(self, value): # amortized O(1)
if self.size==len(self.data):
newArray = np.empty(2*len(self.data), dtype=object) # O(1)
# copy everything over
for i in range(0, self.size): #O(n) O(self.size) worst case
newArray[i]=self.data[i]
self.data=newArray
self.data[self.size]=value # best case O(1)
self.size+=1
def _normalize_idx(self, nidx): #helper function to translate a neg idx to pos idx
if nidx<0:
nidx+=self.size
if nidx<0:
nidx=0
return nidx
def __getitem__(self, idx): #assume valid 0<=idx<self.size
"""Implements `x = self[idx]`"""
assert(isinstance(idx, int))
idx = self._normalize_idx(idx) # now the idx is non-negative
if idx>=self.size:
raise IndexError()
return self.data[idx] #O(1) only on positive index
def __setitem__(self, idx, value): #assume valid 0<=idx<self.size
"""Implements `self[idx] = x`"""
assert(isinstance(idx, int))
idx = self._normalize_idx(idx) # now the idx is non-negative
if idx>=self.size:
raise IndexError()
self.data[idx]=value #O(1)
def __delitem__(self, idx): #assume valid 0<=idx<self.size #worst case O(n)
"""Implements `del self[idx]`"""
assert(isinstance(idx, int))
idx = self._normalize_idx(idx) # now the idx is non-negative
if idx>=self.size:
raise IndexError()
for i in range(idx+1,self.size): #first to move is idx+1, last to move is at self.size-1
self.data[i-1]=self.data[i]
self.data[self.size-1]=None
self.size-=1
def __len__(self):
"""Implements `len(self)`"""
return self.size
def __repr__(self):
"""Supports inspection"""
# [1, -4, 3] []
out="["
if self.size>0:
out=out+str(self.data[0])
for i in range(1, self.size):
out=out+", "+str(self.data[i])
out=out+"]"
return out
def __iter__(self): # for arraylist class
for idx in range(self.size):
yield self.data[idx]
l = ArrayList()
for x in range(5):
l.append(2**x)
l
[1, 2, 4, 8, 16]
for x in l:
print(x)
1 2 4 8 16