Language is Python. Using these imports. The last one is from anaconda. DynamicA

Question

Language is Python. Using these imports. The last one is from anaconda.

DynamicArray:

Consider an implementation of a dynamic array, but instead of copying the ele- ments into an array of double the size (that is, from N to 2N) when its capacity is reached, we copy the elements into an array with N/Al additional cells, going from capacity N to capacity N LN/11. rove that performing a sequence of n append operations still runs in O(n) time in this case. Note: Prove this experimentally, by showing the O(n) trend graphically. You must first fix the implementation of DynamicArray. py to account for the new capacity resize. Notice that the capacity is incremented with the ceiling function on N/4. You must submit your implementation of DynamicArray.py to receive credit for this problem.

Explanation / Answer

import ctypes class DynamicArray(object): def __init__(self): self._n = 0 self._capacity = 1 self._A = self._make_array(self._capacity) def _make_array(self, c): return (c * ctypes.py_object)() # creates an "array" of pointers def __len__(self): return self._n def __getitem__(self, item): if not 0

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

---