

In [ ]:

    
%%HTML
<style>
.container { width:100% } 
</style>

Implementing Maps as Arrays

If the keys are natural numbers that are not too big, a map can be implemented via an array. The class ArrayMap shows how this is done. The constructor init takes a second argument $n$. This argument specifies the size of the array.



In [ ]:

    
class ArrayMap:
    def __init__(self, n):
        self.mArray = [None] * (n + 1)
        
    def find(self, k):
        return self.mArray[k]
    
    def insert(self, k, v):
        self.mArray[k] = v

    def delete(self, k):
        self.mArray[k] = None
            
    def __repr__(self):
        result = '{ '
        for key, value  in enumerate(self.mArray):
            if value != None:
                result += str(key) + ': ' + str(value) + ', '
        if result == '{ ':
            return '{}'
        result = result[:-2] + ' }'
        return result



In [ ]:

    
squares = ArrayMap(10)
squares



In [ ]:

    
for i in range(10):
    squares.insert(i, i * i)
squares



In [ ]:

    
for i in range(10):
    print(f'find({i}) = {squares.find(i)}');



In [ ]:

    
for i in range(10):
    squares.delete(i)
squares

Lets compute the primes up to $n = 10000$.



In [ ]:

    
n = 10000



In [ ]:

    
%%time
S = ArrayMap(n)
for i in range(2, n+1):
    S.insert(i, i)
for i in range(2, n+1):
    for j in range(i, n+1):  
        if i * j > n:
            break
        S.delete(i * j)



In [ ]:

    
for k in range(2, n+1):
    if S.find(k):
        print(k, end=' ')



In [ ]: