本系列博客習(xí)題來(lái)自《算法(第四版)》，算是本人的讀書(shū)筆記，如果有人在讀這本書(shū)的，歡迎大家多多交流。為了方便討論，本人新建了一個(gè)微信群(算法交流)，想要加入的，請(qǐng)?zhí)砑游业奈⑿盘?hào)：zhujinhui207407 謝謝。另外，本人的個(gè)人博客 http://www.kyson.cn 也在不停的更新中，歡迎一起討論
知識(shí)點(diǎn)
- 自動(dòng)裝箱的性能代價(jià)
題目
1.4.37 自動(dòng)裝箱的性能代價(jià)。通過(guò)實(shí)驗(yàn)在你的計(jì)算機(jī)上計(jì)算使用自動(dòng)裝箱所付出的性能代價(jià)。實(shí)現(xiàn)一個(gè) FixedCapacityStackOfInts，并使用類似 DoublingRatio 的用例比較它和泛型 FixedCapacityStack 在進(jìn)行大量 push() 和 pop() 時(shí)的性能。
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.
