# 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: #using the python iterator on a list
print(n)
1 2 4 8 16 32 64 128 256 512
m = l.__iter__()
m.__next__()
1
m.__next__()
m.__next__()
m.__next__()
m.__next__()
2
4
8
16
m.__next__()
m.__next__()
m.__next__()
m.__next__()
32
64
128
256
m.__next__()
m.__next__()
m.__next__()
m.__next__()
512
--------------------------------------------------------------------------- StopIteration Traceback (most recent call last) <ipython-input-11-508b71cb7ac2> in <module> 1 m.__next__() ----> 2 m.__next__() 3 m.__next__() 4 m.__next__() StopIteration:
#for n in l: #using the python iterator on a list
# print(n)
m=l.__iter__()
while True:
try:
print (m.__next__())
except StopIteration:
break
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)
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: # an iterator used to count from 1 up to max
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)
--------------------------------------------------------------------------- StopIteration Traceback (most recent call last) <ipython-input-21-bc1ab118995a> in <module> ----> 1 next(it) <ipython-input-14-f55b03084da0> in __next__(self) 11 return self.curr 12 else: ---> 13 raise StopIteration 14 15 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
class ArrayList:
def __init__(self): # constructor in python
# default arraylist size is 1 element
self.data = np.empty(1, dtype=object) # array variable name is "data"
self.size = 0 # how many items have been addded to the arrayList
# also tells us where to put the next item
# not the same as len(self.data)
# myList = ArrayList() calls __init__
def append(self, value):
# how do we append an item after the last item in the arraylist
# just put the item at the next index position
# if not fit, make a bigger array, copy over, then append
if self.size<len(self.data): # O(1)
self.data[self.size]=value
self.size+=1
else: # iteration needed for copy, slow
# options to make one larger, but then every append
# needs to do a O(self.size) copy of items O(n)
# instead assume more appends are coming, and make array much larger
# so this one append is slow, but future appends are fast
# accepted larger is twice as big
newArray = np.empty(len(self.data)*2, dtype=object)
# iterate over all the items in self.data
# copy them to same position in newArray
for i in range(len(self.data)):
newArray[i]=self.data[i]
newArray[self.size]=value
self.size+=1
self.data=newArray
def __getitem__(self, idx):
"""Implements `x = self[idx]`"""
assert(isinstance(idx, int))
# later implement error checking is idx valid (0 to self.size-1)
# later also support negative idx
# if they give us a valid index
idx=self.normalize_idx(idx) # correcting negative index
if idx<0 or idx>=self.size:
raise IndexError()
return self.data[idx]
def __setitem__(self, idx, value):
"""Implements `self[idx] = x`"""
# if they give us a valid index
assert(isinstance(idx, int))
self.data[idx]=value
def __delitem__(self, idx):
"""Implements `del self[idx]`"""
assert(isinstance(idx, int))
# don;t erase it or cross it out, don;t leave a hole
# move the items after the deleted item, up one
# shifting items
# if they give us a valid index
for i in range(idx, self.size-1): #len(self.data)
# i is the position we are moving to
#i+1 is the position we are moving from
self.data[i]=self.data[i+1]
self.data[self.size-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 normalize_idx(self, idx):
# error checking on out of range will be in get, set, del, insert
# will be done in those methods
# here we just fix the negative index
# corrects index from -1 to -N
# to index N-1 to 0
# we cannot do range checking here, because insert allows N as a valid index
newIdx=idx
if newIdx<0:
newIdx+=self.size
# what if newIdex is still negative?
# what if user gives -2N
# change the if to a while and get newIdx from 0 to N-1
# OR if still negative, set newIdx to 0
if newIdx<0:
newIdx=0
return newIdx
def __iter__(self): #this self is the arraylist selfA
# start of class definition
class ArrayListIterator:
def __init__(self, lst): #this self is the ArrayListIterator selfB
self.theList=lst
self.theIndex=0
# the following methods are required for iterator objects
def __iter__(self):
return self
def __next__(self):
if self.theIndex<self.theList.size:
self.theIndex+=1
return self.theList[self.theIndex-1]
else:
raise StopIteration()
# end of class definition
#create an ArrayListIterator and return it
return ArrayListIterator(self) #send if the ArrayList selfA
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)
type(it)
__main__.ArrayList.__iter__.<locals>.ArrayListIterator
next(it)
1
next(it)
next(it)
next(it)
next(it)
2
4
8
16
next(it)
next(it)
next(it)
next(it)
32
64
128
256
next(it)
next(it)
next(it)
next(it)
512
--------------------------------------------------------------------------- StopIteration Traceback (most recent call last) <ipython-input-32-02d3627ad286> in <module> 1 next(it) ----> 2 next(it) 3 next(it) 4 next(it) <ipython-input-25-a1a784c74543> in __next__(self) 115 return self.theList[self.theIndex-1] 116 else: --> 117 raise StopIteration() 118 # end of class definition 119 StopIteration:
for x in l:
print(x)
1 2 4 8 16 32 64 128 256 512
p=iter(l)
o=iter(l)
next(p)
next(p)
next(o)
next(o)
next(o)
1
2
1
2
4
yield¶What's a "generator"?
l = [ 2**x for x in range(5)] #list comprehension
l
[1, 2, 4, 8, 16]
m = ( 2**x for x in range(5)) #generator comprehension
m
# generators do not create all the items
#instead on demand when call "next"
<generator object <genexpr> at 0x0000020DFB4BB200>
next(m)
1
next(m)
2
next(m)
4
next(m)
next(m)
next(m)
8
16
--------------------------------------------------------------------------- StopIteration Traceback (most recent call last) <ipython-input-40-3c8b43cb6621> in <module> 1 next(m) 2 next(m) ----> 3 next(m) StopIteration:
m
next(m)
<generator object <genexpr> at 0x0000020DFB4BB200>
--------------------------------------------------------------------------- StopIteration Traceback (most recent call last) <ipython-input-42-5ef15a075fcd> in <module> 1 m ----> 2 next(m) StopIteration:
n = (2**x for x in range(5))
for i in n:
print(i)
1 2 4 8 16
# any fucntion with the command "yield" is a generator function
def foo():
print("called foo")
yield 1
print("called foo")
yield 2
print("called foo")
yield 3
g=foo()
next(g)
called foo
1
type(g)
generator
next(g)
called foo
2
next(g)
called foo
3
next(g)
--------------------------------------------------------------------------- StopIteration Traceback (most recent call last) <ipython-input-49-e734f8aca5ac> in <module> ----> 1 next(g) StopIteration:
def foo(max):
for i in range(max):
print("called foo")
yield i
g=foo(10)
next(g)
next(g)
called foo
0
called foo
1
next(g)
next(g)
next(g)
next(g)
next(g)
next(g)
next(g)
called foo
2
called foo
3
called foo
4
called foo
5
called foo
6
called foo
7
called foo
8
next(g)
called foo
9
next(g)
--------------------------------------------------------------------------- StopIteration Traceback (most recent call last) <ipython-input-53-e734f8aca5ac> in <module> ----> 1 next(g) StopIteration:
import numpy as np
class ArrayList:
def __init__(self): # constructor in python
# default arraylist size is 1 element
self.data = np.empty(1, dtype=object) # array variable name is "data"
self.size = 0 # how many items have been addded to the arrayList
# also tells us where to put the next item
# not the same as len(self.data)
# myList = ArrayList() calls __init__
def append(self, value):
# how do we append an item after the last item in the arraylist
# just put the item at the next index position
# if not fit, make a bigger array, copy over, then append
if self.size<len(self.data): # O(1)
self.data[self.size]=value
self.size+=1
else: # iteration needed for copy, slow
# options to make one larger, but then every append
# needs to do a O(self.size) copy of items O(n)
# instead assume more appends are coming, and make array much larger
# so this one append is slow, but future appends are fast
# accepted larger is twice as big
newArray = np.empty(len(self.data)*2, dtype=object)
# iterate over all the items in self.data
# copy them to same position in newArray
for i in range(len(self.data)):
newArray[i]=self.data[i]
newArray[self.size]=value
self.size+=1
self.data=newArray
def __getitem__(self, idx):
"""Implements `x = self[idx]`"""
assert(isinstance(idx, int))
# later implement error checking is idx valid (0 to self.size-1)
# later also support negative idx
# if they give us a valid index
idx=self.normalize_idx(idx) # correcting negative index
if idx<0 or idx>=self.size:
raise IndexError()
return self.data[idx]
def __setitem__(self, idx, value):
"""Implements `self[idx] = x`"""
# if they give us a valid index
assert(isinstance(idx, int))
self.data[idx]=value
def __delitem__(self, idx):
"""Implements `del self[idx]`"""
assert(isinstance(idx, int))
# don;t erase it or cross it out, don;t leave a hole
# move the items after the deleted item, up one
# shifting items
# if they give us a valid index
for i in range(idx, self.size-1): #len(self.data)
# i is the position we are moving to
#i+1 is the position we are moving from
self.data[i]=self.data[i+1]
self.data[self.size-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 normalize_idx(self, idx):
# error checking on out of range will be in get, set, del, insert
# will be done in those methods
# here we just fix the negative index
# corrects index from -1 to -N
# to index N-1 to 0
# we cannot do range checking here, because insert allows N as a valid index
newIdx=idx
if newIdx<0:
newIdx+=self.size
# what if newIdex is still negative?
# what if user gives -2N
# change the if to a while and get newIdx from 0 to N-1
# OR if still negative, set newIdx to 0
if newIdx<0:
newIdx=0
return newIdx
def __iter__(self): #this self is the arraylist self
# to make this function an generator it must have a yeild statement
# call to iter creates a generator object
# repeated calls to next will walk this loop
for i in range(self.size):
yield self.data[i]
# wait here for the following call to next
m = ArrayList()
m.append(5)
m.append(15)
m.append(25)
m.append(35)
for x in m:
print(x)
5 15 25 35
m = range(10)
m[3]
3
m[3]=12
--------------------------------------------------------------------------- TypeError Traceback (most recent call last) <ipython-input-59-15711c73a4b0> in <module> ----> 1 m[3]=12 TypeError: 'range' object does not support item assignment
for x in m:
print(x)
0 1 2 3 4 5 6 7 8 9