算法练习(89):自动装箱的性能代价(1.4.36-1.4.4

本系列博客习题来自《算法(第四版)》，算是本人的读书笔记，如果有人在读这本书的，欢迎大家多多交流。为了方便讨论，本人新建了一个微信群(算法交流)，想要加入的，请添加我的微信号：zhujinhui207407 谢谢。另外，本人的个人博客 http://www.kyson.cn 也在不停的更新中，欢迎一起讨论

算法(第4版)

知识点

• 自动装箱的性能代价

题目

1.4.37 自动装箱的性能代价。通过实验在你的计算机上计算使用自动装箱所付出的性能代价。实现一个 FixedCapacityStackOfInts，并使用类似 DoublingRatio 的用例比较它和泛型 FixedCapacityStack 在进行大量 push() 和 pop() 时的性能。

---

1.4.37 Autoboxing performance penalty. Run experiments to determine the perfor- mance penalty on your machine for using autoboxing and auto-unboxing. Develop an implementation FixedCapacityStackOfInts and use a client such as DoublingRatio to compare its performance with the generic FixedCapacityStack<Integer>, for a large number of push() and pop() operations.

1.4.38 Naive 3-sum implementation. Run experiments to evaluate the following im- plementation of the inner loop of ThreeSum:
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
for (int k = 0; k < N; k++)
if (i < j && j < k)
if (a[i] + a[j] + a[k] == 0)
cnt++;
Do so by developing a version of DoublingTest that computes the ratio of the running times of this program and ThreeSum.

1.4.39 Improved accuracy for doubling test. Modify DoublingRatio to take a second command-line argument that specifies the number of calls to make to timeTrial() for each value of N. Run your program for 10, 100, and 1,000 trials and comment on the precision of the results.

1.4.40 3-sum for random values. Formulate and validate a hypothesis describing the number of triples of N random int values that sum to 0. If you are skilled in math- ematical analysis, develop an appropriate mathematical model for this problem, where the values are uniformly distributed between –M and M, where M is not small.

1.4.41 Running times. Estimate the amount of time it would take to run TwoSumFast, TwoSum, ThreeSumFast and ThreeSum on your computer to solve the problems for a file of 1 million numbers. Use DoublingRatio to do so.

1.4.42 Problem sizes. Estimate the size of the largest value of P for which you can run TwoSumFast, TwoSum, ThreeSumFast, and ThreeSum on your computer to solve the problems for a file of 2P thousand numbers. Use DoublingRatio to do so.

1.4.43 Resizing arrays versus linked lists. Run experiments to validate the hypothesis that resizing arrays are faster than linked lists for stacks (see Exercise 1.4.35 and Exer- cise 1.4.36). Do so by developing a version of DoublingRatio that computes the ratio of the running times of the two programs.

1.4.44 Birthday problem. Write a program that takes an integer N from the command line and uses StdRandom.uniform() to generate a random sequence of integers be- tween 0 and N – 1. Run experiments to validate the hypothesis that the number of integers generated before the first repeated value is found is ~ N/2.

1.4.45 Coupon collector problem. Generating random integers as in the previous exercise, run experiments to validate the hypothesis that the number of integers generated before all possible values are generated is ~N HN.