Need help on Python problem:
Using this:
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)
Tests:
We saw implementations of the add_and submethods 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. Note: it is possible to add and subtract sparse arrays of different lengths. Here is the behavior you should implement in that situation (which the tests below should corroborate): The result array should have the same length as the longer of the two arrays being added/subtracted. When we add/subtract two arrays, we do element-wise addition/subtraction of their elements; for instance, if we're adding/subtracting arrays a and b to create array c, then c[i] = a[i] + b[i] for all i (for addition) and c[i] = a[i] - b[i] for all i (for subtraction). If there's no element to use at a given index in one of the arrays because the array is too short, you should use that array's default value instead (recall that we're dealing with sparse arrays, which have a default value defined at the time they're created). [] ### Exercise: Implement add and sub for SparseArrayDict # YOUR CODE HERE raise Not ImplementedError() # These lines add the newly-defined functions # to the already-defined SparseArrayDict class as methods. SparseArrayDict. __add__ = sparse_array_dict_add SparseArrayDict. __sub_ = sparse_array_dict_sub [] ### Tests for arrays of the same length # Let us test this with arrays of the same length first. a = SparseArrayDict(1, 3, 4, 5) b = SparseArrayDict(5, 4, 3, 2) c = a + b assert isinstance(c, SparseArrayDict) assert_equal(c[0], 6) assert_equal(C[1], 7) assert_equal(C[3], 7) ### Tests for arrays of the same length, different default a = SparseArrayDict(default=1, size=10) b = SparseArrayDict(default=2, size=10) a[1] = 3 a[4] = 5 b[4] = 6 b[5] = 8 c = a + b assert_equal(C[0], 3) # This is due to the defaults. assert_equal(c[1], 5) assert_equal(c[2], 3) assert_equal(c[4], 11) assert_equal(C[5], 9) assert isinstance(C, SparseArrayDict) [] ### Tests for arrays of different length and default a = SparseArrayDict(default=1, size=10) b = SparseArrayDict(default=2, size=20) a[1] = 3 a[4] = 5 b[4] = 6 b[15] = 2 c = a + b assert_equal(len(c), 20) assert_equal(c[0], 3) assert_equal(c[1], 5) assert_equal(c[2], 3) assert_equal(c[4], 11) assert_equal(c[15], 3) assert isinstance(c, SparseArrayDict) [] ### Some tests for subtraction. a = SparseArrayDict(default=1, size=10) b = SparseArrayDict(default=2, size=20) a[1] = 3 a[4] = 7 b[4] = 6 b[15] = -2 c = a - b assert_equal(len(c), 20) assert_equal(c[0], -1) assert_equal(c[1], 1) assert_equal(c[2], -1) assert_equal(c[4], 1) assert_equal(c[15], 3) assert isinstance(c, SparseArrayDict) We saw implementations of the add_and submethods 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. Note: it is possible to add and subtract sparse arrays of different lengths. Here is the behavior you should implement in that situation (which the tests below should corroborate): The result array should have the same length as the longer of the two arrays being added/subtracted. When we add/subtract two arrays, we do element-wise addition/subtraction of their elements; for instance, if we're adding/subtracting arrays a and b to create array c, then c[i] = a[i] + b[i] for all i (for addition) and c[i] = a[i] - b[i] for all i (for subtraction). If there's no element to use at a given index in one of the arrays because the array is too short, you should use that array's default value instead (recall that we're dealing with sparse arrays, which have a default value defined at the time they're created). [] ### Exercise: Implement add and sub for SparseArrayDict # YOUR CODE HERE raise Not ImplementedError() # These lines add the newly-defined functions # to the already-defined SparseArrayDict class as methods. SparseArrayDict. __add__ = sparse_array_dict_add SparseArrayDict. __sub_ = sparse_array_dict_sub [] ### Tests for arrays of the same length # Let us test this with arrays of the same length first. a = SparseArrayDict(1, 3, 4, 5) b = SparseArrayDict(5, 4, 3, 2) c = a + b assert isinstance(c, SparseArrayDict) assert_equal(c[0], 6) assert_equal(C[1], 7) assert_equal(C[3], 7) ### Tests for arrays of the same length, different default a = SparseArrayDict(default=1, size=10) b = SparseArrayDict(default=2, size=10) a[1] = 3 a[4] = 5 b[4] = 6 b[5] = 8 c = a + b assert_equal(C[0], 3) # This is due to the defaults. assert_equal(c[1], 5) assert_equal(c[2], 3) assert_equal(c[4], 11) assert_equal(C[5], 9) assert isinstance(C, SparseArrayDict) [] ### Tests for arrays of different length and default a = SparseArrayDict(default=1, size=10) b = SparseArrayDict(default=2, size=20) a[1] = 3 a[4] = 5 b[4] = 6 b[15] = 2 c = a + b assert_equal(len(c), 20) assert_equal(c[0], 3) assert_equal(c[1], 5) assert_equal(c[2], 3) assert_equal(c[4], 11) assert_equal(c[15], 3) assert isinstance(c, SparseArrayDict) [] ### Some tests for subtraction. a = SparseArrayDict(default=1, size=10) b = SparseArrayDict(default=2, size=20) a[1] = 3 a[4] = 7 b[4] = 6 b[15] = -2 c = a - b assert_equal(len(c), 20) assert_equal(c[0], -1) assert_equal(c[1], 1) assert_equal(c[2], -1) assert_equal(c[4], 1) assert_equal(c[15], 3) assert isinstance(c, SparseArrayDict)
