# 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
for i in range(5):
print (i)
0 1 2 3 4
m=range(5)
it = iter(m)
while True:
try:
print (next(it))
except StopIteration:
break
0 1 2 3 4
it
<range_iterator at 0x1e147826bd0>
next(it)
--------------------------------------------------------------------------- StopIteration Traceback (most recent call last) <ipython-input-5-bc1ab118995a> in <module> ----> 1 next(it) StopIteration:
m=range(5)
it = iter(m)
for i in it:
print(i)
0 1 2 3 4
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?
l = [2**x for x in range(10)]
class MyIterator: # counter up to max
def __init__(self, max): # constructor with max value for the counter
# start at one
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-17-bc1ab118995a> in <module> ----> 1 next(it) <ipython-input-10-f98967dd99f2> in __next__(self) 12 return self.curr 13 else: ---> 14 raise StopIteration 15 16 def __iter__(self): StopIteration:
it = MyIterator(10)
while True:
try:
print(next(it))
except StopIteration:
break
1 2 3 4 5 6 7 8 9 10
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 # ArrayList copied from previous lecture
class ArrayList:
def __init__(self):
self.data = np.empty(1, dtype=object)
self.size = 0
def append(self, value):
"""Appends value to the end of this list."""
if self.size == len(self.data):
nsize = 2 * len(self.data)
ndata = np.empty(nsize, dtype=object)
for i in range(len(self.data)):
ndata[i] = self.data[i]
self.data = ndata
self.data[self.size] = value
self.size += 1
def _normalize_idx(self, idx):
nidx = idx
if nidx < 0:
nidx += self.size
if nidx < 0:
nidx = 0
return nidx
def __getitem__(self, idx):
"""Implements `x = self[idx]`"""
assert(isinstance(idx, int))
idx = self._normalize_idx(idx)
if idx >= self.size:
raise IndexError()
return self.data[idx]
def __setitem__(self, idx, value):
"""Implements `self[idx] = x`"""
assert(isinstance(idx, int))
idx = self._normalize_idx(idx)
if idx >= self.size:
raise IndexError()
self.data[idx] = value
def __delitem__(self, idx):
"""Implements `del self[idx]`"""
assert(isinstance(idx, int))
idx = self._normalize_idx(idx)
if idx >= self.size:
raise IndexError()
for i in range(idx+1, len(self.data)):
self.data[i-1] = self.data[i]
self.data[len(self.data)-1]=None
self.size -= 1
def __len__(self):
"""Implements `len(self)`"""
return self.size
def __repr__(self):
"""Supports inspection"""
value='['
for i in range(self.size):
value+=str(self.data[i])
if i<self.size-1:
value+=', '
value+=']'
return value
def __iter__(self): # iter(on an arraylist)
class ArrayListIterator:
def __init__(self, lst):
self.currentIndex=0
self.theList=lst
def __next__(self):
if self.currentIndex < self.theList.size:
value=self.theList[self.currentIndex]
self.currentIndex+=1
return value
else:
raise StopIteration
def __iter__(self):
return self
return ArrayListIterator(self)
# calling constructor sending it the Arraylist
l = ArrayList()
for x in range(10):
l.append(2**x)
it = iter(l) # create an ArrayListIterator object
type(it)
__main__.ArrayList.__iter__.<locals>.ArrayListIterator
next(it)
1
next(it)
--------------------------------------------------------------------------- StopIteration Traceback (most recent call last) <ipython-input-40-bc1ab118995a> in <module> ----> 1 next(it) <ipython-input-21-e807681aaa5b> in __next__(self) 77 return value 78 else: ---> 79 raise StopIteration 80 def __iter__(self): 81 return self StopIteration:
for x in l:
print(x)
1 2 4 8 16 32 64 128 256 512
yield¶What's a "generator"?
f=[2**x for x in range(5)] #list comprenhension, memory is used for 5 values
g=(2**x for x in range(5))
# generator comprehension, values are not created until needed
for i in f:
print (i)
for i in g:
print (i)
1 2 4 8 16 1 2 4 8 16
f
g
[1, 2, 4, 8, 16]
<generator object <genexpr> at 0x000001E14A3DEB30>
next(g)
--------------------------------------------------------------------------- StopIteration Traceback (most recent call last) <ipython-input-44-e734f8aca5ac> in <module> ----> 1 next(g) StopIteration:
%timeit 1024 in [2**x for x in range(100)]
%timeit 1024 in (2**x for x in range(100))
31.3 µs ± 2.23 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each) 2.99 µs ± 180 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
def foo(): # any function with yield statements is a generator function
print('spot1')
yield 1
print('spot2')
yield 2
print('spot3')
yield 3
g=foo()
next(g)
spot1
1
next(g)
spot2
2
next(g)
spot3
3
next(g)
--------------------------------------------------------------------------- StopIteration Traceback (most recent call last) <ipython-input-50-e734f8aca5ac> in <module> ----> 1 next(g) StopIteration:
import numpy as np # ArrayList copied from previous lecture
class ArrayList:
def __init__(self):
self.data = np.empty(1, dtype=object)
self.size = 0
def append(self, value):
"""Appends value to the end of this list."""
if self.size == len(self.data):
nsize = 2 * len(self.data)
ndata = np.empty(nsize, dtype=object)
for i in range(len(self.data)):
ndata[i] = self.data[i]
self.data = ndata
self.data[self.size] = value
self.size += 1
def _normalize_idx(self, idx):
nidx = idx
if nidx < 0:
nidx += self.size
if nidx < 0:
nidx = 0
return nidx
def __getitem__(self, idx):
"""Implements `x = self[idx]`"""
assert(isinstance(idx, int))
idx = self._normalize_idx(idx)
if idx >= self.size:
raise IndexError()
return self.data[idx]
def __setitem__(self, idx, value):
"""Implements `self[idx] = x`"""
assert(isinstance(idx, int))
idx = self._normalize_idx(idx)
if idx >= self.size:
raise IndexError()
self.data[idx] = value
def __delitem__(self, idx):
"""Implements `del self[idx]`"""
assert(isinstance(idx, int))
idx = self._normalize_idx(idx)
if idx >= self.size:
raise IndexError()
for i in range(idx+1, len(self.data)):
self.data[i-1] = self.data[i]
self.data[len(self.data)-1]=None
self.size -= 1
def __len__(self):
"""Implements `len(self)`"""
return self.size
def __repr__(self):
"""Supports inspection"""
value='['
for i in range(self.size):
value+=str(self.data[i])
if i<self.size-1:
value+=', '
value+=']'
return value
def __iter__(self): # iter(on an arraylist)
# generator function implementation
for i in range(self.size):
yield self.data[i]
l = ArrayList()
for x in range(5):
l.append(3**x)
for x in l: # calls __iter__ which returns a generator function
# which works with next
print(x)
1 3 9 27 81