Answered step by step
Verified Expert Solution
Link Copied!

Question

1 Approved Answer

Python Problem 1: Implementation of arithmetic operations class UndefinedSizeArray(Exception): pass class SparseArrayDict: def __init__(self, *args, default=0., size=None): If args are specified, they form the initial

Python Problem 1: Implementation of arithmetic operations

class UndefinedSizeArray(Exception):

pass

class SparseArrayDict:

def __init__(self, *args, default=0., size=None):

"""If args are specified, they form the initial values for the array.

Otherwise, we need to specify a size."""

self.d = {}

self.default = default

if len(args) > 0:

# We build a representation of the arguments, args.

self.length = len(args)

for i, x in enumerate(args):

if x != default:

self.d[i] = x

if size is not None:

self.length = size

elif len(args) > 0:

self.length = len(args)

else:

raise UndefinedSizeArray

def __repr__(self):

"""We try to build a nice representation."""

if len(self)

# The list() function uses the iterator, which is

# defined below.

return repr(list(self))

else:

s = "The array is a {}-long array of {},".format(

self.length, self.default

)

s += " with the following exceptions: "

ks = list(self.d.keys())

ks.sort()

s += " ".join(["{}: {}".format(k, self.d[k]) for k in ks])

return s

def __setitem__(self, i, x):

"""Implements the a[i] = x assignment operation."""

assert isinstance(i, int) and i >= 0

if x == self.default:

# We simply remove any exceptions.

if i in self.d:

del self.d[i]

else:

self.d[i] = x

# Adjusts the length.

self.length = max(self.length, i + 1)

def __getitem__(self, i):

"""Implements evaluation of a[i]."""

if i >= self.length:

raise IndexError()

return self.d.get(i, self.default)

def __len__(self):

"""Implements the len() operator."""

return self.length

def __iter__(self):

# You may think this is a terrible way to iterate.

# But in fact, it's quite efficient; there is no

# markedly better way.

for i in range(len(self)):

yield self[i]

def storage_len(self):

"""This returns a measure of the amount of space used for the array."""

return len(self.d)

image text in transcribed

image text in transcribed

image text in transcribedimage text in transcribed

image text in transcribed

Sparse Arrays Using Dictionaries Below is the dictionary-based sparse array implementation that we saw during lecture. Recall from lecture that sparse arrays are designed for efficiently representing arrays where most of the elements are a default value, and that one way to do this is to store only the non-default elements in a dictionary that maps from indices to values. [] class UndefinedSizeArray(Exception): pass class SparseArrayDict: def __init__(self, *args, default=0., size=None): """If args are specified, they form the initial values for the array. Otherwise, we need to specify a size."" self.d = {} self.default = default if len(args) > 0: # We build a representation of the arguments, args. self.length = len(args) for i, xin enumerate(args) : if x != default: self.d[i] = x if size is not None: self.length = size elif len(args) > 0: self.length = len(args) else: raise UndefinedSizeArray def_repr__(self): "" "We try to build a nice representation.""" if len(self) = 0 if x == self.default: # We simply remove any exceptions. if i in self.d: del self.d[i] else: self.d[i] = x # Adjusts the length. self.length = max(self.length, i + 1) ___getitem_(self, i): "" "Implements evaluation of a[i].""" if i >= self.length: raise IndexError() return self.d.get(i, self.default) def len_(self): """Implements the len() operator."" return self.length def __iter__(self): # You may think this is a terrible way to iterate. # But in fact, it's quite efficient; there is no # markedly better way. for i in range (len (self)): yield self[i] def storage len(self): "" "This returns a measure of the amount of space used for the array.""" return len(self.d) Run the following cells to refresh your memory about what the SparseArrayDict methods do. [ ] a = SparseArrayDict(size=10) a[2] = 4 a[7] = 1 [0.0, 0.0, 4, 0.0, 0.0, 0.0, 0.0, 1, 0.0, 0.0] [ ] a = SparseArrayDict(size=100) a[77] = 3 a[23] = 1 print("len(a):", len(a)). print("storage_len(a):", a.storage_len()). > len(a): 100 storage_len(a): 2 [] a The array is a 100-long array of 0.0, with the following exceptions 23: 1 77: 3 Problem 1: Implementation of arithmetic operations We saw implementations of the _add__ and __sub_ methods for non-sparse arrays during lecture. These methods implemented element- wise addition (+) and subtraction ( - ) of non-sparse arrays. For instance, if we have a = Array(1, 2, 3, 4) and b = Array(0, 1, 0, 4), then a + b evaluates to [1, 3, 3, 8] and a - b evaluates to [1, 1, 3, 0]. For this exercise, you will implement the analogous ___add__ and __sub_ methods for SparseArrayDict. The efficient way to do this is: First, create a new array for the result, with the appropriate default value. For example, if you're adding arrays, the default value of the new array should be the result of adding the default values of the two existing arrays. Then, figure out which elements are different from the default in one (or more) of the arrays being combined. Lastly, for these non-default elements, set their value appropriately in the result array. At a minimum, you will need to define functions named sparse_array_dict_add and sparse_array_dict_sub in the below cell. An elegant way of solving this problem consists of factoring out their common code into a third, common method that they both call, since the two methods are so similar. Otherwise, you can implement sparse_array_dict_add first, and once you get it to work, copy and paste it, and make the few changes required to obtain sparse_array_dict_sub

Step by Step Solution

There are 3 Steps involved in it

Step: 1

blur-text-image

Get Instant Access to Expert-Tailored Solutions

See step-by-step solutions with expert insights and AI powered tools for academic success

Step: 2

blur-text-image

Step: 3

blur-text-image

Ace Your Homework with AI

Get the answers you need in no time with our AI-driven, step-by-step assistance

Get Started

Recommended Textbook for

Fundamentals Of Database System

Authors: Elmasri Ramez And Navathe Shamkant

7th Edition

978-9332582705

More Books

Students also viewed these Databases questions

Question

Find a possible formula for the graph. 6 3 y 4 8 X

Answered: 1 week ago