Perform experiments to evaluate the efficiency of the remove method of Pythons list class, as we did for insert on page 205. Use known values so that all removals occur either at the beginning, middle, or end of the list. Report your results akin to Table 5.5.
python programming
5.4. Efficiency of Python's Sequence Types 205 Figure 5.16: Creating room to insert a new element at index k of a dynamic array. that process depends upon the index of the new element, and thus the number of other elements that must be shifted. That loop copies the reference that had been at index n- 1 to index n, then the reference that had been at index n -2 to n -1, continuing until copying the reference that had been at index k to k+1, as illus trated in Figure 5.16. Overall this leads to an amortized O(n - k +1) performance for inserting at index k. When exploring the efficiency of Python's append method in Section 5.3.3, we performed an experiment that measured the average cost of repeated calls on varying sizes of lists (see Code Fragment 5.4 and Table 5.2). We have repeated that experiment with the insert method, trying three different access patterns: In the first case, we repeatedly insert at the beginning of a list, for n in range(N) data.insert(0, None) In a second case, we repeatedly insert near the middle of a list for n in range(N) data.insert(n // 2, None) In a third case, we repeatedly insert at the end of the list, for n in range( N 5.4. Efficiency of Python's Sequence Types 205 Figure 5.16: Creating room to insert a new element at index k of a dynamic array. that process depends upon the index of the new element, and thus the number of other elements that must be shifted. That loop copies the reference that had been at index n- 1 to index n, then the reference that had been at index n -2 to n -1, continuing until copying the reference that had been at index k to k+1, as illus trated in Figure 5.16. Overall this leads to an amortized O(n - k +1) performance for inserting at index k. When exploring the efficiency of Python's append method in Section 5.3.3, we performed an experiment that measured the average cost of repeated calls on varying sizes of lists (see Code Fragment 5.4 and Table 5.2). We have repeated that experiment with the insert method, trying three different access patterns: In the first case, we repeatedly insert at the beginning of a list, for n in range(N) data.insert(0, None) In a second case, we repeatedly insert near the middle of a list for n in range(N) data.insert(n // 2, None) In a third case, we repeatedly insert at the end of the list, for n in range( N
